14 results
Filters
Settings
Now showing1 - 10 of 14
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Symmetries of graphs and structures that fail to interpret a finite thing(World Scientific, 2026-10-29); ; ; ; In this paper, we investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters or orbits, every finite structure. Our results generalize several theorems from the literature and yield further algebraic invariance properties that must be satisfied in every such graph. Algebraic properties of this kind are tightly connected to the tractability of constraint satisfaction problems, and we obtain new such properties even for infinite countably categorical graphs. We balance these positive results by showing the existence of a countably categorical hypergraph that fails to interpret some finite structure, while still lacking some of the most essential algebraic invariance properties known to hold for finite structures.Publicationtype: Journal Article5 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Equations over finite monoids with infinite promises(Association for Computing Machinery (ACM), 2026-06-19); ; Larrauri and Živný [ICALP’24/ACM ToCL’24] recently established a complete complexity classification of the problem of solving a system of equations over a monoid N assuming that a solution exists over a monoid M, where both monoids are finite and M admits a homomorphism to N. Using the algebraic approach to promise constraint satisfaction problems, we extend their complexity classification in two directions: we obtain a complexity dichotomy in the case where arbitrary relations are added to the monoids, and we moreover allow the monoid M to be finitely generated.Publicationtype: Journal Article17 6 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , A preservation theorem for valued structures(2026-02-06); ; 19 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Algebraic and algorithmic synergies between promise and infinite-domain CSPsWe establish a framework that allows us to transfer results between some constraint satisfaction problems with infinite templates and promise constraint satisfaction problems. On the one hand, we obtain new algebraic results for infinite-domain CSPs giving new criteria for NP-hardness. On the other hand, we show the existence of promise CSPs with finite templates that reduce naturally to tractable infinite-domain CSPs in the scope of the Bodirsky-Pinsker conjecture, but that are not finitely tractable, thereby showing a non-trivial connection between those two fields of research. In an important part of our proof, we also obtain uniform polynomial-time algorithms solving temporal constraint satisfaction problems.Publicationtype: Conference Paper31 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Finite algebras with hom-sets of polynomal sizeWe provide an internal characterization of those finite algebras (i.e., algebraic structures) A such that the number of homomorphisms from any finite algebra X to A is bounded from above by a polynomial in the size of X. Namely, an algebra A has this property if, and only if, no subalgebra of A has a nontrivial strongly abelian congruence. We also show that the property can be decided in polynomial time for algebras in finite signatures. Moreover, if A is such an algebra, the set of all homomorphisms from X to A can be computed in polynomial time given X as input. As an application of our results to the field of computational complexity, we characterize inherently tractable constraint satisfaction problems over fixed finite structures, i.e., those that are tractable and remain tractable after expanding the fixed structure by arbitrary relations or functions.Publicationtype: Journal Article25 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough(Society for Industrial & Applied Mathematics (SIAM), 2024-12-11); ; ; We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities n>3) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain constraint satisfaction problems (CSPs) studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of Monotone Monadic SNP (MMSNP) sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu et al. In particular, the bounded width hierarchy collapses in those cases as well. Our results extend the scope of theorems of Barto and Kozik characterizing bounded width for finite structures and show the applicability of infinite-domain CSPs to other fields.Publicationtype: Journal Article17 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Smooth approximations : an algebraic approach to CSPs over finitely bounded homogeneous structuresWe introduce the novel machinery of smooth approximations to provide a systematic algebraic approach to the complexity of CSPs over finitely bounded homogeneous structures. We apply smooth approximations to confirm the CSP dichotomy conjecture for first-order reducts of the random tournament and to give new short proofs of the conjecture for various homogeneous graphs including the random graph (STOC'11, ICALP'16, JACM 2015, SICOMP 2019), and for expansions of the order of the rationals (STOC'08, JACM 2009). Apart from obtaining these dichotomy results, we show how our new proof technique allows one to unify and significantly simplify the previous results from the literature. For all but the last structure, we moreover characterize for the first time those CSPs that are solvable by local consistency methods, again using the same machinery.Publicationtype: Journal Article14 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Generalized completion problems with forbidden tournaments(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2024-08-23); A recent result by Bodirsky and Guzmán-Pro gives a complexity dichotomy for the following class of computational problems, parametrized by a finite family F of finite tournaments: given an undirected graph, does there exist an orientation of the graph that avoids every tournament in F? One can see the edges of the input graphs as constraints imposing to find an orientation. In this paper, we consider a more general version of this problem where the constraints in the input are not necessarily about pairs of variables and impose local constraints on the global oriented graph to be found. Our main result is a complexity dichotomy for such problems, as well as a classification of such problems where the yes-instances have bounded treewidth duality. As a consequence, we obtain a streamlined proof of the result by Bodirsky and Guzmán-Pro using the theory of smooth approximations due to Mottet and Pinsker.Publicationtype: Conference Paper48 89 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , An order out of nowhere : a new algorithm for infinite-domain CSPs(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2024-07); ; We consider the problem of satisfiability of sets of constraints in a given set of finite uniform hypergraphs. While the problem under consideration is similar in nature to the problem of satisfiability of constraints in graphs, the classical complexity reduction to finite-domain CSPs that was used in the proof of the complexity dichotomy for such problems cannot be used as a black box in our case. We therefore introduce an algorithmic technique inspired by classical notions from the theory of finite-domain CSPs, and prove its correctness based on symmetries that depend on a linear order that is external to the structures under consideration. Our second main result is a P/NP-complete complexity dichotomy for such problems over many sets of uniform hypergraphs. The proof is based on the translation of the problem into the framework of constraint satisfaction problems (CSPs) over infinite uniform hypergraphs. Our result confirms in particular the Bodirsky-Pinsker conjecture for CSPs of first-order reducts of some homogeneous hypergraphs. This forms a vast generalization of previous work by Bodirsky-Pinsker (STOC’11) and Bodirsky-Martin-Pinsker-Pongrácz (ICALP’16) on graph satisfiability.Publicationtype: Conference Paper16 84 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Promise and infinite-domain constraint satisfactionTwo particularly active branches of research in constraint satisfaction are the study of promise constraint satisfaction problems (PCSPs) with finite templates and the study of infinite-domain constraint satisfaction problems with ω-categorical templates. In this paper, we explore some connections between these two hitherto unrelated fields and describe a general approach to studying the complexity of PCSPs by constructing suitable infinite CSP templates. As a result, we obtain new characterizations of the power of various classes of algorithms for PCSPs, such as first-order logic, arc consistency reductions, and obtain new proofs of the characterizations of the power of the classical linear and affine relaxations for PCSPs.Publicationtype: Conference Paper8