Document Open Access Logo

Bounded Degree Nonnegative Counting CSP

Authors Jin-Yi Cai, Daniel P. Szabo

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2022.27.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Computational Counting Complexity
  • Constraint Satisfaction Problems
  • Counting CSPs
  • Complexity Dichotomy
  • Nonnegative Counting CSP
  • Graph Homomorphisms

Metrics

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

Abstract

Constraint satisfaction problems (CSP) encompass an enormous variety of computational problems. In particular, all partition functions from statistical physics, such as spin systems, are special cases of counting CSP (#CSP). We prove a complete complexity classification for every counting problem in #CSP with nonnegative valued constraint functions that is valid when every variable occurs a bounded number of times in all constraints. We show that, depending on the set of constraint functions ℱ, every problem in the complexity class #CSP(ℱ) defined by ℱ is either polynomial time computable for all instances without the bounded occurrence restriction, or is #P-hard even when restricted to bounded degree input instances. The constant bound in the degree depends on ℱ. The dichotomy criterion on ℱ is decidable. As a second contribution, we prove a slightly modified but more streamlined decision procedure (from [Jin-Yi Cai et al., 2011]) for tractability. This enables us to fully classify a family of directed weighted graph homomorphism problems. This family contains both P-time tractable problems and #P-hard problems. To our best knowledge, this is the first family of such problems explicitly classified that are not acyclic, thereby the Lovász-goodness criterion of Dyer-Goldberg-Paterson [Martin E. Dyer et al., 2006] cannot be applied.

Cite As Get BibTex

Jin-Yi Cai and Daniel P. Szabo. Bounded Degree Nonnegative Counting CSP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.27

Author Details

Jin-Yi Cai
  • Department of Computer Sciences, University of Wisconsin-Madison, WI, USA
Daniel P. Szabo
  • Department of Computer Sciences, University of Wisconsin-Madison, WI, USA

Funding

  • Cai, Jin-Yi: Supported by NSF CCF-1714275.
  • Szabo, Daniel P.: Supported by an REU supplement of NSF CCF-1714275.

Acknowledgements

The authors thank the three anonymous reviewers for their valuable comments and suggestions.

References

  1. Carlo Baldassi, C. Borgs, J. Chayes, A. Ingrosso, Carlo Lucibello, Luca Saglietti, and R. Zecchina. Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes. Proceedings of the National Academy of Sciences, 113:E7655-E7662, 2016. Google Scholar
  2. Alexander Barvinok. Combinatorics and Complexity of Partition Functions, volume 30. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-51829-9.
  3. Rodney J Baxter. Exactly solved models in statistical mechanics. Elsevier, 2016. Google Scholar
  4. Christian Borgs, Jennifer Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi. Counting graph homomorphisms. In Topics in discrete mathematics, pages 315-371. Springer, 2006. Google Scholar
  5. A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: an algorithm for satisfiability. Random Struct. Algorithms, 27:201-226, 2005. Google Scholar
  6. Graham R. Brightwell and Peter Winkler. Graph homomorphisms and phase transitions. Journal of Combinatorial Theory, Series B, 77(2):221-262, 1999. URL: https://doi.org/10.1006/jctb.1999.1899.
  7. Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, and David Richerby. The complexity of weighted and unweighted #CSP. Journal of Computer and System Sciences, 78(2):681-688, 2012. Games in Verification. URL: https://doi.org/10.1016/j.jcss.2011.12.002.
  8. Andrei Bulatov and Martin Grohe. The complexity of partition functions. Theoretical Computer Science, 348(2):148-186, 2005. Automata, Languages and Programming: Algorithms and Complexity (ICALP-A 2004). URL: https://doi.org/10.1016/j.tcs.2005.09.011.
  9. Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, volume 5125 of Lecture Notes in Computer Science, pages 646-661. Springer, 2008. Also in J. ACM 60.5 (October 2013). URL: https://doi.org/10.1007/978-3-540-70575-8_53.
  10. Andrei A. Bulatov and Víctor Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem. Information and Computation, 205(5):651-678, 2007. URL: https://doi.org/10.1016/j.ic.2006.09.005.
  11. Robert Burton and Jeffrey E. Steif. Non-uniqueness of measures of maximal entropy for subshifts of finite type. Ergodic Theory and Dynamical Systems, 14(2):213-235, 1994. URL: https://doi.org/10.1017/S0143385700007859.
  12. Jin-Yi Cai and Xi Chen. A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 437-446. IEEE Computer Society, 2010. Also in Comput. Complex. 28.3 (2019). URL: https://doi.org/10.1109/FOCS.2010.49.
  13. Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 909-920. ACM, 2012. Also in J. ACM 64.3 (2017). URL: https://doi.org/10.1145/2213977.2214059.
  14. Jin-Yi Cai and Xi Chen. Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain. Cambridge University Press, 2017. Google Scholar
  15. Jin-Yi Cai, Xi Chen, and Pinyan Lu. Non-negatively weighted #CSP: An effective complexity dichotomy. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 45-54. IEEE Computer Society, 2011. Also in SIAM J. Comput. 45.6 (2016). URL: https://doi.org/10.1109/CCC.2011.32.
  16. Jin-Yi Cai and Artem Govorov. Dichotomy for graph homomorphisms with complex values on bounded degree graphs. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1103-1111. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00106.
  17. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted boolean #CSP. J. Comput. Syst. Sci., 80(1):217-236, 2014. URL: https://doi.org/10.1016/j.jcss.2013.07.003.
  18. Nadia Creignou and Miki Hermann. Complexity of generalized satisfiability counting problems. Information and computation, 125(1):1-12, 1996. Google Scholar
  19. Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems. Society for Industrial and Applied Mathematics, 2001. URL: https://doi.org/10.1137/1.9780898718546.
  20. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM Journal on Computing, 39(3):843-873, 2009. URL: https://doi.org/10.1137/07068062X.
  21. Martin Dyer and Catherine Greenhill. The complexity of counting graph homomorphisms. Random Structures & Algorithms, 17(3‐4):260-289, 2000. URL: https://doi.org/10.1002/1098-2418(200010/12)17:3/4<260::AID-RSA5>3.0.CO;2-W.
  22. Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing, 42(3):1245-1274, 2013. URL: https://doi.org/10.1137/100811258.
  23. Martin E. Dyer, Alan M. Frieze, and Mark Jerrum. On counting independent sets in sparse graphs. SIAM J. Comput., 31(5):1527-1541, 2002. URL: https://doi.org/10.1137/S0097539701383844.
  24. Martin E. Dyer, Leslie Ann Goldberg, and Mike Paterson. On counting homomorphisms to directed acyclic graphs. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, volume 4051 of Lecture Notes in Computer Science, pages 38-49. Springer, 2006. Also in J. ACM 54.6 (December 2007). URL: https://doi.org/10.1007/11786986_5.
  25. Leslie Ann Goldberg and Mark Jerrum. A complexity classification of spin systems with an external field. Proceedings of the National Academy of Sciences, 112(43):13161-13166, 2015. URL: https://doi.org/10.1073/pnas.1505664112.
  26. Artem Govorov, Jin-Yi Cai, and Martin E. Dyer. A dichotomy for bounded degree graph homomorphisms with nonnegative weights. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 66:1-66:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.66.
  27. P. Hell and J. Nesetril. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications. OUP Oxford, 2004. URL: https://books.google.com/books?id=bJXWV-qK7kYC.
  28. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, July 2001. URL: https://doi.org/10.1145/502090.502098.
  29. A. Ihler and David A. McAllester. Particle belief propagation. In AISTATS, 2009. Google Scholar
  30. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX‐-CUT and other 2‐-variable CSPs? SIAM Journal on Computing, 37(1):319-357, 2007. URL: https://doi.org/10.1137/S0097539705447372.
  31. J. L. Lebowitz and G. Gallavotti. Phase transitions in binary lattice gases. Journal of Mathematical Physics, 12(7):1129-1133, 1971. Google Scholar
  32. Liang Li, Pinyan Lu, and Yitong Yin. Approximate counting via correlation decay in spin systems. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 922-940. SIAM, 2012. Google Scholar
  33. Liang Li, Pinyan Lu, and Yitong Yin. Correlation decay up to uniqueness in spin systems. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 67-84. SIAM, 2013. Google Scholar
  34. Jiabao Lin and Hanpin Wang. The complexity of Boolean Holant problems with nonnegative weights. SIAM J. Comput., 47(3):798-828, 2018. URL: https://doi.org/10.1137/17M113304X.
  35. László Lovász. Operations with structures. Acta Mathematica Academiae Scientiarum Hungarica, 18(3-4):321-328, 1967. Google Scholar
  36. László Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society, 2012. URL: http://www.ams.org/bookstore-getitem/item=COLL-60.
  37. Pinyan Lu and Yitong Yin. Approximating the partition function of two-spin systems. In Encyclopedia of Algorithms, pages 117-123. Springer, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_750.
  38. M. MacDonald and Mark S. Seidenberg. Constraint satisfaction accounts of lexical and sentence comprehension, 2006. Google Scholar
  39. Elitza Maneva, Elchanan Mossel, and Martin J. Wainwright. A new look at survey propagation and its generalizations. J. ACM, 54(4):17-es, July 2007. URL: https://doi.org/10.1145/1255443.1255445.
  40. Nima Noorshams and M. Wainwright. Belief propagation for continuous state spaces: stochastic message-passing with quantitative guarantees. J. Mach. Learn. Res., 14:2799-2835, 2013. Google Scholar
  41. P. Raghavendra and D. Steurer. How to round any CSP. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 586-594, 2009. Google Scholar
  42. Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, pages 245-254, New York, NY, USA, 2008. Association for Computing Machinery. URL: https://doi.org/10.1145/1374376.1374414.
  43. Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. Journal of Statistical Physics, 155(4):666-686, 2014. Google Scholar
  44. Alistair Sinclair, Piyush Srivastava, and Yitong Yin. Spatial mixing and approximation algorithms for graphs with bounded connective constant. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 300-309. IEEE, 2013. Google Scholar
  45. Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 361-369. IEEE, 2012. Google Scholar
  46. L. Song, A. Gretton, D. Bickson, Y. Low, and Carlos Guestrin. Kernel belief propagation. In AISTATS, 2011. Google Scholar
  47. Mauricio Toro, C. Rueda, Carlos Agón, and G. Assayag. GELISP: A framework to represent musical constraint satisfaction problems and search strategies. Journal of theoretical and applied information technology, 86:327-331, 2016. Google Scholar
  48. M. Wainwright, T. Jaakkola, and A. Willsky. Map estimation via agreement on trees: message-passing and linear programming. IEEE Transactions on Information Theory, 51:3697-3717, 2005. Google Scholar
  49. Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 140-149, 2006. Google Scholar
  50. Mingji Xia. Holographic reduction: A domain changed application and its partial converse theorems. In Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, volume 6198 of Lecture Notes in Computer Science, pages 666-677. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-14165-2_56.
  51. Jonathan S. Yedidia, W. Freeman, and Yair Weiss. Generalized belief propagation. In NIPS, 2000. Google Scholar
  52. Hai-Jun Zhou. Spin glass approach to the feedback vertex set problem. The European Physical Journal B, 86:1-9, 2013. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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