Document Open Access Logo

Approximate Counting CSP Seen from the Other Side

Authors Andrei A. Bulatov, Stanislav Živný

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.60.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Andrei A. Bulatov
  • School of Computing Science, Simon Fraser University, Canada
Stanislav Živný
  • Department of Computer Science, University of Oxford, UK

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.
  • Bulatov, Andrei A.: Andrei Bulatov was supported by an NSERC Discovery grant.
  • Živný, Stanislav: Stanislav Živný was supported by a Royal Society University Research Fellowship.

Cite As Get BibTex

Andrei A. Bulatov and Stanislav Živný. Approximate Counting CSP Seen from the Other Side. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.60

Abstract

In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(C,-), in which the goal is, given a relational structure A from a class C of structures and an arbitrary structure B, to find the number of homomorphisms from A to B. Flum and Grohe showed that #CSP(C,-) is solvable in polynomial time if C has bounded treewidth [FOCS'02]. Building on the work of Grohe [JACM'07] on decision CSPs, Dalmau and Jonsson then showed that, if C is a recursively enumerable class of relational structures of bounded arity, then assuming FPT != #W[1], there are no other cases of #CSP(C,-) solvable exactly in polynomial time (or even fixed-parameter time) [TCS'04].
We show that, assuming FPT != W[1] (under randomised parametrised reductions) and for C satisfying certain general conditions, #CSP(C,-) is not solvable even approximately for C of unbounded treewidth; that is, there is no fixed parameter tractable (and thus also not fully polynomial) randomised approximation scheme for #CSP(C,-). In particular, our condition generalises the case when C is closed under taking minors.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • constraint satisfaction
  • approximate counting
  • homomorphisms

Metrics

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

