Document Open Access Logo

A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights

Authors Artem Govorov, Jin-Yi Cai, Martin Dyer

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.66.pdf
  • Filesize: 0.67 MB
  • 18 pages

Document Identifiers

Author Details

Artem Govorov
  • Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI, USA
Jin-Yi Cai
  • Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI, USA
Martin Dyer
  • School of Computing, University of Leeds, UK

Funding

  • Govorov, Artem: Supported by NSF CCF-1714275.
  • Cai, Jin-Yi: Supported by NSF CCF-1714275.
  • Dyer, Martin: Supported by EPSRC grant EP/S016562/1.

Cite AsGet BibTex

Artem Govorov, Jin-Yi Cai, and Martin Dyer. A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.66

Abstract

We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix A. Each symmetric matrix A defines a graph homomorphism function Z_A(⋅), also known as the partition function. Dyer and Greenhill [Martin E. Dyer and Catherine S. Greenhill, 2000] established a complexity dichotomy of Z_A(⋅) for symmetric {0, 1}-matrices A, and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [Andrei Bulatov and Martin Grohe, 2005] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices A. However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric A, either Z_A(G) is in polynomial time for all graphs G, or it is #P-hard for bounded degree (and simple) graphs G. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [Leslie A. Goldberg et al., 2010] for Z_A(⋅) also holds for simple graphs, where A is any real symmetric matrix.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Graph homomorphism
  • Complexity dichotomy
  • Counting problems

Metrics

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

Related Versions

References

  1. Alexander I. Barvinok. Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and combinatorics. Springer, 2017. Google Scholar
  2. Alexander I. Barvinok and Pablo Soberón. Computing the partition function for graph homomorphisms. Combinatorica, 37(4):633-650, 2017. Google Scholar
  3. Rodney J. Baxter. The six and eight-vertex models revisited. Journal of Statistical Physics, 116(1):43-66, 2004. Google Scholar
  4. Andrei Bulatov and Martin Grohe. The complexity of partition functions. Theoretical Computer Science, 348(2-3):148-186, 2005. Google Scholar
  5. Jin-Yi Cai and Xi Chen. Complexity Dichotomies for Counting Problems, volume 1: Boolean Domain. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781107477063.
  6. Jin-Yi Cai and Xi Chen. A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. Computational Complexity, 28(3):345-408, 2019. Google Scholar
  7. Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem. SIAM Journal on Computing, 42(3):924-1029, 2013. Google Scholar
  8. Martin E. Dyer, Alan M. Frieze, and Mark Jerrum. On counting independent sets in sparse graphs. SIAM Journal on Computing, 31(5):1527-1541, 2002. Google Scholar
  9. Martin E. Dyer, Leslie A. Goldberg, and Mike Paterson. On counting homomorphisms to directed acyclic graphs. Journal of the ACM, 54(6):27, 2007. Google Scholar
  10. Martin E. Dyer and Catherine S. Greenhill. The complexity of counting graph homomorphisms. Random Structures and Algorithms, 17(3-4):260-289, 2000. Google Scholar
  11. Martin E. Dyer and Catherine S. Greenhill. Corrigendum: The complexity of counting graph homomorphisms. Random Structures and Algorithms, 25(3):346-352, 2004. Google Scholar
  12. Leslie A. Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs. SIAM Journal on Computing, 39(7):3336-3402, 2010. Google Scholar
  13. Martin Grohe and Marc Thurley. Counting homomorphisms and partition functions. In Model Theoretic Methods in Finite Combinatorics, volume 558 of Contemporary Mathematics, pages 243-292. American Mathematical Society, 2011. Google Scholar
  14. Pavol Hell and Jaroslav Nešetřil. Graphs and homomorphisms, volume 28 of Oxford lecture series in mathematics and its applications. Oxford University Press, 2004. Google Scholar
  15. Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic Pirogov-Sinai theory. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1009-1020, 2019. Google Scholar
  16. Hendrik W. Lenstra Jr. Algorithms in algebraic number theory. Bulletin of the American Mathematical Society, 26(2):211-244, 1992. Google Scholar
  17. Liang Li, Pinyan Lu, and Yitong Yin. Correlation decay up to uniqueness in spin systems. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 67-84, 2013. Google Scholar
  18. László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321-328, 1967. Google Scholar
  19. Han Peters and Guus Regts. Location of zeros for the partition function of the Ising model on bounded degree graphs. arXiv preprint, 2018. URL: https://arxiv.org/abs/1810.01699.
  20. Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 941-953, 2012. Google Scholar
  21. Allan Sly. Computational transition at the uniqueness threshold. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 287-296, 2010. Google Scholar
  22. Marc Thurley. The Complexity of Partition Functions. PhD thesis, Humboldt Universität zu Berlin, 2009. Google Scholar
  23. Marc Thurley. The complexity of partition functions on Hermitian matrices. arXiv preprint, 2010. URL: https://arxiv.org/abs/1004.0992.
  24. Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410-421, 1979. Google Scholar
  25. Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the 38th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 140-149, 2006. Google Scholar
  26. Mingji Xia. Holographic reduction: A domain changed application and its partial converse theorems. International Journal of Software and Informatics, 5(4):567-577, 2011. Google Scholar
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