Abstract
The constraint satisfaction problem (CSP) on a finite relational structure B is to decide, given a set of constraints on variables where the relations come from B, whether or not there is an assignment to the variables satisfying all of the constraints; the surjective CSP is the variant where one decides the existence of a surjective satisfying assignment onto the universe of B. We present an algebraic framework for proving hardness results on surjective CSPs; essentially, this framework computes global gadgetry that permits one to present a reduction from a classical CSP to a surjective CSP. We show how to derive a number of hardness results for surjective CSP in this framework, including the hardness of the disconnected cut problem, of the no-rainbow three-coloring problem, and of the surjective CSP on all two-element structures known to be intractable (in this setting). Our framework thus allows us to unify these hardness results and reveal common structure among them; we believe that our hardness proof for the disconnected cut problem is more succinct than the original. In our view, the framework also makes very transparent a way in which classical CSPs can be reduced to surjective CSPs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Manuel Bodirsky, Jan Kára & Barnaby Martin (2012). The complexity of surjective homomorphism problems - a survey. Discrete Applied Mathematics 160(12), 1680–1690.
Manuel Bodirsky & Jens K. Müller (2011). The Complexity of Rooted Phylogeny Problems. Logical Methods in Computer Science 7(4).
Andrei A. Bulatov (2017). A Dichotomy Theorem for Nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, 319–330.
Andrei A. Bulatov & Dániel Marx (2010). The complexity of global cardinality constraints. Logical Methods in Computer Science 6(4).
Hubie Chen (2014). An algebraic hardness criterion for surjective constraint satisfaction. Algebra Universalis 72(4), 393–401.
Hubie Chen, Radu Curticapean & Holger Dell (2019). The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms. In Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers, Ignasi Sau & Dimitrios M. Thilikos, editors, volume 11789 of Lecture Notes in Computer Science, 364–378. Springer.
Hubie Chen, Bart M. P. Jansen & Astrid Pieterse (2020). Best-Case and Worst-Case Sparsifiability of Boolean CSPs. Algorithmica 82(8), 2200–2242.
Hubie Chen & Benoit Larose (2017). Asking the Metaquestions in Constraint Tractability. TOCT 9(3), 11:1–11:27.
Miguel Couceiro, Lucien Haddad & Victor Lagerkvist (2019). Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey. In 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL), Fredericton, NB, Canada, May 21-23, 2019, 170–175. IEEE.
N. Creignou, S. Khanna & M. Sudan (2001). Complexity Classification of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics.
Radu Curticapean, Holger Dell & Dániel Marx (2017). Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, 210–223.
Jacob Focke, Leslie Ann Goldberg & Stanislav Zivny (2019). The Complexity of Counting Surjective Homomorphisms and Compactions. SIAM J. Discret. Math. 33(2), 1006–1043.
Peter Fulla, Hannes Uppman & Stanislav Zivny (2019). The Complexity of Boolean Surjective General-Valued CSPs. ACM Trans. Comput. Theory 11(1), 4:1–4:31.
Petr A. Golovach, Matthew Johnson, Barnaby Martin, Daniël Paulusma & Anthony Stewart (2019). Surjective Hcolouring: New hardness results. Computability 8(1), 27–42.
Petr A. Golovach, Daniël Paulusma & Jian Song (2012). Computing vertex-surjective homomorphisms to partially reflexive trees. Theor. Comput. Sci. 457, 86–100. URL https://doi.org/10.1016/j.tcs.2012.06.039.
Bart M. P. Jansen & Astrid Pieterse (2019). Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials. ACM Trans. Comput. Theory 11(4), 28:1–28:26.
Peter Jonsson, Victor Lagerkvist, Gustav Nordh & Bruno Zanuttini (2017). Strong partial clones and the time complexity of SAT problems. J. Comput. Syst. Sci. 84, 52–78.
Daniel Král, Jan Kratochvíl, Andrzej Proskurowski & Heinz-Jürgen Voss (2006). Coloring mixed hypertrees. Discret. Appl. Math. 154(4), 660–672.
Andrei A. Krokhin, Andrei A. Bulatov & Peter Jeavons (2003). Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. In 33rd IEEE International Symposium on Multiple-Valued Logic (ISMVL 2003), 16-19 May 2003, Tokyo, Japan, 343–354. IEEE Computer Society.
Andrei A. Krokhin & Stanislav Zivny (editors) (2017). The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Victor Lagerkvist & Biman Roy (2017). A Dichotomy Theorem for the Inverse Satisfiability Problem. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India, Satya V. Lokam & R. Ramanujam, editors, volume 93 of LIPIcs, 39:39–39:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Victor Lagerkvist & Magnus Wahlström (2020). Sparsification of SAT and CSP Problems via Tractable Extensions. ACM Trans. Comput. Theory 12(2), 13:1–13:29.
Benoît Larose, Barnaby Martin & Daniël Paulusma (2019). Surjective H-Colouring over Reflexive Digraphs. ACM Trans. Comput. Theory 11(1), 3:1–3:21.
L. Lovász (1967). Operations with structures. Acta Mathematica Academiae Scientiarum Hungarica 18(3-4), 321–328.
László Lovász (2012). Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society.
Barnaby Martin & Daniël Paulusma (2015). The computational complexity of disconnected cut and 2K2-partition. J. Comb. Theory, Ser. B 111, 17–37.
Michael Pinsker (2002). Rosenberg’s classification of maximal clones. arXiv math/0211420.
B.A. Romov (1981). The algebras of partial functions and their invariants. Cybernetics 17, 157–167.
Marko Samer & Stefan Szeider (2011). Tractable cases of the extended global cardinality constraint. Constraints An Int. J. 16(1), 1–24.
Vitaly I. Voloshin (1995). On the upper chromatic number of a hypergraph. Australas. J Comb. 11, 25–46.
Dmitriy Zhuk (2020). A Proof of the CSP Dichotomy Conjecture. J. ACM 67(5), 30:1–30:78.
Dmitriy Zhuk (2021). No-Rainbow Problem and the Surjective Constraint Satisfaction Problem. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, 1–7. IEEE.
Acknowledgements
The author kindly thanks Barny Martin, Dmitriy Zhuk, and Benoit Larose for useful discussions. The former two are thanked for explanations concerning their results (Martin & Paulusma 2015; Zhuk 2021), respectively. The author also thanks Victor Lagerkvist and Moritz Müller for helpful comments. The author acknowledges the support of EPSRC grants EP/V039318/1 and EP/X03190X/1.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Chen, H. Algebraic Global Gadgetry for Surjective Constraint Satisfaction. comput. complex. 33, 7 (2024). https://doi.org/10.1007/s00037-024-00253-4
Received:
Published:
DOI: https://doi.org/10.1007/s00037-024-00253-4