Document Open Access Logo

On Redundancy in Constraint Satisfaction Problems

Author Clément Carbonnel

PDF
Thumbnail PDF

File

LIPIcs.CP.2022.11.pdf
  • Filesize: 0.72 MB
  • 15 pages

Document Identifiers

Author Details

Clément Carbonnel
  • CNRS, LIRMM, University of Montpellier, France

Funding

This work was supported by the AI Interdisciplinary Institute ANITI, funded by the French program "Investing for the Future – PIA3" under grant agreement no. ANR-19-PI3A-0004. The author also received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement no. 952215.

Cite AsGet BibTex

Clément Carbonnel. On Redundancy in Constraint Satisfaction Problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CP.2022.11

Abstract

A constraint language Γ has non-redundancy f(n) if every instance of CSP(Γ) with n variables contains at most f(n) non-redundant constraints. If Γ has maximum arity r then it has non-redundancy O(n^r), but there are notable examples for which this upper bound is far from the best possible. In general, the non-redundancy of constraint languages is poorly understood and little is known beyond the trivial bounds Ω(n) and O(n^r). In this paper, we introduce an elementary algebraic framework dedicated to the analysis of the non-redundancy of constraint languages. This framework relates redundancy-preserving reductions between constraint languages to closure operators known as pattern partial polymorphisms, which can be interpreted as generic mechanisms to generate redundant constraints in CSP instances. We illustrate the power of this framework by deriving a simple characterisation of all languages of arity r having non-redundancy Θ(n^r).

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
  • Mathematics of computing → Discrete mathematics
Keywords
  • Constraint satisfaction problem
  • redundancy
  • universal algebra
  • extremal combinatorics

Metrics

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

References

  1. Albert Atserias, Andrei A. Bulatov, and Anuj Dawar. Affine systems of equations and counting infinitary logic. Theoretical Compututer Science, 410(18):1666-1683, 2009. URL: https://doi.org/10.1016/j.tcs.2008.12.049.
  2. Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, and Dmitriy Zhuk. Minimal taylor algebras as a common framework for the three algebraic approaches to the CSP. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'21), pages 1-13. IEEE, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470557.
  3. Libor Barto and Marcin Kozik. Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM, 61(1):3:1-3:19, 2014. URL: https://doi.org/10.1145/2556646.
  4. Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Dagstuhl Follow-Ups, volume 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  5. Christian Bessiere, Clément Carbonnel, and George Katsirelos. Chain length and csps learnable with few queries. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI'20), pages 1420-1427, 2020. URL: https://doi.org/10.1609/aaai.v34i02.5499.
  6. Christian Bessiere, Remi Coletta, Emmanuel Hebrard, George Katsirelos, Nadjib Lazaar, Nina Narodytska, Claude-Guy Quimper, and Toby Walsh. Constraint acquisition via partial queries. In Francesca Rossi, editor, Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI'13), pages 475-481, 2013. Google Scholar
  7. Christian Bessiere, Frédéric Koriche, Nadjib Lazaar, and Barry O'Sullivan. Constraint acquisition. Artificial Intelligence, 244:315-342, 2017. URL: https://doi.org/10.1016/j.artint.2015.08.001.
  8. Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS'17), pages 319-330. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  9. Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse. Best-case and worst-case sparsifiability of Boolean csps. Algorithmica, 82(8):2200-2242, 2020. URL: https://doi.org/10.1007/s00453-019-00660-y.
  10. Hubie Chen and Matthew Valeriote. Learnability of solutions to conjunctive queries. Journal of Machine Learing Research, 20:67:1-67:28, 2019. URL: http://jmlr.org/papers/v20/17-734.html.
  11. Miguel Couceiro, Lucien Haddad, and Victor Lagerkvist. A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms. J. Multiple Valued Log. Soft Comput., 38(1-2):115-136, 2022. Google Scholar
  12. László Egri, Pavol Hell, Benoît Larose, and Arash Rafiey. Space complexity of list H-colouring: a dichotomy. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), pages 349-365. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.26.
  13. P Erdös. On extremal problems of graphs and generalized graphs. Israel Journal of Mathematics, 2(3):183-190, 1964. Google Scholar
  14. 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. Google Scholar
  15. David Geiger. Closed systems of functions and predicates. Pacific journal of mathematics, 27(1):95-100, 1968. Google Scholar
  16. Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard. Tractability and learnability arising from algebras with few subpowers. SIAM Journal on Computing, 39(7):3023-3037, 2010. URL: https://doi.org/10.1137/090775646.
  17. Peter Jeavons, David Cohen, and Marc Gyssens. Closure properties of constraints. J. ACM, 44(4):527-548, July 1997. URL: https://doi.org/10.1145/263867.263489.
  18. Peter Jonsson, Victor Lagerkvist, Gustav Nordh, and Bruno Zanuttini. Strong partial clones and the time complexity of SAT problems. J. Comput. Syst. Sci., 84:52-78, 2017. URL: https://doi.org/10.1016/j.jcss.2016.07.008.
  19. Peter Keevash. Hypergraph turán problems. Surveys in combinatorics, 392:83-140, 2011. Google Scholar
  20. Victor Lagerkvist and Magnus Wahlström. Kernelization of constraint satisfaction problems: A study through universal algebra. In Proceedings of the 23rd Conference on Principles and Practice of Constraint Programming (CP'17), pages 157-171, 2017. URL: https://doi.org/10.1007/978-3-319-66158-2_11.
  21. Victor Lagerkvist and Magnus Wahlström. Which np-hard SAT and CSP problems admit exponentially improved algorithms? CoRR, abs/1801.09488, 2018. URL: http://arxiv.org/abs/1801.09488.
  22. Benoît Larose, Cynthia Loten, and Claude Tardif. A characterisation of first-order constraint satisfaction problems. Logical Methods in Computer Science, 3(4), 2007. URL: https://doi.org/10.2168/LMCS-3(4:6)2007.
  23. Emil L. Post. The two-valued iterative systems of mathematical logic. Annals of Mathematics studies, 1941. URL: https://doi.org/10.2307/2268608.
  24. Boris A Romov. The algebras of partial functions and their invariants. Cybernetics, 17(2):157-167, 1981. Google Scholar
  25. Thomas J. Schaefer. The complexity of satisfiability problems. In STOC '78: Proceedings of the tenth annual ACM Symposium on Theory of Computing (STOC'78), pages 216-226. Association for Computing Machinery, 1978. URL: https://doi.org/10.1145/800133.804350.
  26. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. Journal of the ACM, 67(5):30:1-30:78, 2020. URL: https://doi.org/10.1145/3402029.
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