On the computational complexity of the Jones and Tutte polynomials

1990/07/01 by François Jaeger, Dirk Vertigan, Dominic Welsh · 26 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Combinatorial Mathematics #Geometric and Algebraic Topology #Tutte polynomial #Combinatorics #Chromatic polynomial #Matroid #Mathematics #Polynomial #Discrete mathematics #Graph #Mathematical analysis

paper · doi:10.1017/s0305004100068936

openalex publication_date 1990/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/23

Abstract

Abstract We show that determining the Jones polynomial of an alternating link is # P -hard. This is a special case of a wide range of results on the general intractability of the evaluation of the Tutte polynomial T(M; x, y) of a matroid M except for a few listed special points and curves of the (x, y) -plane. In particular the problem of evaluating the Tutte polynomial of a graph at a point in the (x, y) -plane is # P -hard except when (x − 1)(y − 1) = 1 or when (x, y) equals (1, 1), (−1, −1), (0, −1), (−1, 0), (i, −i), (−i, i), (j, j 2 ), (j 2 , j) where j = e 2πi/3

Citations

• The complexity of computing the permanent
• Some simplified NP-complete graph problems
• On Isomorphisms and Density of NP and Other Complete Sets
• The Complexity of Enumeration and Reliability Problems
• The Tutte polynomial
• On the Abstract Properties of Linear Dependence

Cited by

• The Potts model and the Tutte polynomial
• The Computational Complexity of Tutte Invariants for Planar Graphs
• Computing the Tutte Polynomial in Vertex-Exponential Time
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Computing Tutte Polynomials
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Zesting and the relative complexity of Reshetikhin-Turaev invariants
• Inapproximability of the Tutte polynomial
• Relative Tutte Polynomials of Tensor Products of Coloured Graphs
• Relaxations of GF(4)-representable matroids
• The computational complexity of knot and link problems
• Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
• A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• Computing the Tutte Polynomial on Graphs of Bounded Clique-Width
• Graph Polynomials and Their Applications I: The Tutte Polynomial
• Chromatic, Flow and Reliability Polynomials: The Complexity of their Coefficients
• Asymptotic behavior of spanning forests and connected spanning subgraphs on two-dimensional lattices
• The BQP-hardness of approximating the Jones polynomial
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Topological quantum computing and the Jones polynomial
• Chromatic polynomial [wikipedia]
• Graph coloring [wikipedia]
• Spanning tree [wikipedia]
• Tutte polynomial [wikipedia]