Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Computational Complexity - Bachelor's and Master's Theses

Holger Dell: Complexity of the Cover Polynomial

Master's Thesis, 2007.

Advisor: Prof. Dr. Markus Bläser

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 #P-hard 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 #P-hard under polynomial-time Turing reductions, while three points are easy and one line stays unclassified. 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.

Related Publications

• [P]Markus Bläser, Holger Dell
Complexity of the Cover Polynomial.
Automata, Languages and Programming, 34th International Colloquium (ICALP) in Lecture Notes in Computer Science 4596:801-8122007.
• [J]Markus Bläser, Holger Dell, Johann Makowsky
Complextiy of the Bollobas-Riordan Polynomial. Exceptional Points and Uniform Reductions.
Theory of Computing Systems, 46(4):690-706, 2010.
PDF