The Complexity of Computing the Sign of the Tutte Polynomial

DOI10.1137/12088330XzbMath1437.68068MaRDI QIDQ5112588

Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 31 May 2020

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

Mathematics Subject Classification ID

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

Related Items (14)

The complexity of approximating the complex-valued Potts model ⋮ Block interpolation: a framework for tight exponential-time counting complexity ⋮ 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 ⋮ Approximating the chromatic polynomial is as hard as computing it exactly ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Unnamed Item ⋮ Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid ⋮ Density of Real Zeros of the Tutte Polynomial ⋮ A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability ⋮ The complexity of approximating the complex-valued Potts model ⋮ The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs ⋮ Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

This page was built for publication: The Complexity of Computing the Sign of the Tutte Polynomial