Completing the approximation-complexity classification of the six-vertex model: the white region of the disordered phase and the Tutte point $T(G;3,3)$ on planar graphs

The zero-field six-vertex (ice-type) model on a 4-regular graph $G$ assigns weights $a,b,c$ to the six ice-rule-satisfying vertex types and asks for the partition function $Z(G;a,b,c)$ over Eulerian orientations. Cai, Liu, and Lu (SODA 2019) gave a fully polynomial randomized approximation scheme (FPRAS) for all nonnegative parameters satisfying $a^2\le b^2+c^2$ , $b^2\le a^2+c^2$ , $c^2\le a^2+b^2$ (the blue region) and proved NP-hardness of approximation in the ferroelectric/antiferroelectric phases (the grey region), leaving a gap: the white region of the disordered phase, together with the finer classification on planar 4-regular graphs and, most sharply, the point $(1/2,1/2,1)$ (equivalently $(1,1,2)$ ), where computing $Z$ is equivalent to evaluating the Tutte polynomial $T(G;3,3)$ on planar graphs — the critical, self-dual point of the 4-state ferromagnetic Potts model. The approximation status of the white region and of $T(G;3,3)$ on planar graphs remains open.

Background

The six-vertex model (Pauling's ice model) is defined on a 4-regular graph $G$ (every vertex has degree 4): an arrow is placed on each edge so that at every vertex exactly two arrows point in and two point out (the ice rule); such an orientation is called an Eulerian orientation. Six local configurations are allowed at each vertex, grouped into three types with weights $a$ , $b$ , $c$ (two configurations per type), and the partition function is $Z(G;a,b,c)=\sum_{\sigma} a^{n_1(\sigma)}b^{n_2(\sigma)}c^{n_3(\sigma)}$ over all Eulerian orientations $\sigma$ , where $n_i(\sigma)$ counts vertices of type $i$ . Computing $Z$ is #P-hard for most parameters (#P is the counting analogue of NP, so #P-hardness means at least as hard as any counting problem), so the central question is approximability: an FPRAS (fully polynomial randomized approximation scheme) outputs a multiplicative $(1\pm\varepsilon)$ estimate of $Z$ in time polynomial in the input size and $1/\varepsilon$ with high probability. In statistical mechanics the model on the square lattice has three phases: a ferroelectric phase when $a>b+c$ (or symmetrically $b>a+c$ ), an antiferroelectric phase when $c>a+b$ , and a disordered phase when the three triangle inequalities $a\le b+c$ , $b\le a+c$ , $c\le a+b$ hold. On the curve $c^2=a^2+b^2$ (the free-fermion curve) the model is exactly computable by Pfaffians (determinantal signed sums, the Kasteleyn/FKT method) on planar graphs. Cai, Liu, and Lu (SODA 2019) proved: (1) an FPRAS exists on all 4-regular graphs whenever $a^2\le b^2+c^2$ , $b^2\le a^2+c^2$ , and $c^2\le a^2+b^2$ (the blue region, which contains the ice point $(1,1,1)$ and the free-fermion curve), via a rapidly mixing Markov chain for windable constraint functions (windability, due to McQuillan, is a property of the weight function that yields canonical-path mixing proofs); and (2) approximating $Z$ is NP-hard unless RP $=$ NP (RP being randomized polynomial time) in the grey region $a>b+c$ or $b>a+c$ or $c>a+b$ , coinciding with the ferroelectric/antiferroelectric phases. This leaves the white region: disordered-phase parameters with $a,b,c>0$ that violate at least one of the three quadratic inequalities — three lens-shaped regions between the cones $a=b+c$ and $a^2=b^2+c^2$ (and their symmetric images), including the phase-transition boundary $c=a+b$ . The problem has two further sharpenings. First, on planar graphs the model connects to the Tutte polynomial $T(G;x,y)$ , the universal deletion–contraction invariant of graphs: Las Vergnas (1988) proved $Z(H;1,1,2)=2\,T(G;3,3)$ whenever $H$ is the medial graph of a plane graph $G$ (the medial graph of a plane graph has one vertex for each edge of $G$ , with two such vertices adjacent when the corresponding edges are consecutive around a vertex or face of $G$ ; every 4-regular plane graph arises this way), and every plane graph is available, so approximating the six-vertex model at the red point $(1/2,1/2,1)$ (normalized $(1,1,2)$ , on the boundary $c=a+b$ ) is exactly the problem of approximating $T(G;3,3)$ on planar graphs. Via the Fortuin–Kasteleyn correspondence between the Tutte polynomial and the random-cluster/Potts model, $T(G;3,3)$ is, up to an efficiently computable prefactor, the partition function of the ferromagnetic 4-state Potts model at inverse temperature $\beta=\ln 3$ (the $q=4$ random-cluster model at edge probability $p=2/3$ , which is precisely the planar self-dual, i.e. critical, point for $q=4$ ). Approximating $T(G;3,3)$ is known to be #BIS-hard on general graphs (Goldberg–Jerrum 2012; #BIS is the benchmark problem of counting independent sets in bipartite graphs, believed intractable but resistant to NP-hardness proofs), and the planar inapproximability regions charted by Goldberg–Jerrum do not cover $(3,3)$ . Second, the NP-hardness in the grey region uses non-planar gadgets, so even the grey region's status on planar 4-regular graphs — the finer planar classification — is open. On the exact side the picture is complete: Cai–Fu–Shao (SODA 2021) classified exact computation of the six-vertex partition function for all complex parameters, discovering new planar polynomial-time cases beyond Kasteleyn's algorithm, and Cai–Fan–Shao–Tang (2026) completed the planar eight-vertex exact classification; but exact tractability does not decide approximation hardness or availability in the white region.

Problem Statement

Determine the approximation complexity of the zero-field six-vertex model partition function $Z(G;a,b,c)$ for parameters in the white region — all $a,b,c>0$ satisfying the triangle inequalities $a\le b+c$ , $b\le a+c$ , $c\le a+b$ that violate at least one of the quadratic inequalities $a^2\le b^2+c^2$ , $b^2\le a^2+c^2$ , $c^2\le a^2+b^2$ (including the phase-transition boundary $c=a+b$ ) — on 4-regular graphs: for each such parameter setting, does an FPRAS exist, is approximating $Z$ NP-hard (or #BIS-hard), or does it have intermediate status? In particular, resolve the red point $(1/2,1/2,1)$ (equivalently $(1,1,2)$ ): is there an FPRAS for $T(G;3,3)$ on planar graphs — the partition function of the ferromagnetic 4-state Potts model at its planar self-dual point — or is it hard to approximate? Finally, establish the finer approximation-complexity classification of $Z(G;a,b,c)$ restricted to planar 4-regular graphs, where the known NP-hardness reductions (which use non-planar gadgets) do not apply. The common objective is to complete the approximation-complexity classification of the six-vertex model over its nonnegative parameter space, in direct analogy with the already complete exact-computation classification. The three requested results are (i) the white-region classification on general 4-regular graphs, (ii) the finer planar classification of $Z(G;a,b,c)$ over the full parameter space on planar 4-regular graphs (covering the planar status of the grey region as well as of the white region), and (iii) the red point $(1/2,1/2,1)$ , equivalently $T(G;3,3)$ on planar graphs; (i) and (ii) each require an independent answer, whereas (iii) is a single-point special case of (ii) called out separately because it is the sharpest instance.

References

Jin-Yi Cai, Tianyu Liu, Pinyan Lu. "Approximability of the Six-Vertex Model." Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pp. 2248–2261. DOI: 10.1137/1.9781611975482.136; arXiv:1712.05880. https://arxiv.org/abs/1712.05880
Michel Las Vergnas. "On the evaluation at (3,3) of the Tutte polynomial of a graph." Journal of Combinatorial Theory, Series B 45(3):367–372, 1988. DOI: 10.1016/0095-8956(88)90079-2. https://doi.org/10.1016/0095-8956(88)90079-2
Leslie Ann Goldberg, Mark Jerrum. "Approximating the partition function of the ferromagnetic Potts model." Journal of the ACM 59(5), Article 25, pp. 1–31, 2012. DOI: 10.1145/2371656.2371660. https://doi.org/10.1145/2371656.2371660
Leslie Ann Goldberg, Mark Jerrum. "Inapproximability of the Tutte polynomial of a planar graph." Computational Complexity 21(4):605–642, 2012. DOI: 10.1007/s00037-012-0046-4; arXiv:0907.1724. https://doi.org/10.1007/s00037-012-0046-4
Zhiguo Fu, Junda Li, Xiongxin Yang. "Beyond Windability: An FPRAS for The Six-Vertex Model." arXiv:2202.02999 (2022). https://arxiv.org/abs/2202.02999
Zhiguo Fu, Tianyu Liu, Xiongxin Yang. "Approximability of the Four-Vertex Model." arXiv:2302.11336 (2023). https://arxiv.org/abs/2302.11336
Tianyu Liu, Xiongxin Yang. "Beyond windability: Approximability of the four-vertex model." Theoretical Computer Science 995:114491, 2024. DOI: 10.1016/j.tcs.2024.114491. https://doi.org/10.1016/j.tcs.2024.114491
Jin-Yi Cai, Tianyu Liu. "An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures." Proceedings of SODA 2021, pp. 1520–1534. DOI: 10.1137/1.9781611976465.92. https://doi.org/10.1137/1.9781611976465.92
Jin-Yi Cai, Zhiguo Fu, Shuai Shao. "New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification." Proceedings of SODA 2021, pp. 1535–1547. DOI: 10.1137/1.9781611976465.93. https://doi.org/10.1137/1.9781611976465.93
Jin-Yi Cai, Tianyu Liu, Pinyan Lu, Jing Yu. "Approximability of the Eight-Vertex Model." Proceedings of the 35th Computational Complexity Conference (CCC 2020), LIPIcs 169, pp. 4:1–4:18. DOI: 10.4230/LIPIcs.CCC.2020.4; arXiv:1811.03126. https://doi.org/10.4230/LIPIcs.CCC.2020.4
Jin-Yi Cai, Tianyu Liu. "Counting perfect matchings and the eight-vertex model." Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), LIPIcs 168, pp. 23:1–23:18. DOI: 10.4230/LIPIcs.ICALP.2020.23; arXiv:1904.10493. https://doi.org/10.4230/LIPIcs.ICALP.2020.23
Matthew Fahrbach, Dana Randall. "Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases." Proceedings of APPROX/RANDOM 2019, LIPIcs 145, pp. 37:1–37:20. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.37; arXiv:1904.01495. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.37
Tianyu Liu. "Torpid Mixing of Markov Chains for the Six-vertex Model on $\mathbb{Z}^2$ ." Proceedings of APPROX/RANDOM 2018, LIPIcs 116, pp. 52:1–52:15. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.52; arXiv:1809.02703. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.52
Xiaoyu Chen, Weiming Feng, Zhe Ju, Tianshun Miao, Yitong Yin, Xinyuan Zhang. "Faster Mixing of the Jerrum-Sinclair Chain." Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025), pp. 1007–1028. DOI: 10.1109/FOCS63196.2025.00053; arXiv:2504.02740. https://doi.org/10.1109/FOCS63196.2025.00053
Benjamin Wong, Sergey Bravyi, David Gosset, Yinchen Liu. "Lee-Yang tensors and Hamiltonian complexity." arXiv:2602.03605 (2026). https://arxiv.org/abs/2602.03605
Jin-Yi Cai, Austen Z. Fan, Shuai Shao, Zhuxiao Tang. "New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model." Proceedings of STOC 2026, pp. 967–978. DOI: 10.1145/3798129.3800810; arXiv:2602.11292. https://doi.org/10.1145/3798129.3800810