Completing the approximability classification of the Tutte polynomial of a planar graph: the unclassified points of the Tutte plane and the strength of the hardness conclusions

The Tutte polynomial $T(G;x,y)$ of a planar graph can be computed exactly in polynomial time only on the hyperbolas $H_1$ and $H_2$ and at the two points $(1,1)$ and $(-1,-1)$ (Vertigan); at every other rational point the exact problem is #P-hard. Goldberg and Jerrum (2012) initiated the approximation-side classification: assuming $\mathrm{NP}\neq\mathrm{RP}$ , no FPRAS (fully polynomial randomised approximation scheme) exists for planar inputs in the regions $x<0\wedge y<0$ with $(x-1)(y-1)>5$ , on the branch of $H_3$ with $x<1$ and $y<1$ , and in the quadrants $x>1\wedge y<-1$ and $y>1\wedge x<-1$ . They explicitly left open the limit points of these regions — the chromatic point $(1-q,0)$ , counting proper $q$ -colourings, and the flow point $(0,1-q)$ — the band $q\in[0,5]$ , the strength of the hardness conclusion ( $\mathrm{NP}=\mathrm{RP}$ versus #P-hardness, as suggested by Kuperberg, whose sketch, if fillable, would also relax $q>5$ to $q\ge 4$ in the negative quadrant), and the whole 'white region' of their map. The chromatic and flow points for integers $q\ge 4$ have since been resolved in a recent preprint of Guo and Zhang (2026) — no FPRAS unless $\mathrm{NP}=\mathrm{RP}$ , with the flow point following by planar duality — and non-real (complex) parameter values are fully classified as #P-hard even on planar graphs. The surviving problem is to complete the classification: determine FPRASability at every remaining rational point — the ferromagnetic region $x>1,y>1$ (zero-field ferromagnetic Potts model), the non-integer chromatic and flow axes, the interior of the square $-1<x,y<1$ , the forest axes, and the $q\in[0,5]$ band where dense chromatic zeros block the known technique — and to settle whether the hardness at real points can be strengthened from $\mathrm{NP}=\mathrm{RP}$ -conditionality to #P-hardness.

Background

The Tutte polynomial $T(G;x,y)$ of a graph $G=(V,E)$ is a two-variable graph invariant that specialises to many classical quantities. Along the hyperbola $H_q=\{(x,y):(x-1)(y-1)=q\}$ it is, up to a normalising prefactor, the partition function of the $q$ -state Potts model of statistical mechanics in its random-cluster form $Z(G;q,v)=\sum_{A\subseteq E}q^{k(A)}v^{|A|}$ , where $k(A)$ is the number of connected components of the spanning subgraph $(V,A)$ and $v=y-1$ ; $H_2$ is the Ising model; $T(G;1,1)$ counts spanning trees, and on $H_1$ (the case $q=1$ ) the random-cluster sum collapses to $(1+v)^{|E|}$ , which is why evaluations there are elementary. Two axis specialisations are especially notable: the chromatic polynomial $P(G;\lambda)=(-1)^{n-k}\lambda^{k}T(G;1-\lambda,0)$ , which for positive integer $\lambda$ counts proper $\lambda$ -colourings of $G$ (assignments of colours to vertices such that the two ends of every edge receive different colours), and the flow polynomial $F(G;\lambda)=(-1)^{m-n+k}T(G;0,1-\lambda)$ , which for positive integer $\lambda$ counts nowhere-zero $\lambda$ -flows (assignments of non-zero elements of a fixed abelian group of order $\lambda$ to edges so that flow is conserved at every vertex). For a connected planar graph $G$ with planar dual $G^*$ , $T(G;x,y)=T(G^*;y,x)$ , so the chromatic and flow points are the same computational problem up to duality.

On the computational side, #P is the class of counting problems associated with NP verification (counting satisfying assignments rather than merely finding one), and a problem is #P-hard if solving it would solve every problem in #P. An FPRAS (fully polynomial randomised approximation scheme) for a non-negative quantity $Z$ is a randomised algorithm that, given an input $G$ and $\varepsilon\in(0,1)$ , outputs $\hat Z$ with $\Pr[e^{-\varepsilon}Z\le \hat Z\le e^{\varepsilon}Z]\ge 3/4$ in time polynomial in the input size and $1/\varepsilon$ ; the success probability $3/4$ is a convention that can be amplified. RP denotes one-sided-error randomised polynomial time. A statement of the form 'no FPRAS unless $\mathrm{NP}=\mathrm{RP}$ ' follows from a randomised reduction of an NP-hard decision problem to the approximation task, while '#P-hardness of approximation' is a strictly stronger conclusion: any approximation algorithm would give randomised polynomial-time algorithms for all of #P.

