@inproceedings{bulin_reduction_2013,
address = {Berlin, Heidelberg},
series = {Lecture {Notes} in {Computer} {Science}},
title = {On the reduction of the {CSP} dichotomy conjecture to digraphs},
copyright = {All rights reserved},
isbn = {978-3-642-40627-0},
doi = {10.1007/978-3-642-40627-0_17},
abstract = {It is well known that the constraint satisfaction problem over general relational structures can be reduced in polynomial time to digraphs. We present a simple variant of such a reduction and use it to show that the algebraic dichotomy conjecture is equivalent to its restriction to digraphs and that the polynomial reduction can be made in logspace. We also show that our reduction preserves the bounded width property, i.e., solvability by local consistency methods. We discuss further algorithmic properties that are preserved and related open problems.},
language = {en},
booktitle = {Principles and {Practice} of {Constraint} {Programming}},
publisher = {Springer},
author = {Bulín, Jakub and Delić, Dejan and Jackson, Marcel and Niven, Todd},
editor = {Schulte, Christian},
year = {2013},
keywords = {Constraint Satisfaction Problem, Polynomial Time, Relation Symbol, Relational Structure, Single Edge},
pages = {184--199},
file = {Full Text PDF:files/70/Bulín et al. - 2013 - On the Reduction of the CSP Dichotomy Conjecture t.pdf:application/pdf},
}
@techreport{bodirsky_smallest_2022,
title = {The smallest hard trees},
copyright = {All rights reserved},
url = {http://arxiv.org/abs/2205.07528},
abstract = {We find an orientation of a tree with 20 vertices such that the corresponding fixed-template constraint satisfaction problem (CSP) is NP-complete, and prove that for every orientation of a tree with fewer vertices the corresponding CSP can be solved in polynomial time. We also compute the smallest tree that is NL-hard (assuming L is not NL), the smallest tree that cannot be solved by arc consistency, and the smallest tree that cannot be solved by Datalog. Our experimental results also support a conjecture of Bulin concerning a question of Hell, Nesetril and Zhu, namely that "easy trees lack the ability to count". Most proofs are computer-based and make use of the most recent universal-algebraic theory about the complexity of finite-domain CSPs. However, further ideas are required because of the huge number of orientations of trees. In particular, we use the well-known fact that it suffices to study orientations of trees that are cores and show how to efficiently decide whether a given orientation of a tree is a core using the arc-consistency procedure. Moreover, we present a method to generate orientations of trees that are cores that works well in practice. In this way we found interesting examples for the open research problem to classify finite-domain CSPs in NL.},
number = {arXiv:2205.07528},
urldate = {2022-05-17},
institution = {arXiv},
author = {Bodirsky, Manuel and Bulín, Jakub and Starke, Florian and Wernthaler, Michael},
month = may,
year = {2022},
doi = {10.48550/arXiv.2205.07528},
note = {arXiv:2205.07528 [math]
type: article},
keywords = {08A70, 08B05, G.2.2, Mathematics - Rings and Algebras},
file = {arXiv Fulltext PDF:files/77/Bodirsky et al. - 2022 - The Smallest Hard Trees.pdf:application/pdf;arXiv.org Snapshot:files/76/2205.html:text/html},
}
@inproceedings{bulin_algebraic_2019,
address = {New York},
title = {Algebraic approach to promise constraint satisfaction},
copyright = {All rights reserved},
isbn = {978-1-4503-6705-9},
url = {https://www.webofscience.com/wos/woscc/summary/1adda51d-b986-4fbf-8333-6c5432c927ff-389b7ae5/relevance/1},
doi = {10.1145/3313276.3316300},
abstract = {The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms - high-dimensional symmetries of solution spaces - to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases. The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this paper we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem, and show that every PCSP with a fixed constraint language is equivalent to a problem of this form. This allows us to identify a "measure of symmetry" that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by improving the state-of-the-art in approximate graph colouring: we show that, for any k {\textgreater}= 3, it is NP-hard to find a (2k - 1)-colouring of a given k-colourable graph.},
language = {English},
urldate = {2022-05-17},
booktitle = {Proceedings of the 51st {Annual} {Acm} {Sigact} {Symposium} on {Theory} of {Computing} (stoc '19)},
publisher = {Assoc Computing Machinery},
author = {Bulín, Jakub and Krokhin, Andrei and Opršal, Jakub},
editor = {Charikar, M. and Cohen, E.},
year = {2019},
note = {ISSN: 0737-8017
WOS:000523199100055},
keywords = {complexity, constraint satisfaction, polymorphism, approximation, graph colouring, hardness, promise problem},
pages = {602--613},
file = {Full Text:files/74/Bulin et al. - 2019 - Algebraic Approach to Promise Constraint Satisfact.pdf:application/pdf},
}
@article{barto_algebraic_2021,
title = {Algebraic approach to promise constraint satisfaction},
volume = {68},
copyright = {All rights reserved},
issn = {0004-5411},
url = {https://www.webofscience.com/wos/woscc/summary/1adda51d-b986-4fbf-8333-6c5432c927ff-389b7ae5/relevance/1},
doi = {10.1145/3457606},
abstract = {The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the past 20 years. A new version of the CSP, the promise CSP (PCSP), has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms-high-dimensional symmetries of solution spaces-to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases. The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this article, we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem and show that every PCSP with a fixed constraint language is equivalent to a problem of this form. This allows us to identify a "measure of symmetry" that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by giving both general and specific hardness/tractability results. Among other things, we improve the state-of-the-art in approximate graph colouring by showing that, for any k {\textgreater}= 3, it is NP-hard to find a (2k - 1)-colouring of a given k-colourable graph.},
language = {English},
number = {4},
urldate = {2022-05-17},
journal = {Journal of the Acm},
author = {Barto, Libor and Bulín, Jakub and Krokhin, Andrei and Opršal, Jakub},
month = aug,
year = {2021},
note = {Place: New York
Publisher: Assoc Computing Machinery
WOS:000744649100007},
keywords = {complexity, polymorphism, approximation, graph colouring, hardness, promise problem, chromatic number, conjecture, Constraint satisfaction, systems},
pages = {28},
file = {Full Text:files/75/Barto et al. - 2021 - Algebraic Approach to Promise Constraint Satisfact.pdf:application/pdf},
}
@article{bulin_finer_2015,
title = {A finer reduction of constraint problems to digraphs},
volume = {11},
copyright = {All rights reserved},
issn = {1860-5974},
url = {https://www.webofscience.com/wos/woscc/summary/1adda51d-b986-4fbf-8333-6c5432c927ff-389b7ae5/relevance/1},
doi = {10.2168/LMCS-11(4:18)2015},
abstract = {It is well known that the constraint satisfaction problem over a general relational structure A is polynomial time equivalent to the constraint problem over some associated digraph. We present a variant of this construction and show that the corresponding constraint satisfaction problem is logspace equivalent to that over A. Moreover, we show that almost all of the commonly encountered polymorphism properties are held equivalently on the A and the constructed digraph. As a consequence, the Algebraic CSP dichotomy conjecture as well as the conjectures characterizing CSPs solvable in logspace and in nondeterministic logspace are equivalent to their restriction to digraphs.},
language = {English},
number = {4},
urldate = {2022-05-17},
journal = {Logical Methods in Computer Science},
author = {Bulín, Jakub and Delić, Dejan and Jackson, Marcel and Niven, Todd},
year = {2015},
note = {Place: Braunschweig
Publisher: Logical Methods Computer Science E V
WOS:000373922900018},
keywords = {constraint satisfaction problem, complexity, polymorphism, dichotomy, dichotomy conjecture, directed graph, satisfaction},
pages = {18},
file = {Full Text:files/73/Bulin et al. - 2015 - A Finer Reduction of Constraint Problems to Digrap.pdf:application/pdf},
}
@article{barto_csp_2013,
title = {{CSP} dichotomy for special polyads},
volume = {23},
copyright = {All rights reserved},
issn = {0218-1967},
url = {https://www.worldscientific.com/doi/abs/10.1142/S0218196713500215},
doi = {10.1142/S0218196713500215},
abstract = {For a digraph ℍ, the Constraint Satisfaction Problem with template ℍ, or CSP(ℍ), is the problem of deciding whether a given input digraph 𝔾 admits a homomorphism to ℍ. The CSP dichotomy conjecture of Feder and Vardi states that for any digraph ℍ, CSP(ℍ) is either in P or NP-complete. Barto, Kozik, Maróti and Niven (Proc. Amer. Math. Soc.137 (2009) 2921–2934) confirmed the conjecture for a class of oriented trees called special triads. We generalize this result, establishing the dichotomy for a class of oriented trees which we call special polyads. We prove that every tractable special polyad has bounded width and provide the description of special polyads of width 1. We also construct a tractable special polyad which neither has width 1 nor admits any near-unanimity polymorphism.},
number = {05},
urldate = {2022-05-17},
journal = {International Journal of Algebra and Computation},
author = {Barto, Libor and Bulín, Jakub},
month = aug,
year = {2013},
note = {Publisher: World Scientific Publishing Co.},
keywords = {graph coloring, bounded width, Constraint satisfaction problem, special triad},
pages = {1151--1174},
file = {Full Text PDF:files/68/Barto and Bulín - 2013 - Csp dichotomy for special polyads.pdf:application/pdf},
}
@article{bulin_complexity_2018,
title = {On the complexity of {H}-coloring for special oriented trees},
volume = {69},
copyright = {All rights reserved},
issn = {0195-6698},
url = {https://www.sciencedirect.com/science/article/pii/S0195669817301609},
doi = {10.1016/j.ejc.2017.10.001},
abstract = {For a fixed digraph H, the H-coloring problem is the problem of deciding whether a given input digraph G admits a homomorphism to H. The CSP dichotomy conjecture of Feder and Vardi is equivalent to proving that, for any H, the H-coloring problem is in P or NP-complete. We confirm this dichotomy for a certain class of oriented trees, which we call special trees (generalizing earlier results on special triads and polyads). Moreover, we prove that every tractable special oriented tree has bounded width, i.e., the corresponding H-coloring problem is solvable by local consistency checking. Our proof relies on recent algebraic tools, namely characterization of congruence meet-semidistributivity via pointing operations and absorption theory.},
language = {en},
urldate = {2022-05-17},
journal = {European Journal of Combinatorics},
author = {Bulín, Jakub},
month = mar,
year = {2018},
pages = {54--75},
file = {Full Text:files/69/Bulín - 2018 - On the complexity of H-coloring for special orient.pdf:application/pdf},
}
@article{barto_deciding_2017,
title = {Deciding absorption in relational structures},
volume = {78},
copyright = {All rights reserved},
issn = {1420-8911},
url = {https://doi.org/10.1007/s00012-017-0440-5},
doi = {10.1007/s00012-017-0440-5},
abstract = {We prove that for finite, finitely related algebras, the concepts of an absorbing subuniverse and a J´onsson absorbing subuniverse coincide. Consequently, it is decidable whether a given subset is an absorbing subuniverse of the polymorphism algebra of a given relational structure.},
language = {en},
number = {1},
urldate = {2022-05-17},
journal = {Algebra universalis},
author = {Barto, Libor and Bulín, Jakub},
month = sep,
year = {2017},
keywords = {absorbing subalgebra, 08A70, congruence distributivity, finitely related algebra, Jónsson absorbing subalgebra, near unanimity, Primary: 08A05, Secondary: 08B10},
pages = {3--18},
file = {Full Text PDF:files/71/Barto and Bulín - 2017 - Deciding absorption in relational structures.pdf:application/pdf},
}
@article{bulin_decidability_2014,
title = {Decidability of absorption in relational structures of bounded width},
volume = {72},
copyright = {All rights reserved},
issn = {1420-8911},
url = {https://doi.org/10.1007/s00012-014-0283-2},
doi = {10.1007/s00012-014-0283-2},
abstract = {The absorption theory of Barto and Kozik has proven to be a very useful tool in the algebraic approach to the Constraint Satisfaction Problem and the structure of finite algebras in general. We address the following problem: Given a finite relational structure \$\$\{{\textbackslash}mathbb\{A\}\}\$\$and a subset \$\$\{B {\textbackslash}subseteq A\}\$\$, is it decidable whether B is an absorbing subuniverse? We provide an affirmative answer in the case when \$\$\{{\textbackslash}mathbb\{A\}\}\$\$has bounded width (i.e., the algebra of polymorphisms of \$\$\{{\textbackslash}mathbb\{A\}\}\$\$generates a congruence meet semidistributive variety). As a by-product, we confirm that in this case the notion of Jónsson absorption coincides with the usual absorption. We also show that several open questions about absorption in relational structures can be reduced to digraphs.},
language = {en},
number = {1},
urldate = {2022-05-17},
journal = {Algebra universalis},
author = {Bulín, Jakub},
month = aug,
year = {2014},
keywords = {Primary: 08B05, 08A70, bounded width, finitely related algebra, Secondary: 08B10, absorbing subuniverse, congruence meet semidistributivity, constraint satisfactionproblem, Jónsson operations, near unanimity operation},
pages = {15--28},
file = {Full Text PDF:files/72/Bulín - 2014 - Decidability of absorption in relational structure.pdf:application/pdf},
}