An FPRAS for the four-vertex model without ARS on planar graphs

Junda LI , Zhiguo FU

Front. Comput. Sci. ›› 2027, Vol. 21 ›› Issue (8) : 2108402

PDF (292KB)
Front. Comput. Sci. ›› 2027, Vol. 21 ›› Issue (8) :2108402 DOI: 10.1007/s11704-026-51888-1
Theoretical Computer Science
LETTER
An FPRAS for the four-vertex model without ARS on planar graphs
Author information +
History +
PDF (292KB)

Graphical abstract

Cite this article

Download citation ▾
Junda LI, Zhiguo FU. An FPRAS for the four-vertex model without ARS on planar graphs. Front. Comput. Sci., 2027, 21 (8) : 2108402 DOI:10.1007/s11704-026-51888-1

登录浏览全文

4963

注册一个新账户 忘记密码

References

[1]

Liu T, Yang X . Beyond windability: approximability of the four-vertex model. Theoretical Computer Science, 2024, 995: 114491

[2]

Huang L, Lu P, Zhang C. Canonical paths for MCMC: from art to science. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms. 2016, 514−527

[3]

Cai J Y, Fu Z, Xia M . Complexity classification of the six-vertex model. Information and Computation, 2018, 259: 130–141

[4]

Dyer M, Greenhill C . On Markov chains for independent sets. Journal of Algorithms, 2000, 35( 1): 17–49

[5]

Jerrum M . Glauber dynamics for the hard-core model on bounded-degree H-free graphs. Combinatorics, Probability and Computing, 2025, 34( 6): 803–814

[6]

Chen Z, Liu K, Vigoda E. Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021, 1537−1550

[7]

Anari N, Liu K, Gharan S O. Spectral independence in high-dimensional expanders and applications to the hardcore model. In: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS). 2020, 1319−1330

[8]

Friedli S, Velenik Y. Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction. Cambridge: Cambridge University Press, 2018

[9]

Lozin V V . Bipartite graphs without a skew star. Discrete Mathematics, 2002, 257( 1): 83–100

Rights & permissions

Higher Education Press

PDF (292KB)

Supplementary files

Highlights

Supplementary materials

302

Accesses

0

Citation

Detail

Sections
Recommended

/

〈 〉