Document Open Access Logo

The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights

Authors Jiabao Lin, Hanpin Wang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.29.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Jiabao Lin
Hanpin Wang

Cite As Get BibTex

Jiabao Lin and Hanpin Wang. The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.29

Abstract

Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Holant problems over the Boolean domain with non-negative weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric. 

Holant problems are indeed read-twice #CSPs. Intuitively, some #CSPs that are #P-hard become tractable when restricted to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set F satisfies the condition, then F is of affine type or product type. Otherwise (a) Holant(F) is #P-hard; or (b) every function in F is a tensor product of functions of arity at most 2; or (c) F is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability.

Subject Classification

Keywords
  • counting complexity
  • dichotomy
  • Holant
  • #CSP

Metrics

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

References

  1. Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34, 2013. Google Scholar
  2. Andrei A. Bulatov and Víctor Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem. Inf. Comput., 205(5):651-678, 2007. Google Scholar
  3. Andrei A. Bulatov, Martin E. Dyer, Leslie A. Goldberg, Markus Jalsenius, Mark Jerrum, and David Richerby. The complexity of weighted and unweighted #CSP. J. Comput. Syst. Sci., 78(2):681-688, 2012. Google Scholar
  4. Andrei A. Bulatov, Martin E. Dyer, Leslie A. Goldberg, Markus Jalsenius, and David Richerby. The complexity of weighted Boolean #CSP with mixed signs. Theor. Comput. Sci., 410(38-40):3949-3961, 2009. Google Scholar
  5. Andrei A. Bulatov and Martin Grohe. The complexity of partition functions. Theor. Comput. Sci., 348(2):148-186, 2005. Google Scholar
  6. Jin-Yi Cai and Xi Chen. A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. In Proceedings of 51th Annual IEEE Symposium on Foundations of Computer Science, pages 437-446, 2010. Google Scholar
  7. Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. In Proceedings of the 44th Symposium on Theory of Computing, pages 909-920, 2012. Google Scholar
  8. 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, pages 45-54, 2011. Google Scholar
  9. Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem. SIAM J. Comput., 42(3):934-1029, 2013. Google Scholar
  10. Jin-Yi Cai, Zhiguo Fu, Heng Guo, and Tyson Williams. A Holant dichotomy: Is the FKT algorithm universal? In IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1259-1276, 2015. Google Scholar
  11. Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures: Extended abstract. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 635-644, 2013. Google Scholar
  12. Jin-Yi Cai, Heng Guo, and Tyson Williams. Holographic algorithms beyond matchgates. In Proceedings of ICALP, pages 271-282, 2014. Google Scholar
  13. Jin-Yi Cai, Sangxia Huang, and Pinyan Lu. From Holant to #CSP and back: Dichotomy for Holant^c problems. Algorithmica, 64(3):511-533, 2012. Google Scholar
  14. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holant problems and counting CSP. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 715-724, 2009. Google Scholar
  15. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of Holant problems. SIAM J. Comput., 40(4):1101-1132, 2011. Google Scholar
  16. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for Holant^* problems of Boolean domain. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1714-1728, 2011. Google Scholar
  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. Google Scholar
  18. Nadia Creignou and Miki Hermann. Complexity of generalized satisfiability counting problems. Inf. Comput., 125(1):1-12, 1996. Google Scholar
  19. Martin E. Dyer, Leslie A. Goldberg, and Mark Jerrum. The complexity of weighted Boolean #CSP. SIAM J. Comput., 38(5):1970-1986, 2009. Google Scholar
  20. Martin E. Dyer, Leslie A. Goldberg, and Mike Paterson. On counting homomorphisms to directed acyclic graphs. J. ACM, 54(6), 2007. Google Scholar
  21. Martin E. Dyer and Catherine S. Greenhill. The complexity of counting graph homomorphisms. Random Struct. Algorithms, 17(3-4):260-289, 2000. Google Scholar
  22. Martin E. Dyer and David Richerby. On the complexity of #CSP. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 725-734, 2010. Google Scholar
  23. Martin E. Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput., 42(3):1245-1274, 2013. Google Scholar
  24. Michael Freedman, László Lovász, and Alexander Schrijver. Reflection positivity, rank connectivity, and homomorphism of graphs. J. Amer. Math. Soc., 20(1):37-51, 2007. Google Scholar
  25. Leslie A. Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput., 39(7):3336-3402, 2010. Google Scholar
  26. Heng Guo, Pinyan Lu, and Leslie G. Valiant. The complexity of symmetric Boolean parity Holant problems. SIAM J. Comput., 42(1):324-356, 2013. Google Scholar
  27. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. J. Comb. Theory Ser. B, 48(1):92-110, 1990. Google Scholar
  28. Sangxia Huang and Pinyan Lu. A dichotomy for real weighted Holant problems. In Proceedings of the 27th Conference on Computational Complexity, pages 96-106, 2012. Google Scholar
  29. Richard E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22(1):155-171, 1975. Google Scholar
  30. László Lovász. Operations with structures. Acta Math. Hung., 18(3-4):321-328, 1967. Google Scholar
  31. Leslie G. Valiant. Accidental algorithms. In Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science, pages 509-517, 2006. Google Scholar
  32. Leslie G. Valiant. Holographic algorithms. SIAM J. Comput., 37(5):1565-1594, 2008. 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 About DROPS Imprint Privacy Contact