Document Open Access Logo

Counting Perfect Matchings and the Eight-Vertex Model

Authors Jin-Yi Cai, Tianyu Liu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.23.pdf
  • Filesize: 1.12 MB
  • 18 pages

Document Identifiers

Author Details

Jin-Yi Cai
  • University of Wisconsin-Madison, Madison, WI, USA
Tianyu Liu
  • University of Wisconsin-Madison, Madison, WI, USA

Funding

Supported by NSF CCF-1714275.

Cite AsGet BibTex

Jin-Yi Cai and Tianyu Liu. Counting Perfect Matchings and the Eight-Vertex Model. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.23

Abstract

We study the approximation complexity of the partition function of the eight-vertex model on general 4-regular graphs. For the first time, we relate the approximability of the eight-vertex model to the complexity of approximately counting perfect matchings, a central open problem in this field. Our results extend those in [Jin-Yi Cai et al., 2018]. In a region of the parameter space where no previous approximation complexity was known, we show that approximating the partition function is at least as hard as approximately counting perfect matchings via approximation-preserving reductions. In another region of the parameter space which is larger than the region that is previously known to admit Fully Polynomial Randomized Approximation Scheme (FPRAS), we show that computing the partition function can be reduced to counting perfect matchings (which is valid for both exact and approximate counting). Moreover, we give a complete characterization of nonnegatively weighted (not necessarily planar) 4-ary matchgates, which has been open for several years. The key ingredient of our proof is a geometric lemma. We also identify a region of the parameter space where approximating the partition function on planar 4-regular graphs is feasible but on general 4-regular graphs is equivalent to approximately counting perfect matchings. To our best knowledge, these are the first problems that exhibit this dichotomic behavior between the planar and the nonplanar settings in approximate counting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Approximate complexity
  • the eight-vertex model
  • counting perfect matchings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. R. J. Baxter. Eight-vertex model in lattice statistics. Phys. Rev. Lett., 26:832-833, April 1971. URL: https://doi.org/10.1103/PhysRevLett.26.832.
  2. R. J. Baxter. Partition function of the eight-vertex lattice model. Annals of Physics, 70(1):193-228, 1972. URL: https://doi.org/10.1016/0003-4916(72)90335-1.
  3. R. J. Baxter. Exactly Solved Models in Statistical Mechanics. Academic Press Inc., San Diego, CA, USA, 1982. Google Scholar
  4. Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, and Stanislav Živný. Functional clones and expressibility of partition functions. Theoretical Computer Science, 687:11-39, 2017. URL: https://doi.org/10.1016/j.tcs.2017.05.001.
  5. Jin-Yi Cai and Xi Chen. Complexity Dichotomies for Counting Problems, volume 1. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781107477063.
  6. Jin-Yi Cai and Zhiguo Fu. Complexity classification of the eight-vertex model. CoRR, abs/1702.07938, 2017. URL: http://arxiv.org/abs/1702.07938.
  7. Jin-Yi Cai, Tianyu Liu, and Pinyan Lu. Approximability of the six-vertex model. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 2248-2261, 2019. URL: https://doi.org/10.1137/1.9781611975482.136.
  8. Jin-Yi Cai, Tianyu Liu, Pinyan Lu, and Jing Yu. Approximability of the eight-vertex model. CoRR, abs/1811.03126, 2018. URL: http://arxiv.org/abs/1811.03126.
  9. Chungpeng Fan and F. Y. Wu. General lattice model of phase transitions. Phys. Rev. B, 2:723-733, August 1970. URL: https://doi.org/10.1103/PhysRevB.2.723.
  10. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. J. ACM, 62(6), December 2015. URL: https://doi.org/10.1145/2785964.
  11. Leslie Ann Goldberg and Mark Jerrum. Inapproximability of the Tutte polynomial. Information and Computation, 206(7):908-929, 2008. URL: https://doi.org/10.1016/j.ic.2008.04.003.
  12. Sam Greenberg and Dana Randall. Slow mixing of Markov chains using fault lines and fat contours. Algorithmica, 58(4):911-927, December 2010. URL: https://doi.org/10.1007/s00453-008-9246-3.
  13. Thomas P. Hayes, Juan C. Vera, and Eric Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree. Random Structures & Algorithms, 47(4):731-759, 2015. URL: https://doi.org/10.1002/rsa.20560.
  14. Richard M. Karp and Michael Luby. Monte-Carlo algorithms for enumeration and reliability problems. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science, SFCS '83, pages 56-64, Washington, DC, USA, 1983. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.1983.35.
  15. P.W. Kasteleyn. The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. Physica, 27(12):1209-1225, 1961. URL: https://doi.org/10.1016/0031-8914(61)90063-5.
  16. P.W. Kasteleyn. Graph theory and crystal physics. In F. Harary, editor, Graph Theory and Theoretical Physics, pages 43-110. Academic Press, 1967. Google Scholar
  17. Tianyu Liu. Torpid mixing of Markov chains for the six-vertex model on ℤ². In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, pages 52:1-52:15, 2018. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.52.
  18. Colin McQuillan. Approximating Holant problems by winding. CoRR, abs/1301.2880, 2013. URL: http://arxiv.org/abs/1301.2880.
  19. Bill Sutherland. Two dimensional hydrogen bonded crystals without the ice rule. Journal of Mathematical Physics, 11(11):3183-3186, 1970. URL: https://doi.org/10.1063/1.1665111.
  20. H. N. V. Temperley and Michael E. Fisher. Dimer problem in statistical mechanics-an exact result. The Philosophical Magazine: A Journal of Theoretical Experimental and Applied Physics, 6(68):1061-1063, 1961. URL: https://doi.org/10.1080/14786436108243366.
  21. Leslie Valiant. Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 31(4):1229-1254, 2002. URL: https://doi.org/10.1137/S0097539700377025.
  22. Leslie G. Valiant. Holographic algorithms. SIAM J. Comput., 37(5):1565-1594, February 2008. URL: https://doi.org/10.1137/070682575.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact