Document Open Access Logo

Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems

Authors Andreas Galanis, Leslie Ann Goldberg, Kuan Yang

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2017.27.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • Constraint Satisfaction
  • Approximate Counting

Metrics

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

Abstract

We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language Gamma and a degree bound Delta, we study the complexity of #CSP_Delta(Gamma), which is the problem of counting satisfying assignments to CSP instances with constraints from Gamma and whose variables can appear at most Delta times. Our main result shows that: (i) if every function in Gamma is affine, then #CSP_Delta(Gamma) is in FP for all Delta, (ii) otherwise, if every function in Gamma is in a class called IM_2, then for all sufficiently large Delta, #CSP_Delta(Gamma) is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large Delta, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSP_Delta(Gamma), even within an exponential factor. Our result extends previous results, which apply only in the so-called "conservative" case.

Cite As Get BibTex

Andreas Galanis, Leslie Ann Goldberg, and Kuan Yang. Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.27

Author Details

Andreas Galanis
Leslie Ann Goldberg
Kuan Yang

References

  1. Ivona Bezáková, Andreas Galanis, Leslie A. Goldberg, Heng Guo, and Daniel Štefankovič. Approximation via Correlation Decay when Strong Spatial Mixing Fails. ArXiv e-prints, October 2015. URL: http://arxiv.org/abs/1510.09193.
  2. Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). Dagstuhl Reports, 5(7):22-41, 2016. URL: http://dx.doi.org/10.4230/DagRep.5.7.22.
  3. Jin-Yi Cai. Complexity dichotomy for counting problems. In Language and Automata Theory and Applications - 7th International Conference, LATA 2013, Bilbao, Spain, April 2-5, 2013. Proceedings, pages 1-11, 2013. URL: http://dx.doi.org/10.1007/978-3-642-37064-9_1.
  4. Jin-Yi Cai, Andreas Galanis, Leslie A. Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, and Eric Vigoda. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Journal of Computer and System Sciences, 82(5):690-711, 2016. URL: http://dx.doi.org/10.1016/j.jcss.2015.11.009.
  5. 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: http://dx.doi.org/10.1016/j.jcss.2013.07.003.
  6. Nadia Creignou and Miki Hermann. Complexity of generalized satisfiability counting problems. Inf. Comput., 125(1):1-12, 1996. URL: http://dx.doi.org/10.1006/inco.1996.0016.
  7. Víctor Dalmau and Daniel K. Ford. Generalized satisfability with limited occurrences per variable: A study through delta-matroid parity. In Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings, pages 358-367, 2003. URL: http://dx.doi.org/10.1007/978-3-540-45138-9_30.
  8. Martin Dyer, Leslie A. Goldberg, Catherine Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3):471-500, 2003. URL: http://dx.doi.org/10.1007/s00453-003-1073-y.
  9. Martin E. Dyer, Leslie A. Goldberg, Markus Jalsenius, and David Richerby. The complexity of approximating bounded-degree boolean #CSP. Inf. Comput., 220:1-14, 2012. URL: http://dx.doi.org/10.1016/j.ic.2011.12.007.
  10. Martin E. Dyer, Leslie A. Goldberg, and Mark Jerrum. An approximation trichotomy for boolean #csp. J. Comput. Syst. Sci., 76(3-4):267-277, 2010. URL: http://dx.doi.org/10.1016/j.jcss.2009.08.003.
  11. Andreas Galanis and Leslie A. Goldberg. The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs. Information and Computation, 251:36-66, 2016. Google Scholar
  12. Pavol Hell and Jaroslav Nešetřil. Graphs and homomorphisms. Oxford lecture series in mathematics and its applications. Oxford University Press, Oxford, New York, 2004. URL: http://opac.inria.fr/record=b1121618.
  13. Jonathan Hermon, Allan Sly, and Yumeng Zhang. Rapid mixing of hypergraph independent set. CoRR, abs/1610.07999, 2016. URL: http://arxiv.org/abs/1610.07999.
  14. Phokion G. Kolaitis and Moshe Y. Vardi. Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci., 61(2):302-332, 2000. URL: http://dx.doi.org/10.1006/jcss.2000.1713.
  15. Vipin Kumar. Algorithms for constraint-satisfaction problems: A survey. AI Magazine, 13(1):32-44, 1992. URL: http://www.aaai.org/ojs/index.php/aimagazine/article/view/976.
  16. Jingcheng Liu and Pinyan Lu. FPTAS for counting monotone CNF. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1531-1548, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.101.
  17. Ugo Montanari. Networks of constraints: Fundamental properties and applications to picture processing. Inf. Sci., 7:95-132, 1974. URL: http://dx.doi.org/10.1016/0020-0255(74)90008-5.
  18. Francesca Rossi, Peter van Beek, and Toby Walsh. Handbook of Constraint Programming (Foundations of Artificial Intelligence). Elsevier Science Inc., New York, NY, USA, 2006. Google Scholar
  19. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216-226, 1978. URL: http://dx.doi.org/10.1145/800133.804350.
  20. Renjie Song, Yitong Yin, and Jinman Zhao. Counting hypergraph matchings up to uniqueness threshold. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France, pages 46:1-46:29, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.46.
  21. Dominic J. A. Welsh. Complexity: Knots, Colourings and Counting. Cambridge University Press, New York, NY, USA, 1993. 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