Document Open Access Logo

The Complexity of Boolean Surjective General-Valued CSPs

Authors Peter Fulla, Stanislav Zivny

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.4.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Peter Fulla
Stanislav Zivny

Cite AsGet BibTex

Peter Fulla and Stanislav Zivny. The Complexity of Boolean Surjective General-Valued CSPs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.4

Abstract

Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with the objective function given as a sum of fixed-arity functions; the values are rational numbers or infinity. In Boolean surjective VCSPs variables take on labels from D={0,1} and an optimal assignment is required to use both labels from D. A classic example is the global min-cut problem in graphs. Building on the work of Uppman, we establish a dichotomy theorem and thus give a complete complexity classification of Boolean surjective VCSPs. The newly discovered tractable case has an interesting structure related to projections of downsets and upsets. Our work generalises the dichotomy for {0,infinity}-valued constraint languages corresponding to CSPs) obtained by Creignou and Hebrard, and the dichotomy for {0,1}-valued constraint languages (corresponding to Min-CSPs) obtained by Uppman.
Keywords
  • constraint satisfaction problems
  • surjective CSP
  • valued CSP
  • min-cut
  • polymorphisms
  • multimorphisms

Metrics

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

References

  1. Libor Barto. Constraint satisfaction problem and universal algebra. ACM SIGLOG News, 1(2):14-24, 2014. URL: http://dx.doi.org/10.1145/2677161.2677165.
  2. Libor Barto and Marcin Kozik. Constraint Satisfaction Problems Solvable by Local Consistency Methods. Journal of the ACM, 61(1), 2014. Article No. 3. URL: http://dx.doi.org/10.1145/2556646.
  3. Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017. URL: http://dx.doi.org/10.4230/DFU.Vol7.15301.1.
  4. Manuel Bodirsky, Jan Kára, and Barnaby Martin. The complexity of surjective homomorphism problems - a survey. Discrete Applied Mathematics, 160(12):1680-1690, 2012. URL: http://dx.doi.org/10.1016/j.dam.2012.03.029.
  5. Andrei Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM, 53(1):66-120, 2006. URL: http://dx.doi.org/10.1145/1120582.1120584.
  6. Andrei Bulatov, Andrei Krokhin, and Peter Jeavons. Classifying the Complexity of Constraints using Finite Algebras. SIAM Journal on Computing, 34(3):720-742, 2005. URL: http://dx.doi.org/10.1137/S0097539700376676.
  7. Hubie Chen. An algebraic hardness criterion for surjective constraint satisfaction. Algebra universalis, 72(4):393-401, 2014. URL: http://dx.doi.org/10.1007/s00012-014-0308-x.
  8. David A. Cohen, Martin C. Cooper, Peter G. Jeavons, and Andrei A. Krokhin. The Complexity of Soft Constraint Satisfaction. Artificial Intelligence, 170(11):983-1016, 2006. URL: http://dx.doi.org/10.1016/j.artint.2006.04.002.
  9. Nadia Creignou. A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences, 51(3):511-522, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1087.
  10. Nadia Creignou and Jean-Jacques Hébrard. On generating all solutions of generalized satisfiability problems. ITA, 31(6):499-511, 1997. Google Scholar
  11. 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: http://dx.doi.org/10.1137/S0097539794266766.
  12. Jiří Fiala and Jan Kratochvíl. Locally constrained graph homomorphisms - structure, complexity, and applications. Computer Science Review, 2(2):97-111, 2008. URL: http://dx.doi.org/10.1016/j.cosrev.2008.06.001.
  13. Jiří Fiala and Daniël Paulusma. A complete complexity classification of the role assignment problem. Theoretical Computer Science, 349(1):67-81, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.029.
  14. Peter Fulla and Stanislav Živný. The complexity of Boolean surjective general-valued CSPs. CoRR, abs/1702.04679, 2017. URL: http://arxiv.org/abs/1702.04679.
  15. Anna Huber, Andrei Krokhin, and Robert Powell. Skew bisubmodularity and valued CSPs. SIAM Journal on Computing, 43(3):1064-1084, 2014. URL: http://dx.doi.org/10.1137/120893549.
  16. Peter Jonsson, Mikael Klasson, and Andrei A. Krokhin. The approximability of three-valued MAX CSP. SIAM Journal on Computing, 35(6):1329-1349, 2006. URL: http://dx.doi.org/10.1137/S009753970444644X.
  17. David R. Karger. Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'93), pages 21-30, 1993. Google Scholar
  18. Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolínek. The complexity of general-valued CSPs. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS'15). IEEE Computer Society, 2015. Google Scholar
  19. Marcin Kozik and Joanna Ochremiak. Algebraic properties of valued constraint satisfaction problem. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP'15), volume 9134 of Lecture Notes in Computer Science, pages 846-858. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_69.
  20. Barnaby Martin and Daniël Paulusma. The computational complexity of disconnected cut and 2K₂-partition. Journal of Combinatorial Theory, Series B, 111:17-37, 2015. URL: http://dx.doi.org/10.1016/j.jctb.2014.09.002.
  21. Thomas J. Schaefer. The Complexity of Satisfiability Problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC'78), pages 216-226. ACM, 1978. URL: http://dx.doi.org/10.1145/800133.804350.
  22. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer, 2003. Google Scholar
  23. Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. Journal of the ACM, 44(4):585-591, 1997. URL: http://dx.doi.org/10.1145/263867.263872.
  24. Hannes Uppman. Max-Sur-CSP on Two Elements. In Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP'12), volume 7514 of Lecture Notes in Computer Science, pages 38-54. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33558-7_6.
  25. Vijay V. Vazirani and Mihalis Yannakakis. Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract). In Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP'92), pages 366-377. Springer-Verlag, 1992. URL: http://dl.acm.org/citation.cfm?id=646246.684856.
  26. Narayan Vikas. Algorithms for partition of some class of graphs under compaction and vertex-compaction. Algorithmica, 67(2):180-206, 2013. URL: http://dx.doi.org/10.1007/s00453-012-9720-9.
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