Inapproximability of the Tutte polynomial of a planar graph

DOI10.1007/s00037-012-0046-4zbMath1282.68122arXiv0907.1724MaRDI QIDQ1926110

Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 27 December 2012

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

Tutte polynomial; approximate counting; FPRAS

Mathematics Subject Classification ID

05C31: Graph polynomials

05A15: Exact enumeration problems, generating functions

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

68W20: Randomized algorithms

Related Items

Density of Real Zeros of the Tutte Polynomial, The complexity of approximating the complex-valued Potts model, Approximate Counting via Correlation Decay in Spin Systems, The complexity of approximating complex-valued Ising and Tutte partition functions, The complexity of approximating the complex-valued Potts model, Functional clones and expressibility of partition functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Inapproximability of the Tutte polynomial
• Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
• Some simplified NP-complete graph problems
• The largest real zero of the chromatic polynomial
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On the computational complexity of the Jones and Tutte polynomials
• The Computational Complexity of Tutte Invariants for Planar Graphs
• Chromatic Polynomials