Approximation complexity of the six-vertex model in the white region and on planar graphs

Cai, Liu and Lu (SODA 2019) initiated the classification of the approximation complexity of the zero-field six-vertex model partition function $Z(G;a,b,c)$ — a weighted sum over Eulerian orientations of a 4-regular graph $G$ with nonnegative vertex weights $(a,b,c)$. They proved that an FPRAS exists in the conic region $a^2≤b^2+c^2$, $b^2≤a^2+c^2$, $c^2≤a^2+b^2$, and that no FPRAS exists (unless RP $=$ NP) in the ordered ferroelectric/antiferroelectric region where one weight strictly exceeds the sum of the other two. The open problem is the remaining white region — parameters satisfying the triangle inequalities weakly but violating at least one quadratic inequality, including the phase-transition boundary lines such as $c=a+b$ — together with the finer classification on planar 4-regular graphs. The standout planar instance is the point $(1/2,1/2,1)$ (equivalently $(1,1,2)$), which by a theorem of Las Vergnas is equivalent to approximating the Tutte polynomial $T(G;3,3)$ on planar graphs — a problem known to be #BIS-hard on general graphs and tied to the open problem of approximating the ferromagnetic Potts model for $q≥3$. Follow-up work through 2026 (eight-vertex extensions, degenerate sub-model FPRAS results, exact-complexity classifications) leaves the white region and the planar boundary lines, including the $T(G;3,3)$ point, unresolved.

Background

The six-vertex model is a classical statistical-mechanical system introduced in the 1930s to model ice and famously solved in the infinite-lattice limit on the square lattice in the 1960s. In its graph-theoretic form the model lives on a 4-regular graph $G$: every edge carries an arrow, and at each vertex exactly two arrows point in and two point out (the ice rule). Such arrow configurations are precisely the Eulerian orientations of $G$ — orientations whose in-degree equals their out-degree (here 2) at every vertex — and there are six allowed local patterns around a vertex. Under arrow-reversal symmetry (the zero-field convention of classical physics), the six patterns receive weights $a,a,b,b,c,c$, and the partition function is $Z(G;a,b,c)=Σ_τ a^{n1+n2} b^{n3+n4} c^{n5+n6}$, where the sum ranges over Eulerian orientations $τ$ and $n_i$ counts the vertices of local type $i$ in $τ$. At $a=b=c=1$ the partition function simply counts Eulerian orientations.

The algorithmic questions are whether $Z(G;a,b,c)$ can be computed exactly, or approximated, in polynomial time. A fully polynomial randomized approximation scheme (FPRAS) is a randomized algorithm that, given $G$ and $ε>0$, runs in time polynomial in the input size and $1/ε$ and outputs an estimate within a multiplicative factor $1±ε$ of the true value with probability at least $3/4$. Exactly, the model is #P-hard (the counting-problem analogue of NP-hardness) except at degenerate points (two of $a,b,c$ zero, or one zero and the other two equal), and on planar graphs it becomes polynomial-time computable on the free-fermion curve $c^2=a^2+b^2$, where it reduces, by the Pfaffian method (Kasteleyn's technique of expressing perfect-matching counts as determinants of signed adjacency matrices), to counting perfect matchings. For approximation, before 2019 only the unweighted point $(1,1,1)$ was settled: Mihail and Winkler gave an FPRAS for counting Eulerian orientations.

Cai, Liu and Lu (SODA 2019) initiated the classification of the approximation complexity over the whole parameter space, and their results track the physics phase diagram. In the thermodynamic limit on the square lattice the model has three phases: ferroelectric when $a>b+c$ or $b>a+c$, antiferroelectric when $c>a+b$, and disordered when all three triangle inequalities $a≤b+c$, $b≤a+c$, $c≤a+b$ hold. They proved that there is an FPRAS whenever all three quadratic inequalities $a^2≤b^2+c^2$, $b^2≤a^2+c^2$, $c^2≤a^2+b^2$ hold (the blue region, a closed cone containing $(1,1,1)$), and that no FPRAS exists in the ordered region where one weight strictly exceeds the sum of the other two, unless RP $=$ NP (RP being the one-sided-error randomized analogue of P). The approximation complexity in the remaining white region — nonnegative parameters that satisfy the triangle inequalities weakly but violate at least one quadratic inequality, including the phase-transition boundary lines such as $c=a+b$ (the yellow line) — is left open, as is a finer classification on planar graphs. The blue-region FPRAS rests on windability, a criterion under which canonical-path arguments in the style of the classical perfect-matching Markov chain apply; this framework exhausts itself at the boundary of the cone.

The standout open instance on planar graphs connects to the Tutte polynomial $T(G;x,y)$, the fundamental two-variable graph polynomial that specializes to the chromatic and flow polynomials. Las Vergnas proved that for a plane graph $G$ with medial graph $H$ — the plane graph whose vertices correspond to edges of $G$, two being adjacent when the corresponding edges are consecutive along a face boundary — one has $Z(H;1,1,2)=2T(G;3,3)$, and every 4-regular plane graph is the medial graph of some plane graph. Hence approximating the six-vertex model at $(1/2,1/2,1)$ (the same parameter point as $(1,1,2)$, since rescaling all weights by $t$ multiplies $Z$ by $t$ to the power $|V|$) on planar graphs is exactly the problem of approximating $T(G;3,3)$ on planar graphs. Approximating $T(G;3,3)$ is known to be #BIS-hard on general graphs — #BIS, the problem of counting independent sets in a bipartite graph, being the canonical problem of conjecturally intermediate approximation complexity — while the known no-FPRAS regions for the Tutte polynomial on planar graphs do not cover the point $(3,3)$. Under the standard random-cluster specialization $q=(x−1)(y−1)$, $v=y−1$, the point $(3,3)$ is the ferromagnetic random-cluster (Potts) point $q=4$, $v=2$, so this instance sits inside the well-known open problem of approximating the ferromagnetic Potts model for $q≥3$, of which only the $q=2$ Ising case is settled in general.

Problem Statement

Determine the approximation complexity of the zero-field six-vertex model partition function $Z(G;a,b,c)$ with nonnegative weights on 4-regular graphs, completing the classification initiated by Cai, Liu and Lu (SODA 2019).

1. General graphs. For every parameter triple in the white region — the set of nonnegative $(a,b,c)$ satisfying $a≤b+c$, $b≤a+c$, $c≤a+b$ in which at least one of $a^2>b^2+c^2$, $b^2>a^2+c^2$, $c^2>a^2+b^2$ holds (the disordered phase outside the closed quadratic cone, including the phase-transition boundary lines such as $c=a+b$) — determine whether $Z(G;a,b,c)$ admits an FPRAS on general 4-regular graphs, or is hard to approximate at that point (for example NP-hard to approximate unless RP $=$ NP, or #BIS-hard).

2. Planar graphs. Complete the finer classification on planar 4-regular graphs: for the white region and for the ordered-phase regions where only general-graph hardness is known, determine whether approximation becomes tractable on planar graphs. The general planar classification is required; the point $(1/2,1/2,1)$ is its central required instance, not a substitute for the classification. In particular, settle the approximability at the point $(1/2,1/2,1)$ (equivalently $(1,1,2)$, on the boundary line $c=a+b$), which by Las Vergnas's identity $Z(H;1,1,2)=2T(G;3,3)$ for the medial graph $H$ of a plane graph $G$ is the same as approximating the Tutte polynomial $T(G;3,3)$ on planar graphs.

The two facets share one objective: completing the approximation-complexity classification of the model — deciding, for every nonnegative parameter point beyond the exactly computable degenerate points and the planar free-fermion curve $c^2=a^2+b^2$, whether $Z$ admits an FPRAS or is inapproximable — consistently with the established results: FPRAS on the closed cone; inapproximability on the ordered phases for general graphs unless RP $=$ NP; exact polynomial-time computation at the degenerate points and on the planar free-fermion curve; and the FPRAS that Cai and Liu (2020) subsequently obtained for a subregion of the $c$-dominant ordered phase on planar graphs via weight-preserving holographic maps.

References

1. Jin-Yi Cai, Tianyu Liu, Pinyan Lu. Approximability of the Six-Vertex Model. Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), SIAM, pp. 2248–2261, 2019. DOI: 10.1137/1.9781611975482.136; arXiv:1712.05880. https://arxiv.org/abs/1712.05880
2. 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 vol. 169, Article 4. DOI: 10.4230/LIPIcs.CCC.2020.4; arXiv:1811.03126. https://arxiv.org/abs/1811.03126
3. 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, Article 23. DOI: 10.4230/LIPIcs.ICALP.2020.23; arXiv:1904.10493. https://arxiv.org/abs/1904.10493
4. Jin-Yi Cai, Tianyu Liu. FPRAS via MCMC where it mixes torpidly (and very little effort). arXiv:2010.05425, 2020. https://arxiv.org/abs/2010.05425
5. 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
6. Zhiguo Fu, Tianyu Liu, Xiongxin Yang. Approximability of the Four-Vertex Model. arXiv:2302.11336, 2023. https://arxiv.org/abs/2302.11336
7. Boning Meng, Juqiu Wang, Mingji Xia. P-time Algorithms for Typical #EO Problems. arXiv:2410.11557, 2024. https://arxiv.org/abs/2410.11557
8. Austen Fan, Jin-Yi Cai, Shuai Shao, Zhuxiao Tang. New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model. arXiv:2602.11292, 2026. https://arxiv.org/abs/2602.11292
9. 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://arxiv.org/abs/0907.1724
10. Leslie Ann Goldberg, Mark Jerrum. Approximating the partition function of the ferromagnetic Potts model. Journal of the ACM 59(5), Article 25, 2012. DOI: 10.1145/2371656.2371660; arXiv:1002.0986. https://arxiv.org/abs/1002.0986
11. 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
12. M. Mihail, P. Winkler. On the number of Eulerian orientations of a graph. Algorithmica 16(4):402–414, 1996. DOI: 10.1007/s004539900057. https://doi.org/10.1007/s004539900057
13. Matthew Fahrbach, Dana Randall. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases. Proceedings of APPROX/RANDOM 2019, LIPIcs vol. 145, Article 37, 2019. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.37; arXiv:1904.01495. https://arxiv.org/abs/1904.01495
14. Tianyu Liu. Torpid Mixing of Markov Chains for the Six-Vertex Model on Z^2. Proceedings of APPROX/RANDOM 2018, LIPIcs, Article 52. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.52; arXiv:1809.02703. https://arxiv.org/abs/1809.02703
15. Jin-Yi Cai, Zhiguo Fu, Shuai Shao. New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification. arXiv:1704.01657, 2017 (extended abstract in SODA 2021). https://arxiv.org/abs/1704.01657
16. Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali. Efficient sampling and counting algorithms for the Potts model on $\mathbb{Z}^d$ at all temperatures. Random Structures & Algorithms 63(1):130–170, 2023. DOI: 10.1002/rsa.21131; arXiv:1909.09298. https://arxiv.org/abs/1909.09298