Jaeger, Vertigan and Welsh (1990) completely mapped the exact complexity of evaluating $T(G;x,y)$ for general graphs: evaluation is in FP (deterministic polynomial time) exactly on $H_1$ and at the points $(1,1)$ , $(0,-1)$ , $(-1,0)$ and $(-1,-1)$ , and #P-hard at every other rational point. Vertigan (2005) proved the analogous dichotomy for planar inputs: restricted to planar graphs, evaluation is in FP on $H_1$ and $H_2$ and at $(1,1)$ and $(-1,-1)$ — the $H_2$ case being the celebrated polynomial-time Ising algorithm obtained via the Fisher–Kasteleyn reduction to counting perfect matchings in a planar graph — and #P-hard everywhere else. The approximation side is harder. Goldberg and Jerrum (2008) mapped inapproximability for general graphs using heavily non-planar constructions, and in the 2012 paper that generates the present problem they showed, by planarity-preserving reductions, that assuming $\mathrm{NP}\neq\mathrm{RP}$ there is no FPRAS for $\mathrm{PlanarTutte}(x,y)$ — the problem of approximating $T(G;x,y)$ given a planar $G$ — in four regions: $x<0$ , $y<0$ , $(x-1)(y-1)>5$ ; $x<1$ , $y<1$ , $(x-1)(y-1)=3$ (the branch of $H_3$ lying in $x<1$ , $y<1$ ); $x>1$ , $y<-1$ ; and $y>1$ , $x<-1$ . Their map leaves a 'white region' of unclassified points, and they highlight specific gaps: the negative-quadrant construction approaches, along $H_q$ , the chromatic point $(1-q,0)$ and the flow point $(0,1-q)$ but does not cover these limit points; extending the hardness to $(x-1)(y-1)\in[0,5]$ is blocked by a sign condition that fails because chromatic polynomials have many zeros in $(0,5)$ ; and the hardness conclusions are conditioned on $\mathrm{NP}\neq\mathrm{RP}$ rather than being #P-hardness. For comparison, for unrestricted graphs approximating the chromatic polynomial at real $q>2$ was already known to be intractable (Goldberg–Jerrum 2008), so it is the planarity restriction that makes the question delicate.

Subsequent work resolved parts of this picture. For non-real (complex) parameter values the classification is complete: multiplicatively approximating the Ising/Tutte/Potts partition function at non-real algebraic parameters is #P-hard even restricted to planar graphs (Goldberg–Guo 2017; Galanis–Goldberg–Herrera-Poyatos 2022; Bencs–Huijben–Regts 2024 for the chromatic polynomial). Kuperberg (2015), whose 2009 proof sketch motivated the #P-hardness question, proved in his published paper that value-dependent approximation of the Jones polynomial (a knot invariant that arises as a specialisation of the Tutte polynomial) is #P-hard at non-lattice principal roots of unity, again a complex-parameter statement that does not settle the real points. For general (non-planar) graphs, Goldberg–Jerrum (2014) showed that even computing the sign of the Tutte polynomial is #P-hard in large regions, which implies #P-hardness of approximation there, and that computing the sign of the chromatic polynomial is NP-hard for every real $q>32/27$ except $q=2$ ; these sign arguments do not transfer to planar graphs. Most recently, Guo and Zhang (2026) resolved the integer chromatic point: for every integer $q\ge 4$ , an FPRAS for the number of proper $q$ -colourings of planar graphs would imply $\mathrm{NP}=\mathrm{RP}$ (for $q=3$ the same conclusion follows from NP-completeness of planar 3-colourability, while $q=2$ is exactly computable), and by planar duality the same holds for the flow polynomial at integers $q\ge 4$ . What remains open — the subject of this problem — is the rest of the map: the ferromagnetic region $x>1,y>1$ apart from the exactly computable hyperbolas $H_1$ and $H_2$ (it contains the zero-field ferromagnetic $q$ -state Potts model for integers $q\ge 3$ , whose approximability is open even for unrestricted graphs, where it is known to be as hard as counting independent sets in bipartite graphs), the strips $x>1,-1<y<1$ and $-1<x<1,y>1$ , the interior of the square $-1<x,y<1$ outside the exactly computable hyperbolas $H_1$ and $H_2$ and the inapproximable branch of $H_3$ , the axes $x=1$ and $y=1$ away from $(1,1)$ (spanning-forest and connected-subgraph generating functions), the chromatic and flow axes at non-integer real $q$ (the non-integer rational points among them are what the rational-point classification requires), and the whole band $(x-1)(y-1)\in[0,5]$ . A further complication, established by Ok and Perrett, is that the zeros of Tutte polynomials of graphs are dense in much of the antiferromagnetic region, so any technique for the $q\in[0,5]$ band must be robust to inputs where the value is zero or exponentially small.

