Complexity and approximability of the cover polynomial

DOI10.1007/S00037-011-0018-0MaRDI QIDQ445242zbMATH OpenOpenAlexFDO

Authors Markus Bläser, Holger Dell, Mahmoud Fouz

Publication date 24 August 2012

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-011-0018-0

zbMATH Keywords

graph polynomialapproximationTutte polynomialcounting complexitypermanent

Mathematics Subject Classification ID

Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Complexity of the Cover Polynomial
• The complexity of the cover polynomials for planar graphs of bounded degree
• Inapproximability of the Tutte polynomial
• The complexity of computing the sign of the Tutte polynomial (and consequent \#P-hardness of approximation)
• Inapproximability of the Tutte polynomial of a planar graph

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1859208 (Why is no real title available?)
• A Most General Edge Elimination Polynomial
• A Tutte Polynomial for Coloured Graphs
• A most general edge elimination polynomial -- thickening of edges
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• A short proof of the rook reciprocity theorem
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• Complexity of the Bollobás-Riordan Polynomial
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Hard Enumeration Problems in Geometry and Combinatorics
• Inapproximability of the Tutte polynomial
• NP is as easy as detecting unique solutions
• On Counting Homomorphisms to Directed Acyclic Graphs
• On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids
• On the algebraic complexity of some families of coloured Tutte polynomials
• On the computational complexity of the Jones and Tutte polynomials
• On the cover polynomial of a digraph
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• The Travelling Salesman Problem in Bounded Degree Graphs
• The complexity of computing the permanent
• The complexity of partition functions
• The cycle-path indicator polynomial of a digraph

Cited in

(10)

• An algorithm of polynomial order for computing the covering dimension of a finite space
• Noncommutativity makes determinants hard
• The matrix cover polynomial
• Minimum constellation covers: hardness, approximability and polynomial cases
• Complexity and approximation of the connected set-cover problem
• The complexity of the cover polynomials for planar graphs of bounded degree
• scientific article; zbMATH DE number 1760347 (Why is no real title available?)
• Partially Polynomial Kernels for Set Cover and Test Cover
• Complexity of the Cover Polynomial
• Polynomial-time algorithms for regular set-covering and threshold synthesis

Describes a project that uses

Uses Software

• tutte_bhkk

This page was built for publication: Complexity and approximability of the cover polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q445242)