Name
Abstract | ||
|---|---|---|
The cover polynomial introduced by Chung and Graham is a two-variate graph polynomial for directed graphs. It counts the (weighted) number of ways to cover a graph with disjoint directed cycles and paths, it is an interpolation between determinant and permanent, and it is believed to be a directed analogue of the Tutte polynomial. Jaeger, Vertigan, and Welsh showed that the Tutte polynomial is #Phard to evaluate at all but a few special points and curves. It turns out that the same holds for the cover polynomial: We prove that, in almost the whole plane, the problem of evaluating the cover polynomial is #Phard under polynomial-time Turing reductions, while only three points are easy. Our construction uses a gadget which is easier to analyze and more general than the XOR-gadget used by Valiant in his proof that the permanent is #P-complete. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-73420-8_69 | ICALP |
Keywords | Field | DocType |
whole plane,polynomial-time turing reduction,tutte polynomial,two-variate graph polynomial,special point,cover polynomial,directed graph,polynomial time | Discrete mathematics,Characteristic polynomial,Stable polynomial,Combinatorics,Edge cover,Tutte polynomial,Monic polynomial,Reciprocal polynomial,Matrix polynomial,Chromatic polynomial,Mathematics | Conference |
Volume | ISSN | ISBN |
4596 | 0302-9743 | 3-540-73419-8 |
Citations | PageRank | References |
18 | 0.82 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Markus Bläser | 1 | 326 | 34.03 |
| Holger Dell | 2 | 220 | 16.74 |