The complexity of computing the sign of the Tutte polynomial

DOI10.1137/12088330XMaRDI QIDQ5112588zbMATH OpenFDO

Authors Leslie Ann Goldberg, Mark Jerrum

Publication date 31 May 2020

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/12088330X

Mathematics Subject Classification ID

Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• 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
• Inapproximability of the Tutte polynomial
• The complexities of the coefficients of the Tutte polynomial
• The computational complexity of knot and matroid polynomials

Cited in

(24)

• The computational complexity of knot and matroid polynomials
• Random cluster dynamics for the Ising model is rapidly mixing
• The complexity of approximating complex-valued Ising and Tutte partition functions
• Density of real zeros of the Tutte polynomial
• Inapproximability of the Tutte polynomial of a planar graph
• The complexity of approximating the complex-valued Potts model
• The complexity of computing the sign of the Tutte polynomial (and consequent \#P-hardness of approximation)
• Chromatic, Flow and Reliability Polynomials: The Complexity of their Coefficients
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Density of real zeros of the Tutte polynomial
• scientific article; zbMATH DE number 7375995 (Why is no real title available?)
• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• The complexity of approximating the complex-valued Potts model
• A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
• The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
• Approximating the chromatic polynomial is as hard as computing it exactly
• Parameterized Counting and Cayley Graph Expanders
• Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
• On the complexity of generalized chromatic polynomials
• Two-state spin systems with negative interactions
• Two-state spin systems with negative interactions
• Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
• Inapproximability of the Tutte polynomial
• Complexity measures of sign matrices

This page was built for publication: The complexity of computing the sign of the Tutte polynomial

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