Paper Info
Title
Complexity and Approximability of the Cover Polynomial
Abstract
The cover polynomial and its geometric version introduced by Chung & Graham and D’Antona & Munarini, respectively, are two-variate graph polynomials for directed graphs. They count the (weighted) number of ways to cover a graph with disjoint directed cycles and paths, can be thought of as interpolations between determinant and permanent, and are proposed as directed analogues of the Tutte polynomial. Jaeger, Vertigan, and Welsh showed that the Tutte polynomial is #P-hard to evaluate at all but a few special points and curves. It turns out that the same holds for the cover polynomials: We prove that, in almost the whole plane, the problem of evaluating the cover polynomial and its geometric version is #P-hard under polynomial time Turing reductions, while only three points in the cover polynomial and two points in the geometric cover polynomial are easy. We also study the complexity of approximately evaluating the geometric cover polynomial. Under the reasonable complexity assumptions RP ≠ NP and RFP ≠ #P, we give a succinct characterization of a large class of points at which approximating the geometric cover polynomial within any polynomial factor is not possible.
Year
DOI
Venue
2012
10.1007/s00037-011-0018-0
Computational Complexity
Keywords
Field
DocType
tutte polynomial,large class,counting complexity,geometric cover polynomial,. graph polynomial,two-variate graph polynomial,cover polynomial,reasonable complexity assumption,permanent,approximation,geometric version,polynomial time,polynomial factor,special point
Alternating polynomial,Discrete mathematics,Combinatorics,Stable polynomial,Tutte polynomial,Edge cover,Monic polynomial,Reciprocal polynomial,Matrix polynomial,Chromatic polynomial,Mathematics
Journal
Volume
Issue
ISSN
21
3
1420-8954
Citations 
PageRank 
References 
3
0.39
24
Authors
3
Name
Order
Citations
PageRank
Markus Bläser132634.03
Holger Dell222016.74
Mahmoud Fouz322613.16