4 results
Now showing1 - 4 of 4
- 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: 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 , Symmetries of graphs and structures that fail to interpret a finite thingWe 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: Conference Paper26 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Constraint Satisfaction Problems over Finite Structures(2021-06-29); ; We initiate a systematic study of the computational complexity of the Constraint Satisfaction Problem (CSP) over finite structures that may contain both relations and operations. We show the close connection between this problem and a natural algebraic question: which finite algebras admit only polynomially many homomorphisms into themWe give some sufficient and some necessary conditions for a finite algebra to have this property. In particular, we show that every finite equationally nontrivial algebra has this property which gives us, as a simple consequence, a complete complexity classification of CSPs over two-element structures, thus extending the classification for two-element relational structures by Schaefer (STOC'78).We also present examples of two-element structures that have bounded width but do not have relational width (2,3), thus demonstrating that, from a descriptive complexity perspective, allowing operations leads to a richer theory.Publicationtype: Conference Paper29