 |
 |
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
Classifications
Mathematics Subject Classification 20201
Sources:
- [1] zbMATH Open.
Bibliographic References
56 Documents citing this article
- Andrei A. Bulatov, 2024, Graphs of finite algebras: maximality, rectangularity, and decomposition, Algebra Universalis, 85, 4, 10.1007/s00012-024-00874-4.
- Andrei A. Bulatov
, 2024, Graphs of finite algebras: edges, and connectivity, Algebra Universalis, 85, 4, 10.1007/s00012-024-00865-5. - Demian Banakh;Marcin Kozik, 2024, Injective hardness condition for PCSPs, arXiv (Cornell University), pp. 1-10, 10.1145/3661814.3662072, http://arxiv.org/abs/2405.10774.
- Libor Barto;Bertalan Bodor;Marcin Kozik;Antoine Mottet;Michael Pinsker, 2023, Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing, Homo Politicus (Academy of Humanities and Economics in Lodz), pp. 1-13, 10.1109/lics56636.2023.10175732, https://ruj.uj.edu.pl/xmlui/handle/item/326045.
- 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, 2022, Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep, 2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL), pp. 80-87, 10.1109/ismvl52857.2022.00019.
- Antoine Mottet;Tomáš Nagy;Michael Pinsker;Michał Wrona, 2021, Smooth Approximations and Relational Width Collapses, Leibniz-Zentrum für Informatik (Schloss Dagstuhl), pp. 20-, 10.4230/lipics.icalp.2021.138, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.138.
- Libor Barto;Zarathustra Brady;Andrei Bulatov;Marcin Kozik;Dmitriy Zhuk, 2021, Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP, arXiv (Cornell University), 10.1109/lics52264.2021.9470557, https://arxiv.org/pdf/2104.11808.pdf.
- 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.
- 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), SIAM Journal on Computing, 49, 2, pp. 365-393, 10.1137/18m1216213.
- 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, Algebra Universalis, 80, 1, 10.1007/s00012-019-0580-x.
- Claude Tardif;Marcin Wrochna, 2019, Hedetniemi's Conjecture and Strongly Multiplicative Graphs, arXiv (Cornell University), 33, 4, pp. 2218-2250, 10.1137/19m1245013, http://arxiv.org/abs/1808.04778.
- Libor Barto;Libor Barto, 2019, Promises Make Finite (Constraint Satisfaction) Problems Infinitary, arXiv (Cornell University), abs 1811 970, pp. 1-8, 10.1109/lics.2019.8785671, http://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, http://arxiv.org/abs/1712.01731.
- Miroslav Olšák, 2019, Loop conditions for strongly connected digraphs, International Journal of Algebra and Computation, 30, 03, pp. 467-499, 10.1142/s0218196720500083.
- Miroslav Olšák, 2019, Loop conditions, Algebra Universalis, 81, 1, 10.1007/s00012-019-0631-3.
- 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, 2018, Absorption and directed Jónsson terms, Homo Politicus (Academy of Humanities and Economics in Lodz), pp. 203-220, 10.1007/978-3-319-74772-9_7, https://ruj.uj.edu.pl/xmlui/handle/item/55389.
- Andrei A. Bulatov, 2018, Constraint Satisfaction Problems: Complexity and Algorithms, Lecture notes in computer science, pp. 1-25, 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.
- 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, http://arxiv.org/abs/1704.02099.
- Mike Behrisch;Edith Vargas-García;Dmitriy Zhuk;Mike Behrisch;Edith Vargas-García;et al., 2018, The Number of Clones Determined by Disjunctions of Unary Relations, Theory of Computing Systems, 63, 6, pp. 1298-1313, 10.1007/s00224-018-9905-y, https://doi.org/10.1007/s00224-018-9905-y.
- Andrei A. Bulatov, 2017, A Dichotomy Theorem for Nonuniform CSPs, arXiv (Cornell University), pp. 319-330, 10.1109/focs.2017.37, http://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.
- Manuel Bodirsky;Marcello Mamino, 2017, Tropically Convex Constraint Satisfaction, Theory of Computing Systems, 62, 3, pp. 481-509, 10.1007/s00224-017-9762-0.
- Miroslav Olšák;Miroslav Olšák, 2017, The weakest nontrivial idempotent equations, arXiv (Cornell University), 49, 6, pp. 1028-1047, 10.1112/blms.12097, http://arxiv.org/abs/1609.00531.
- Adrien Matricon;David Filliat;Pierre-Yves Oudeyer, 2016, An iterative algorithm for forward-parameterized skill discovery, 2016 Joint IEEE International Conference on Development and Learning and Epigenetic Robotics (ICDL-EpiRob), 4, pp. 186-192, 10.1109/devlrn.2016.7846816.
- Alexander Wires, 2016, On finite Taylor algebras, International Journal of Algebra and Computation, 26, 08, pp. 1547-1571, 10.1142/s0218196716500685.
- Andrei A. Bulatov, 2016, Graphs of relational structures, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 642-651, 10.1145/2933575.2933604.
- 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, 2016, The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 615-622, 10.1145/2933575.2934544.
- Manuel Bodirsky;Antoine Mottet, 2016, Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 623-632, 10.1145/2933575.2934515.
- 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, Dichotomy for finite tournaments of mixed-type, Discrete Mathematics, 338, 12, pp. 2523-2538, 10.1016/j.disc.2015.06.024.
- 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.
- Bartek Klin;Eryk Kopczynski;Joanna Ochremiak;Szymon Torunczyk, 2015, Locally Finite Constraint Satisfaction Problems, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, abs 1203 1876, pp. 475-486, 10.1109/lics.2015.51.
- 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, Homo Politicus (Academy of Humanities and Economics in Lodz), 74, 1-2, pp. 185-206, 10.1007/s00012-015-0338-z, http://ruj.uj.edu.pl/xmlui/handle/item/22434.
- Marcin Kozik;Andrei Krokhin;Matt Valeriote;Ross Willard, 2015, Characterizations of several Maltsev conditions, Homo Politicus (Academy of Humanities and Economics in Lodz), 73, 3-4, pp. 205-224, 10.1007/s00012-015-0327-2, http://ruj.uj.edu.pl/xmlui/handle/item/19551.
- Marcin Kozik;Joanna Ochremiak;Marcin Kozik;Joanna Ochremiak, 2015, Algebraic Properties of Valued Constraint Satisfaction Problem, arXiv (Cornell University), pp. 846-858, 10.1007/978-3-662-47672-7_69, http://arxiv.org/abs/1403.0476.
- Matt Valeriote, 2015, Algebras and Algorithms, 2015 IEEE International Symposium on Multiple-Valued Logic, 78, pp. 1, 10.1109/ismvl.2015.45.
- 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.
- Gergő Gyenizse;Miklós Maróti;László Zádori, 2014, The structure of polynomial operations associated with smooth digraphs, Algebra Universalis, 72, 4, pp. 381-391, 10.1007/s00012-014-0309-9.
- 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 Kearnes;Petar Marković;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.
- Libor Barto, 2014, The collapse of the bounded width hierarchy, Journal of Logic and Computation, 26, 3, pp. 923-943, 10.1093/logcom/exu070.
- Dmitriy N. Zhuk, 2013, The existence of a near-unanimity function is decidable, Algebra Universalis, 71, 1, pp. 31-54, 10.1007/s00012-013-0259-7.
- Libor Barto;Marcin Kozik;Ross Willard, 2012, Near Unanimity Constraints Have Bounded Pathwidth Duality, Homo Politicus (Academy of Humanities and Economics in Lodz), 113, pp. 125-134, 10.1109/lics.2012.24, http://ruj.uj.edu.pl/xmlui/handle/item/1977.
Share and export
Consultation statistics
This page has been seen 3191 times.
This article's PDF has been downloaded 505 times.