Inapproximability of the Tutte polynomial

DOI10.1016/j.ic.2008.04.003zbMath1153.68039arXivcs/0605140OpenAlexW2122765404WikidataQ55879601 ScholiaQ55879601MaRDI QIDQ937302

Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 14 August 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0605140

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (35)

Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs ⋮ The complexity of approximating the complex-valued Potts model ⋮ The complexity of weighted Boolean \#CSP with mixed signs ⋮ Block interpolation: a framework for tight exponential-time counting complexity ⋮ Random cluster dynamics for the Ising model is rapidly mixing ⋮ Mixing of the Glauber dynamics for the ferromagnetic Potts model ⋮ Edge cut splitting formulas for Tutte-Grothendieck invariants ⋮ Inapproximability of the Tutte polynomial of a planar graph ⋮ The complexity of approximating complex-valued Ising and Tutte partition functions ⋮ Approximating the chromatic polynomial is as hard as computing it exactly ⋮ Sparse reliable graph backbones ⋮ Unnamed Item ⋮ Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid ⋮ Some Problems on Approximate Counting in Graphs and Matroids ⋮ Triangulations of Cayley and Tutte polytopes ⋮ Complexity and approximability of the cover polynomial ⋮ Unnamed Item ⋮ Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ The BQP-hardness of approximating the Jones polynomial ⋮ Counting Constraint Satisfaction Problems. ⋮ Expansions for the Bollobás-Riordan polynomial of separable ribbon graphs ⋮ The Ising partition function: zeros and deterministic approximation ⋮ Density of Real Zeros of the Tutte Polynomial ⋮ Modifications of Tutte–Grothendieck invariants and Tutte polynomials ⋮ ON THE QUANTUM COMPLEXITY OF EVALUATING THE TUTTE POLYNOMIAL ⋮ Holomorphic quadratic differentials on graphs and the chromatic polynomial ⋮ Interpretations of the Tutte and characteristic polynomials of matroids ⋮ Some Inequalities for Whitney–Tutte Polynomials ⋮ The Exponential Time Complexity of Computing the Probability That a Graph Is Connected ⋮ A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid ⋮ A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability ⋮ The complexity of approximating the complex-valued Potts model ⋮ Interpretations of the Tutte polynomials of regular matroids ⋮ Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random generation of combinatorial structures from a uniform distribution
• NP is as easy as detecting unique solutions
• Nowhere-zero 6-flows
• The relative complexity of approximate counting problems
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• The Tutte Polynomial Part I: General Theory
• Polynomial-Time Approximation Algorithms for the Ising Model
• Hard Enumeration Problems in Geometry and Combinatorics
• Approximation Algorithms for Several Graph Augmentation Problems
• The Complexity of Multiterminal Cuts
• Randomised Approximation in the Tutte Plane
• On the computational complexity of the Jones and Tutte polynomials
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• On Unapproximable Versions of $NP$-Complete Problems
• A Contribution to the Theory of Chromatic Polynomials

This page was built for publication: Inapproximability of the Tutte polynomial