 |
 |
Libor Barto ; Marcin Kozik - Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
lmcs:673 - Logical Methods in Computer Science, February 20, 2012, Volume 8, Issue 1 - https://doi.org/10.2168/LMCS-8(1:7)2012Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction
ProblemArticle
Authors: Libor Barto ; Marcin Kozik NULL##NULLLibor Barto;Marcin Kozik
The Algebraic Dichotomy Conjecture states that the Constraint Satisfaction Problem over a fixed template is solvable in polynomial time if the algebra of polymorphisms associated to the template lies in a Taylor variety, and is NP-complete otherwise. This paper provides two new characterizations of finitely generated Taylor varieties. The first characterization is using absorbing subalgebras and the second one cyclic terms. These new conditions allow us to reprove the conjecture of Bang-Jensen and Hell (proved by the authors) and the characterization of locally finite Taylor varieties using weak near-unanimity terms (proved by McKenzie and Maróti) in an elementary and self-contained way.
Source: arXiv.org:1201.0557
Volume: Volume 8, Issue 1
Published on: February 20, 2012
Imported on: December 30, 2010
Keywords: Computer Science - Logic in Computer Science,F.2.2, F.4.1
Bibliographic References
60 Documents citing this article
- Libor Barto
;Bertalan Bodor;Marcin Kozik;Antoine Mottet;Michael Pinsker, 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing, 2023, Boston, MA, USA, 10.1109/lics56636.2023.10175732. - Clifford Bergman;William DeMeo, 2022, Universal Algebraic Methods for Constraint Satisfaction Problems, Logical Methods in Computer Science, Volume 18, Issue 1, 10.46298/lmcs-18(1:12)2022, https://doi.org/10.46298/lmcs-18(1:12)2022.
- Michael Pinsker, arXiv (Cornell University), Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep, 168, pp. 80-87, 2022, Dallas, TX, USA, 10.1109/ismvl52857.2022.00019, https://arxiv.org/abs/2203.17182.
- Antoine Mottet;Tomáš Nagy;Michael Pinsker;Michał Wrona, International Colloquium on Automata, Languages and Programming, Smooth Approximations and Relational Width Collapses, pp. 20-, 2021, 10.4230/lipics.icalp.2021.138.
- Libor Barto;Jakub Bulín;Andrei Krokhin;Jakub Opršal, 2021, Algebraic Approach to Promise Constraint Satisfaction, Journal of the ACM, 68, 4, pp. 1-66, 10.1145/3457606, https://doi.org/10.1145/3457606.
- Libor Barto;Zarathustra Brady;Andrei Bulatov;Marcin Kozik;Dmitriy Zhuk, arXiv (Cornell University), Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP, 2021, Rome, Italy, 10.1109/lics52264.2021.9470557, http://arxiv.org/abs/2104.11808.
- Manuel Bodirsky;Florent Madelaine;Antoine Mottet, 2021, A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP, SIAM Journal on Computing, 50, 4, pp. 1359-1409, 10.1137/19m128466x.
- Pavol Hell;Jaroslav Nešetřil, 2021, In praise of homomorphisms, Computer Science Review, 40, pp. 100352, 10.1016/j.cosrev.2020.100352.
- Thodsaporn Kumduang;Sorasak Leeratanavalee, 2021, Menger systems of idempotent cyclic and weak near-unanimity multiplace functions, Asian-European Journal of Mathematics, 15, 09, 10.1142/s1793557122501625.
- Dmitriy Zhuk, 2020, A Proof of the CSP Dichotomy Conjecture, arXiv (Cornell University), 67, 5, pp. 1-78, 10.1145/3402029, http://arxiv.org/abs/1704.01914.
- Ian Payne, 2020, Some structural and residual properties of 2-semilattices, Algebra Universalis, 81, 4, 10.1007/s00012-020-00682-6.
- Libor Barto;Michael Pinsker, 2020, Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems), arXiv (Cornell University), 49, 2, pp. 365-393, 10.1137/18m1216213, https://arxiv.org/abs/1909.06201.
- Manuel Bodirsky;Thomas Quinn-Gregson, 2020, Solving equation systems in ω-categorical algebras, Journal of Mathematical Logic, 21, 03, 10.1142/s0219061321500203.
- Miroslav Olšák, 2020, The local loop lemma, Algebra Universalis, 81, 2, 10.1007/s00012-020-0644-y, https://doi.org/10.1007/s00012-020-0644-y.
- Alexandr Kazda, 2019, Taylor term does not imply any nontrivial linear one-equality Maltsev condition, arXiv (Cornell University), 80, 1, 10.1007/s00012-019-0580-x, https://arxiv.org/abs/1706.01147.
- Claude Tardif;Marcin Wrochna, 2019, Hedetniemi's Conjecture and Strongly Multiplicative Graphs, arXiv (Cornell University), 33, 4, pp. 2218-2250, 10.1137/19m1245013, https://arxiv.org/abs/1808.04778.
- Libor Barto, arXiv (Cornell University), Promises Make Finite (Constraint Satisfaction) Problems Infinitary, 2019, Vancouver, BC, Canada, 10.1109/lics.2019.8785671, https://arxiv.org/abs/1909.04878.
- Libor Barto;Ondřej Draganov, 2019, The minimal arity of near unanimity polymorphisms, arXiv (Cornell University), 69, 2, pp. 297-310, 10.1515/ms-2017-0223, https://arxiv.org/abs/1712.01731.
- Miroslav Olšák, 2019, Loop conditions, Algebra Universalis, 81, 1, 10.1007/s00012-019-0631-3.
- Miroslav Olšák, 2019, Loop conditions for strongly connected digraphs, International Journal of Algebra and Computation, 30, 03, pp. 467-499, 10.1142/s0218196720500083.
- Pierre Gillibert;Julius Jonušas;Michael Pinsker, 2019, Pseudo‐loop conditions, Bulletin of the London Mathematical Society, 51, 5, pp. 917-936, 10.1112/blms.12286, https://doi.org/10.1112/blms.12286.
- Alexandr Kazda;Marcin Kozik;Ralph McKenzie;Matthew Moore, arXiv (Cornell University), Absorption and directed Jónsson terms, pp. 203-220, 2018, 10.1007/978-3-319-74772-9_7, https://arxiv.org/abs/1502.01072.
- Andrei A. Bulatov, Lecture notes in computer science, Constraint Satisfaction Problems: Complexity and Algorithms, pp. 1-25, 2018, 10.1007/978-3-319-77313-1_1.
- Andrei A. Bulatov, 2018, Constraint satisfaction problems, ACM SIGLOG News, 5, 4, pp. 4-24, 10.1145/3292048.3292050, https://doi.org/10.1145/3292048.3292050.
- Lucy Ham;Marcel Jackson, 2018, Axiomatisability and hardness for universal Horn classes of hypergraphs, arXiv (Cornell University), 79, 2, 10.1007/s00012-018-0515-y, https://arxiv.org/abs/1704.02099.
- Mike Behrisch;Edith Vargas-García;Dmitriy Zhuk, 2018, The Number of Clones Determined by Disjunctions of Unary Relations, arXiv (Cornell University), 63, 6, pp. 1298-1313, 10.1007/s00224-018-9905-y, https://arxiv.org/abs/1811.11737.
- Andrei A. Bulatov, arXiv (Cornell University), A Dichotomy Theorem for Nonuniform CSPs, 2017, Berkeley, CA, 10.1109/focs.2017.37, https://arxiv.org/abs/1703.03021.
- Jakub Bulín, 2017, On the complexity of H-coloring for special oriented trees, European Journal of Combinatorics, 69, pp. 54-75, 10.1016/j.ejc.2017.10.001, https://doi.org/10.1016/j.ejc.2017.10.001.
- Libor Barto;Jakub Bulín, 2017, Deciding absorption in relational structures, arXiv (Cornell University), 78, 1, pp. 3-18, 10.1007/s00012-017-0440-5, http://arxiv.org/abs/1601.06450.
- Manuel Bodirsky;Marcello Mamino, 2017, Tropically Convex Constraint Satisfaction, arXiv (Cornell University), 62, 3, pp. 481-509, 10.1007/s00224-017-9762-0, https://arxiv.org/abs/1506.04184.
- Miroslav Olšák, 2017, The weakest nontrivial idempotent equations, arXiv (Cornell University), 49, 6, pp. 1028-1047, 10.1112/blms.12097, https://arxiv.org/abs/1609.00531.
- Vladimir Kolmogorov;Andrei Krokhin;Michal Rolínek, 2017, The Complexity of General-Valued CSPs, SIAM Journal on Computing, 46, 3, pp. 1087-1110, 10.1137/16m1091836, https://dro.dur.ac.uk/18078/.
- Adrien Matricon;David Filliat;Pierre-Yves Oudeyer, An iterative algorithm for forward-parameterized skill discovery, 4, pp. 186-192, 2016, Cergy-Pontoise, France, 10.1109/devlrn.2016.7846816, https://hal.archives-ouvertes.fr/hal-01370820.
- Alexander Wires, 2016, On finite Taylor algebras, International Journal of Algebra and Computation, 26, 08, pp. 1547-1571, 10.1142/s0218196716500685.
- Andrei A. Bulatov, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, Graphs of relational structures, 71, pp. 642-651, 2016, New York NY USA, 10.1145/2933575.2933604.
- Catarina Carvalho;Andrei Krokhin, 2016, On algebras with many symmetric operations, University of Hertfordshire Research Archive (University of Hertfordshire), 26, 05, pp. 1019-1031, 10.1142/s0218196716500429, https://hdl.handle.net/2299/19798.
- Libor Barto;Alexandr Kazda, 2016, Deciding absorption, International Journal of Algebra and Computation, 26, 05, pp. 1033-1060, 10.1142/s0218196716500430.
- Libor Barto;Michael Pinsker, arXiv (Cornell University), The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems, 2016, New York NY USA, 10.1145/2933575.2934544, https://arxiv.org/abs/1602.04353.
- Manuel Bodirsky;Antoine Mottet, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction, 2016, New York NY USA, 10.1145/2933575.2934515.
- Marcel Jackson;Tomasz Kowalski;Todd Niven, 2016, Complexity and polymorphisms for digraph constraint problems under some basic constructions, arXiv (Cornell University), 26, 07, pp. 1395-1433, 10.1142/s0218196716500600, https://arxiv.org/abs/1304.4986.
- Mike Behrisch, 2016, Galois theory for semiclones, Algebra Universalis, 76, 3, pp. 385-413, 10.1007/s00012-016-0407-y, https://doi.org/10.1007/s00012-016-0407-y.
- Alexander Wires, 2015, A quasi-Mal’cev condition with unexpected application, Algebra Universalis, 73, 3-4, pp. 335-346, 10.1007/s00012-015-0322-7.
- Alexander Wires, 2015, Dichotomy for finite tournaments of mixed-type, Discrete Mathematics, 338, 12, pp. 2523-2538, 10.1016/j.disc.2015.06.024, https://doi.org/10.1016/j.disc.2015.06.024.
- Bartek Klin;Eryk Kopczynski;Joanna Ochremiak;Szymon Torunczyk, CiteSeer X (The Pennsylvania State University), Locally Finite Constraint Satisfaction Problems, 2015, Kyoto, Japan, 10.1109/lics.2015.51, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.702.3798.
- George F. McNulty, 2015, A juggler’s dozen of easy† problems, Algebra Universalis, 74, 1-2, pp. 17-34, 10.1007/s00012-015-0333-4.
- Jonah Horowitz, 2015, Testing for edge terms is decidable, Algebra Universalis, 73, 3-4, pp. 321-334, 10.1007/s00012-015-0325-4.
- LIBOR BARTO, 2015, THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA, Bulletin of Symbolic Logic, 21, 3, pp. 319-337, 10.1017/bsl.2015.25.
- Libor Barto;Marcin Kozik;David Stanovský, 2015, Mal’tsev conditions, lack of absorption, and solvability, CiteSeer X (The Pennsylvania State University), 74, 1-2, pp. 185-206, 10.1007/s00012-015-0338-z, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.433.7908.
- Marcin Kozik;Andrei Krokhin;Matt Valeriote;Ross Willard, 2015, Characterizations of several Maltsev conditions, Durham Research Online (Durham University), 73, 3-4, pp. 205-224, 10.1007/s00012-015-0327-2, https://dro.dur.ac.uk/21179/1/21179.pdf.
- Marcin Kozik;Joanna Ochremiak, arXiv (Cornell University), Algebraic Properties of Valued Constraint Satisfaction Problem, pp. 846-858, 2015, 10.1007/978-3-662-47672-7_69, http://arxiv.org/abs/1403.0476.
- Matt Valeriote, 2015 IEEE International Symposium on Multiple-Valued Logic, Algebras and Algorithms, 2015, Waterloo, ON, Canada, 10.1109/ismvl.2015.45.
- Vladimir Kolmogorov;Andrei Krokhin;Michal Rolinek, Durham Research Online (Durham University), The Complexity of General-Valued CSPs, 2015, Berkeley, CA, USA, 10.1109/focs.2015.80, https://dro.dur.ac.uk/18078/.
- Anna Huber;Andrei A. Krokhin;Robert Powell, 2014, Skew Bisubmodularity and Valued CSPs, SIAM Journal on Computing, 43, 3, pp. 1064-1084, 10.1137/120893549, https://dro.dur.ac.uk/12578/1/12578.pdf.
- Gergő Gyenizse;Miklós Maróti;László Zádori, 2014, The structure of polynomial operations associated with smooth digraphs, SZTE Publicatio Repozitórium (University of Szeged), 72, 4, pp. 381-391, 10.1007/s00012-014-0309-9, https://publicatio.bibl.u-szeged.hu/15001/1/publ28.pdf.
- Jakub Bulín, 2014, Decidability of absorption in relational structures of bounded width, Algebra Universalis, 72, 1, pp. 15-28, 10.1007/s00012-014-0283-2.
- Keith A. Kearnes;Petar Markovic;Ralph McKenzie, 2014, Optimal strong Mal’cev conditions for omitting type 1 in locally finite varieties, Algebra Universalis, 72, 1, pp. 91-100, 10.1007/s00012-014-0289-9.
- Libor Barto, 2014, Constraint satisfaction problem and universal algebra, ACM SIGLOG News, 1, 2, pp. 14-24, 10.1145/2677161.2677165, https://doi.org/10.1145/2677161.2677165.
- Libor Barto, 2014, The collapse of the bounded width hierarchy, CiteSeer X (The Pennsylvania State University), 26, 3, pp. 923-943, 10.1093/logcom/exu070, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.434.7970.
- Dmitriy N. Zhuk, 2013, The existence of a near-unanimity function is decidable, arXiv (Cornell University), 71, 1, pp. 31-54, 10.1007/s00012-013-0259-7, https://arxiv.org/abs/1108.1671.
- Libor Barto;Marcin Kozik;Ross Willard, 2012 27th Annual IEEE Symposium on Logic in Computer Science, Near Unanimity Constraints Have Bounded Pathwidth Duality, 113, pp. 125-134, 2012, Dubrovnik, Croatia, 10.1109/lics.2012.24.
Share and export
Consultation statistics
This page has been seen 1620 times.
This article's PDF has been downloaded 379 times.