Problem Statement

Determine the approximation complexity of the Tutte polynomial of a planar graph at the rational points of the Tutte plane that remain unclassified, and settle the strength of the hardness conclusions at the real points.

Specifically, for $\mathrm{PlanarTutte}(x,y)$ — the problem of multiplicatively approximating $T(G;x,y)$ given a planar input graph $G$ — settle, for every rational point $(x,y)$ not covered by the known results, whether an FPRAS exists. The unclassified set is, by definition, the set of rational points settled neither by exact tractability (Vertigan's dichotomy: $H_1$ , $H_2$ , $(1,1)$ , $(-1,-1)$ ) nor by any known inapproximability result (the four Goldberg–Jerrum regions recalled above and the Guo–Zhang integer chromatic and flow points); it comprises, in particular:

(i) the 'white region' of the Goldberg–Jerrum planar map: the ferromagnetic region $x>1$ , $y>1$ apart from the exactly computable hyperbolas $H_1$ and $H_2$ (it contains the zero-field ferromagnetic $q$ -state Potts model with $q=(x-1)(y-1)$ , including integers $q\ge 3$ ), the strips $x>1$ , $-1<y<1$ and $-1<x<1$ , $y>1$ , the interior of the square $-1<x,y<1$ minus the exactly computable hyperbolas $H_1$ and $H_2$ and the branch of $H_3$ with $x<1$ , $y<1$ , and the axes $x=1$ with $y\neq 1$ and $y=1$ with $x\neq 1$ (spanning-forest and connected-subgraph generating functions);
(ii) the chromatic axis $(1-q,0)$ — equivalently, by planar duality, the flow axis $(0,1-q)$ — at non-integer real $q$ , in particular at every non-integer rational $q$ , which is the case the rational-point classification requires;
(iii) the points with $(x-1)(y-1)\in[0,5]$ other than those already classified as exactly tractable or inapproximable (the hyperbolas $H_1$ , $H_2$ and the branch of $H_3$ with $x<1$ , $y<1$ ), notably the part of the negative quadrant with $1<q\le 5$ , where the sign-based technique of the source paper fails because of chromatic zeros;
(iv) further rational points covered by none of the classified regions above, for instance those with $x<-1$ , $0\le y<1$ and $q=(x-1)(y-1)>5$ (such as $(-10,\tfrac12)$ , where $q=\tfrac{11}2$ ) together with their duals under $(x,y)\mapsto(y,x)$ , and boundary lines of the classified regions such as $\{x>1,\ y=-1\}$ and $\{x=-1,\ y>1\}$ .

In any case the goal is governed by the completion rule below: no rational point may be left unclassified, whether or not it appears in this list.

In addition, determine whether the established inapproximability at the real points can be strengthened from 'no FPRAS unless $\mathrm{NP}=\mathrm{RP}$ ' to #P-hardness of approximation. The source paper poses this question explicitly for the negative quadrant: it asks whether Kuperberg's proof sketch can be filled in, which would strengthen its result there by relaxing the condition $q>5$ to $q\ge 4$ and by strengthening the conclusion to #P-hardness. The same strengthening question arises naturally at the other established real hard regions — the branch of $H_3$ with $x<1$ and $y<1$ , the strips $x>1,y<-1$ and $y>1,x<-1$ , and the chromatic and flow points at integers $q\ge 4$ — as an extension beyond the source paper's explicit formulation, #P-hardness being already known to hold at the non-real points of the plane.

A complete answer is a classification: for every rational point $(x,y)$ , either a polynomial-time (randomised) approximation algorithm with the standard multiplicative guarantee, or an inapproximability result under a stated complexity assumption, with no rational point left unclassified.

References

Leslie Ann Goldberg and Mark Jerrum (2012). Inapproximability of the Tutte polynomial of a planar graph. Computational Complexity 21(4):605-642. DOI: 10.1007/s00037-012-0046-4. https://doi.org/10.1007/s00037-012-0046-4 (arXiv:0907.1724, https://arxiv.org/abs/0907.1724)
Heng Guo and Xinyuan Zhang (2026). Approximating spin systems on planar graphs. Preprint arXiv:2608.06172v2. https://arxiv.org/abs/2608.06172
Ferenc Bencs, Jeroen Huijben, and Guus Regts (2024). Approximating the chromatic polynomial is as hard as computing it exactly. Computational Complexity 33(1). DOI: 10.1007/s00037-023-00247-8. https://doi.org/10.1007/s00037-023-00247-8 (arXiv:2211.13790, https://arxiv.org/abs/2211.13790)
Andreas Galanis, Leslie Ann Goldberg, and Andrés Herrera-Poyatos (2022). The complexity of approximating the complex-valued Potts model. Computational Complexity 31(1). DOI: 10.1007/s00037-021-00218-x. https://doi.org/10.1007/s00037-021-00218-x (arXiv:2005.01076, https://arxiv.org/abs/2005.01076)
Leslie Ann Goldberg and Heng Guo (2017). The complexity of approximating complex-valued Ising and Tutte partition functions. Computational Complexity 26(4):765-833. DOI: 10.1007/s00037-017-0162-2. https://doi.org/10.1007/s00037-017-0162-2 (arXiv:1409.5627, https://arxiv.org/abs/1409.5627)
Greg Kuperberg (2015). How hard is it to approximate the Jones polynomial? Theory of Computing 11:183-219. DOI: 10.4086/toc.2015.v011a006. https://doi.org/10.4086/toc.2015.v011a006 (arXiv:0908.0512, https://arxiv.org/abs/0908.0512)
Dirk Vertigan (2005). The computational complexity of Tutte invariants for planar graphs. SIAM Journal on Computing 35(3):690-712. DOI: 10.1137/S0097539704446797. https://doi.org/10.1137/S0097539704446797
F. Jaeger, D. L. Vertigan, and D. J. A. Welsh (1990). On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society 108(1):35-53. DOI: 10.1017/S0305004100068936. https://doi.org/10.1017/S0305004100068936
Leslie Ann Goldberg and Mark Jerrum (2008). Inapproximability of the Tutte polynomial. Information and Computation 206(7):908-929. DOI: 10.1016/j.ic.2008.04.003. https://doi.org/10.1016/j.ic.2008.04.003
Leslie Ann Goldberg and Mark Jerrum (2014). The complexity of computing the sign of the Tutte polynomial. SIAM Journal on Computing 43(6):1921-1952. DOI: 10.1137/12088330X. https://doi.org/10.1137/12088330X (arXiv:1202.0313, https://arxiv.org/abs/1202.0313)
Seongmin Ok and Thomas J. Perrett (2016). Density of zeros of the Tutte polynomial. Preprint arXiv:1608.08747. https://arxiv.org/abs/1608.08747
T. Voice, M. Polukarov, and N. R. Jennings (2012). Coalition structure generation over graphs. Journal of Artificial Intelligence Research 45:165-196. DOI: 10.1613/jair.3715. https://doi.org/10.1613/jair.3715
Yoram Bachrach, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadimoghaddam (2013). Optimal coalition structure generation in cooperative graph games. Proceedings of the AAAI Conference on Artificial Intelligence 27. DOI: 10.1609/aaai.v27i1.8653. https://doi.org/10.1609/aaai.v27i1.8653
M. R. Garey, D. S. Johnson, and L. Stockmeyer (1976). Some simplified NP-complete graph problems. Theoretical Computer Science 1(3):237-267. DOI: 10.1016/0304-3975(76)90059-1. https://doi.org/10.1016/0304-3975(76)90059-1
Bill Jackson and Alan D. Sokal (2009). Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids. Journal of Combinatorial Theory, Series B 99(6):869-903. DOI: 10.1016/j.jctb.2009.03.002. https://doi.org/10.1016/j.jctb.2009.03.002
Leslie Ann Goldberg and Mark Jerrum (2012). Approximating the partition function of the ferromagnetic Potts model. Journal of the ACM 59(5):1-31. DOI: 10.1145/2371656.2371660. https://doi.org/10.1145/2371656.2371660
Zonglei Bai, Yongzhi Cao, and Hanpin Wang (2019). FPRAS for the Potts model and the number of k-colorings. Preprint arXiv:1902.09114 (withdrawn by the authors). https://arxiv.org/abs/1902.09114