Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions

DOI10.1007/s00224-009-9213-7zbMath1206.68137OpenAlexW2020085754MaRDI QIDQ987376

Markus Bläser, Holger Dell, Johann A. Makowsky

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9213-7

zbMATH Keywords

computational complexityTutte polynomialgraph polynomialsalgebraic reductions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On the complexity of generalized chromatic polynomials

Uses Software

• tutte_bhkk

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• A Tutte polynomial for signed graphs
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• On the algebraic complexity of some families of coloured Tutte polynomials
• Acyclic orientations of graphs. (Reprint)
• PP is as Hard as the Polynomial-Time Hierarchy
• The Travelling Salesman Problem in Bounded Degree Graphs
• A Most General Edge Elimination Polynomial – Thickening of Edges
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Hard Enumeration Problems in Geometry and Combinatorics
• A Tutte Polynomial for Coloured Graphs
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On the computational complexity of the Jones and Tutte polynomials
• A Most General Edge Elimination Polynomial
• Complexity of the Cover Polynomial