Document Open Access Logo

An Algebraic Approach to Valued Constraint Satisfaction

Authors Rostislav Horcík, Tommaso Moraschini, Amanda Vidal

PDF
Thumbnail PDF

File

LIPIcs.CSL.2017.42.pdf
  • Filesize: 0.59 MB
  • 20 pages

Document Identifiers

Author Details

Rostislav Horcík
Tommaso Moraschini
Amanda Vidal

Cite As Get BibTex

Rostislav Horcík, Tommaso Moraschini, and Amanda Vidal. An Algebraic Approach to Valued Constraint Satisfaction. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CSL.2017.42

Abstract

We study the complexity of the valued CSP (VCSP, for short) over arbitrary templates, taking the general framework of integral bounded linearly order monoids as valuation structures. The class of problems considered here subsumes and generalizes the most common one in VCSP literature, since both monoidal and lattice conjunction operations are allowed in the formulation of constraints. Restricting to locally finite monoids, we introduce a notion of polymorphism that captures the pp-definability in the style of Geiger’s result. As a consequence, sufficient conditions for tractability of the classical CSP, related to the existence of certain polymorphisms, are shown to serve also for the valued case. Finally, we establish the dichotomy conjecture for the VCSP, modulo the dichotomy for classical CSP.

Subject Classification

Keywords
  • Valued CSP
  • Polymorphism
  • pp-definability
  • Geiger’s Theorem.

Metrics

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

References

  1. L. Barto and M. Kozik. Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem. Logical Methods in Computer Science, 8(1):1-26, 2012. Google Scholar
  2. L. Barto and M. Kozik. Constraint Satisfaction Problems Solvable by Local Consistency Methods. Journal of the ACM, 61(1):1-19, 2014. Google Scholar
  3. S. Bistarelli, U. Montanari, and F. Rossi. Semiring-based constraint satisfaction and optimization. Journal of the ACM, 44(2):201-236, 1997. Google Scholar
  4. M. Bodirsky. Complexity classification in infinite-domain constraint satisfaction. CoRR, abs/1201.0856, 2012. URL: http://arxiv.org/abs/1201.0856.
  5. M. Bodirsky and V. Dalmau. Datalog and constraint satisfaction with infinite templates. Journal of Computer and System Sciences, 79(1):79-100, 2013. Google Scholar
  6. M. Bodirsky and J. Nešetřil. Constraint Satisfaction with Countable Homogeneous Templates. Journal of Logic and Computation, 16(3):359-373, 2006. Google Scholar
  7. V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov. Galois theory for post algebras. I. Cybernetics, 5(3):243-252, 1969. Google Scholar
  8. V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov. Galois theory for Post algebras. II. Cybernetics, 5(5):531-539, 1969. Google Scholar
  9. A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs. CoRR, abs/1703.03021, 2017. URL: http://arxiv.org/abs/1703.03021.
  10. A. Bulatov and V. Dalmau. A Simple Algorithm for Mal'tsev Constraints. SIAM Journal on Computing, 36(1):16-27, 2006. Google Scholar
  11. A. Bulatov, P. Jeavons, and A. Krokhin. Classifying the Complexity of Constraints Using Finite Algebras. SIAM Journal on Computing, 34(3):720-742, 2005. Google Scholar
  12. D. Cohen, M. Cooper, P. Creed, P. Jeavons, and S. Živný. An Algebraic Theory of Complexity for Discrete Optimisation. SIAM Journal on Computing, 42(5):210-224, 2013. Google Scholar
  13. D. Cohen, M. Cooper, P. G. Jeavons, and A. Krokhin. The complexity of soft constraint satisfaction. Artificial Intelligence, 170(11):983-1016, 2006. Google Scholar
  14. D. A. Cohen. Tractable decision for a constraint language implies tractable search. Constraints, 9(3):219-229, 2004. Google Scholar
  15. M. Cooper and T. Schiex. Arc consistency for soft constraints. Artificial Intelligence, 154(1-2):199-227, 2004. Google Scholar
  16. F. Esteva and L. Godo. Monoidal t-norm based logic: towards a logic for left-continuous t-norms. Fuzzy Sets and Systems, 124(3):271-288, 2001. Google Scholar
  17. T. Feder and M. 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
  18. D. Geiger. Closed systems of functions and predicates. Pacific Journal of Mathematics, 27(1), 1968. Google Scholar
  19. P. Idziak, R. Mckenzie, M. Valeriote, and R. Willard. Tractability and learnability arising from algebras with few subpowers. In LICS, pages 213-222, 2007. Google Scholar
  20. P. Kolaitis and M. Vardi. Conjunctive-Query Containment and Constraint Satisfaction. Journal of Computer and System Sciences, 61(2):302-332, 2000. Google Scholar
  21. V. Kolmogorov, A. Krokhin, and M. Rolinek. The Complexity of General-Valued CSPs. In FOCS, pages 1246-1258, 2015. Google Scholar
  22. V. Kolmogorov, J. Thapper, and S. Živný. The Power of Linear Programming for General-Valued CSPs. SIAM Journal on Computing, 44(1):1-36, 2015. Google Scholar
  23. M. Kozik and J. Ochremiak. Algebraic properties of valued constraint satisfaction problem. In ICALP, Part I, pages 846-858, 2015. Google Scholar
  24. A. Rafiey, J. Kinne, and T. Feder. Dichotomy for digraph homomorphism problems. CoRR, abs/1701.02409, 2017. URL: http://arxiv.org/abs/1701.02409.
  25. F. Rossi, P. van Beek, and T. Walsh. Handbook of Constraint Programming (Foundations of Artificial Intelligence). Elsevier Science Inc., 2006. Google Scholar
  26. M. Siggers. A strong Mal'cev condition for locally finite varieties omitting the unary type. Algebra Universalis, 64(1-2):15-20, 2010. Google Scholar
  27. J. Thapper and S. Živný. The complexity of finite-valued CSPs. In STOC, page 695. ACM Press, 2013. Google Scholar
  28. E. Vodolazskii, B. Flach, and M. Schlesinger. Minimax problems of discrete optimization invariant under majority operators. Computational Mathematics and Mathematical Physics, 54(8):1327-1336, 2014. Google Scholar
  29. S. Živný. The Complexity of Valued Constraint Satisfaction Problems. Cognitive Technologies. Springer Berlin Heidelberg, 2012. 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