The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation)

DOI10.1007/978-3-642-31594-7_34zbMath1272.68155arXiv1202.0313OpenAlexW93786605MaRDI QIDQ2843265

Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 12 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

Tutte polynomial of a graph

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 (2)

Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ On metaplectic modular categories and their applications

This page was built for publication: The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation)