Extending the FPRAS for the six-vertex model with an unwindable constraint function beyond two-by-two-intersection-free circuit decompositions and the $b\le 1/\delta$ regime

Fu, Li and Yang (arXiv:2202.02999, 2022) gave the first fully polynomial randomized approximation scheme (FPRAS) for the partition function of a six-vertex model whose constraint function is unwindable, using a Glauber dynamics on a circuit decomposition of the underlying graph. Their rapid-mixing proof, and hence the FPRAS, holds only under two restrictions: the circuit decomposition must be two-by-two-intersection free (no three circuits of the decomposition pairwise intersect), a condition the authors explicitly leave unresolved, stating they believe it unnecessary, and the vertex weight must satisfy $b\le 1/\delta$ , where $\delta$ is the maximum number of circuits intersecting any single circuit. No subsequent work has removed either restriction; the authors' own follow-up addresses the more special four-vertex model instead. Determining whether an FPRAS exists for this six-vertex model on unrestricted underlying graphs and for $b>1/\delta$ is the open problem.

Background

The six-vertex model, introduced by Pauling in 1935 to describe ice, lives on a 4-regular graph $G$ : each vertex is incident to four edges, and a valid configuration is an orientation of the edges in which every vertex has exactly two edges directed in and two directed out (an Eulerian orientation). At each vertex there are six possible local in/out patterns, weighted $w_1,\dots,w_6$ (types 1 and 2 get weight $w_1,w_2$ ; types 3 and 4 get $w_3,w_4$ ; types 5 and 6 get $w_5,w_6$ ), and the partition function $Z$ sums the products of vertex weights over all valid configurations. Computing $Z$ exactly is #P-hard in most regimes, so one asks for an FPRAS — a randomized algorithm that outputs a $(1\pm\varepsilon)$ -multiplicative estimate of $Z$ with probability at least $3/4$ in time polynomial in the instance size and $1/\varepsilon$ . Writing the model as a Holant problem (a sum over edge assignments of products of vertex-local constraint functions) reveals a key structural property: windability, introduced by McQuillan, which guarantees a system of canonical paths for Markov chain Monte Carlo (MCMC) sampling. Mihail and Winkler gave an early FPRAS for Eulerian orientations (the ice model, all weights equal), and Cai, Liu and Lu gave an MCMC-based FPRAS for the six-vertex model precisely for parameter settings whose constraint function is windable — a region inside the disordered phase for arrow-reversal-symmetric weights — together with NP-hardness of approximation on the antiferroelectric side of the phase transition. Windability was therefore the boundary of all known FPRAS results for the model.

Fu, Li and Yang crossed this boundary for one specific unwindable constraint function $f^*$ with weights $w_1=1$ , $w_3=w_4=b>0$ , and $w_2=w_5=w_6=0$ (a degenerate, non-arrow-symmetric setting whose exact computation is #P-hard by Cai–Fu–Xia). Their algorithm is a Glauber dynamics — a single-site heat-bath Markov chain — defined on a circuit decomposition of the underlying graph: pair the four half-edges at each degree-4 vertex into two pairs $(x_1,x_3)$ and $(x_2,x_4)$ and trace circuits that pass straight through vertices along paired half-edges, obtaining a set $\mathcal C$ of circuits. The constraint $f^*$ forces the edge values along each circuit to alternate, so a valid configuration is determined by a 0/1 value on each circuit, and two circuits sharing a vertex cannot both take the value 1. Writing $\Gamma(C_i)$ for the set of circuits sharing a vertex with $C_i$ , $\delta_{C_i}=|\Gamma(C_i)|$ , $\delta=\max_i\delta_{C_i}\ge 2$ and $n=|\mathcal C|$ , the chain updates one circuit at a time, and its stationary distribution is proportional to the six-vertex measure. The authors prove rapid mixing by path coupling (the Bubley–Dyer technique, which deduces the mixing time $\tau(\varepsilon)$ of the chain from the one-step contraction of a well-chosen metric on pairs of states) with a potential function $\Phi(\sigma,\sigma_{C_i})=\delta_{C_i}-w\lvert B(\sigma,C_i)\rvert$ , where $B$ is the set of blocked neighbouring circuits and $w=\frac{b\delta}{b^{\delta}+2}$ (the authors note that $w<1$ when $b\le 1/\delta$ , which since $\delta\ge2$ forces $b\le 1/2$ ); their one-step estimate gives $E[\Delta\Phi]=\frac{\delta_{C_i}}{1+b^{\delta}}\,(b\delta-1-b^{\delta})$ , which is nonpositive under the same condition $b\le 1/\delta$ . The resulting mixing time is $O\big(\tfrac{n(1+b^{\delta})}{b^{\delta}+1-b\delta}\log(n\delta/\varepsilon)\big)$ , which yields the FPRAS via the standard MCMC counting reduction. The proof, however, is established only when the circuit decomposition is two-by-two-intersection free — no three circuits of $\mathcal C$ pairwise intersect — a condition the authors impose 'for some technical difficulties' and explicitly state they believe to be unnecessary. Whether local chains can work at all in wider six-vertex regimes is a genuine question: on $\mathbb Z^2$ , Glauber dynamics and the directed-loop algorithm mix torpidly in the ferroelectric and antiferroelectric phases (Liu), and Glauber dynamics requires exponential time in the ordered phases for suitable boundary conditions (Fahrbach–Randall), so rapid mixing beyond the proven regime is not automatic.

Problem Statement

The Fu–Li–Yang theorem proves rapid mixing of the circuit Glauber dynamics — mixing time $O\big(\tfrac{n(1+b^{\delta})}{b^{\delta}+1-b\delta}\log\tfrac{n\delta}{\varepsilon}\big)$ , and hence an FPRAS for the partition function of the six-vertex model with constraint function $f^*$ ( $w_1=1$ , $w_3=w_4=b>0$ , $w_2=w_5=w_6=0$ ) — only under two restrictions: the two-by-two-intersection-free circuit decomposition, which the authors explicitly leave unresolved, and the parameter bound $b\le 1/\delta$ . The open problem is to remove them:

Structural restriction. Prove rapid mixing of this chain (or of another chain with the same stationary distribution) on arbitrary underlying graphs of the model — any graph on which the six-vertex configuration space is defined — dropping only the assumption that the circuit decomposition is two-by-two-intersection free, i.e. handling graphs whose decomposition contains three circuits that pairwise intersect. The authors state they believe this condition is unnecessary.
Parameter restriction. Extend the rapid-mixing result, and hence the FPRAS, beyond $b\le 1/\delta$ , where $\delta=\max_{C_i\in\mathcal C}\lvert\Gamma(C_i)\rvert\ge 2$ is the maximum number of circuits intersecting any one circuit (the proven regime already forces $b\le 1/2$ ); the ideal target is all $b>0$ .

The question is settled by a rigorous proof of polynomial mixing time — or by any other FPRAS construction — whose stated applicability covers instances excluded above (graphs violating the structural condition, or parameter values with $b>1/\delta$ ), together with the derivation of the approximation guarantee; it is likewise settled by a proof that no such FPRAS exists (for instance an approximation-hardness or non-mixing result) for the corresponding instances. A complete answer addresses both restrictions; a precise answer to either one alone, with the other explicitly left open, is a well-defined partial resolution.

References

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, Pinyan Lu. Approximability of the Six-vertex Model. In Proceedings of SODA 2019, pp. 2248–2261; arXiv:1712.05880 (2017/2019). doi:10.1137/1.9781611975482.136. https://arxiv.org/abs/1712.05880
Jin-Yi Cai, Zhiguo Fu, Mingji Xia. Complexity classification of the six-vertex model. Information and Computation 259:130–141 (2018). doi:10.1016/j.ic.2018.01.003. https://doi.org/10.1016/j.ic.2018.01.003
Colin McQuillan. Approximating Holant problems by winding. arXiv:1301.2880 (2013). https://arxiv.org/abs/1301.2880
Milena Mihail, Peter Winkler. On the number of Eulerian orientations of a graph. Algorithmica 16:402–414 (1996). doi:10.1007/BF01940872. https://doi.org/10.1007/BF01940872
Tianyu Liu. Torpid Mixing of Markov Chains for the Six-vertex Model on $\mathbb{Z}^2$ . arXiv:1809.02703 (2018). https://arxiv.org/abs/1809.02703
Matthew Fahrbach, Dana Randall. Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases. arXiv:1904.01495 (2019). https://arxiv.org/abs/1904.01495
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
Jincheng Guan, Shuai Shao, Ke Shi. An LP Algorithm for Counting Eulerian Orientations Through the Lens of Quasi-polymorphism. arXiv:2607.27961 (2026). https://arxiv.org/abs/2607.27961