References

  1. Vikraman Arvind and Venkatesh Raman. Approximation Algorithms for Some Parameterized Counting Problems. In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC'02), volume 2518 of Lecture Notes in Computer Science, pages 453-464. Springer, 2002. URL: https://doi.org/10.1007/3-540-36136-7_40.
  2. Johann Brault-Baron, Florent Capelli, and Stefan Mengel. Understanding Model Counting for beta-acyclic CNF-formulas. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS'15), pages 143-156, 2015. URL: https://doi.org/10.4230/LIPIcs.STACS.2015.143.
  3. Andrei Bulatov. A dichotomy theorem for nonuniform CSP. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS'17), pages 319-330. IEEE, 2017. Google Scholar
  4. Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the Complexity of Constraints using Finite Algebras. SIAM Journal on Computing, 34(3):720-742, 2005. URL: https://doi.org/10.1137/S0097539700376676.
  5. Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. Journal of the ACM, 60(5):34, 2013. URL: https://doi.org/10.1145/2528400.
  6. Jin-Yi Cai and Xi Chen. Complexity of Counting CSP with Complex Weights. Journal of the ACM, 64(3):19:1-19:39, 2017. URL: https://doi.org/10.1145/2822891.
  7. Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby. The complexity of approximating conservative counting CSPs. Journal of Computer and System Sciences, 81(1):311-329, 2015. Google Scholar
  8. Nadia Creignou and Miki Hermann. Complexity of Generalized Satisfiability Counting Problems. Information and Computation, 125(1):1-12, 1996. Google Scholar
  9. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theoretical Computer Science, 329(1-3):315-323, 2004. URL: https://doi.org/10.1016/j.tcs.2004.08.008.
  10. Víctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP'02), volume 2470 of Lecture Notes in Computer Science, pages 310-326. Springer, 2002. URL: https://doi.org/10.1007/3-540-46135-3_21.
  11. Reinhard Diestel. Graph Theory. Springer, fourth edition, 2010. Google Scholar
  12. Rodney G. Downey and Michael R. Fellows. Fixed-Parameter Tractability and Completeness I: Basic Results. SIAM Journal on Computing Computing, 24(4):873-921, 1995. URL: https://doi.org/10.1137/S0097539792228228.
  13. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141(1-2):109-131, 1995. Google Scholar
  14. Rodney G. Downey, Michael R. Fellows, and Kenneth W. Regan. Parameterized Circuit Complexity and the W Hierarchy. Theoretical Computer Science, 191(1-2):97-115, 1998. URL: https://doi.org/10.1016/S0304-3975(96)00317-9.
  15. Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, and Mark Jerrum. The Relative Complexity of Approximate Counting Problems. Algorithmica, 38(3):471-500, 2004. URL: https://doi.org/10.1007/s00453-003-1073-y.
  16. Martin E. Dyer, Leslie Ann Goldberg, and Mark Jerrum. An approximation trichotomy for Boolean #CSP. Journal of Computer and System Sciences, 76(3-4):267-277, 2010. URL: https://doi.org/10.1016/j.jcss.2009.08.003.
  17. Martin E. Dyer and Catherine S. Greenhill. The complexity of counting graph homomorphisms. Random Struct. Algorithms, 17(3-4):260-289, 2000. Google Scholar
  18. Martin E. 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.
  19. Tomás Feder, Pavol Hell, Daniel Král', and Jiří Sgall. Two algorithms for general list matrix partitions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05), pages 870-876, 2005. Google Scholar
  20. Tomás Feder, Pavol Hell, and Wing Xie. Matrix Partitions with Finitely Many Obstructions. Electr. J. Comb., 14(1), 2007. Google Scholar
  21. Tomás Feder and Moshe Y. Vardi. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM Journal on Computing, 28(1):57-104, 1998. URL: https://doi.org/10.1137/S0097539794266766.
  22. Jörg Flum and Martin Grohe. The Parameterized Complexity of Counting Problems. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS'02), page 538. IEEE Computer Society, 2002. URL: https://doi.org/10.1109/SFCS.2002.1181978.
  23. Jörg Flum and Martin Grohe. The Parameterized Complexity of Counting Problems. SIAM Journal on Computing, 33(4):892-922, 2004. URL: https://doi.org/10.1137/S0097539703427203.
  24. Jörg Flum and Martin Grohe. Parametrized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. Google Scholar
  25. Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum. Approximately Counting H-Colorings is #BIS-Hard. SIAM Journal on Computing, 45(3):680-711, 2016. Google Scholar
  26. Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum. A Complexity Trichotomy for Approximately Counting List H-Colorings. ACM Transactions on Computation Theory, 9(2):9:1-9:22, 2017. URL: https://doi.org/10.1145/3037381.
  27. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979. Google Scholar
  28. Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decomposition and tractable queries. Journal of Computer and System Sciences, 64(3):579-627, 2002. URL: https://doi.org/10.1006/jcss.2001.1809.
  29. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1):1-24, 2007. URL: https://doi.org/10.1145/1206035.1206036.
  30. Martin Grohe and Dániel Marx. Constraint Solving via Fractional Edge Covers. ACM Transactions on Algorithms, 11(1):4:1-4:20, 2014. URL: https://doi.org/10.1145/2636918.
  31. Martin Grohe, Thomas Schwentick, and Luc Segoufin. When is the evaluation of conjunctive queries tractable? In Proceedings 33rd ACM Symposium on Theory of Computing (STOC'01), pages 657-666. ACM, 2001. URL: https://doi.org/10.1145/380752.380867.
  32. Pavol Hell and Jaroslav Nešetřil. On the Complexity of H-coloring. Journal of Combinatorial Theory, Series B, 48(1):92-110, 1990. URL: https://doi.org/10.1016/0095-8956(90)90132-J.
  33. Phokion G. Kolaitis and Moshe Y. Vardi. Conjunctive-Query Containment and Constraint Satisfaction. Journal of Computer and System Sciences, 61(2):302-332, 2000. URL: https://doi.org/10.1006/jcss.2000.1713.
  34. Kitty Meeks. The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Applied Mathematics, 198:170-194, 2016. URL: https://doi.org/10.1016/j.dam.2015.06.019.
  35. Michael Mitzenmacher and Eli Upfal. Probability and Computing. Cambridge University Press, Cambridge, second edition, 2017. Randomization and Probabilistic techniques in Algorithms and Data Analysis. Google Scholar
  36. Neil Robertson and Paul D. Seymour. Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49-64, 1984. URL: https://doi.org/10.1016/0095-8956(84)90013-3.
  37. Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92-114, 1986. URL: https://doi.org/10.1016/0095-8956(86)90030-4.
  38. Thomas J. Schaefer. The Complexity of Satisfiability Problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOCS'78), pages 216-226, 1978. Google Scholar
  39. Dmitriy Zhuk. The Proof of CSP Dichotomy Conjecture. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS'17), pages 331-342. IEEE, 2017. 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