Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree
verfasst von : Markus Bläser, Radu Curticapean
Erschienen in: Mathematical Foundations of Computer Science 2011
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The cover polynomials are bivariate graph polynomials that can be defined as weighted sums over all path-cycle covers of a graph. In [3], a dichotomy result for the cover polynomials was proven, establishing that their evaluation is #
P
-hard everywhere but at a finite set of points, where evaluation is in
FP
. In this paper, we show that almost the same dichotomy holds when restricting the evaluation to planar graphs. We even provide hardness results for planar DAGs of bounded degree. For particular subclasses of planar graphs of bounded degree and for variants thereof, we also provide algorithms that allow for polynomial-time evaluation of the cover polynomials at certain new points by utilizing Valiant’s holographic framework.