Graphs of relational structures: restricted types

DOI10.1145/2933575.2933604MaRDI QIDQ4635925zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov

Publication date 23 April 2018

Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.11713

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Applications of universal algebra in computer science (08A70) Analysis of algorithms and problem complexity (68Q25)

Abstract: The algebraic approach to the Constraint Satisfaction Problem (CSP) uses high order symmetries of relational structures -- polymorphisms -- to study the complexity of the CSP. In this paper we further develop one of the methods the algebraic approach can be implemented, and apply it to some kinds of the CSP. This method was introduced in our LICS 2004 paper and involves the study of the local structure of finite algebras and relational structures. It associates with an algebra A or a relational structure S a graph, whose vertices are the elements of A (or S), the edges represent subsets of A such that the restriction of some term operation of A is `good' on the subset, that is, act as an operation of one of the 3 types: semilattice, majority, or affine. In this paper we use this theory and consider algebras with edges from a restricted set of types. We prove type restrictions are preserved under the standard algebraic constructions. Then we show that if the types edges in a relational structure are restricted, then the corresponding CSP can be solved in polynomial time by specific algorithms. In particular, we give a new, somewhat more intuitive proof of the Bounded Width Theorem: the CSP over algebra A has bounded width if and only if A does not contain affine edges. Actually, this result shows that bounded width implies width (2,3). Finally, we prove that algebras without semilattice edges have few subalgebras of powers, that is, the CSP over such algebras is also polynomial time. The methods and results obtained in this paper are important ingredients of the 2017 proof of the Dichotomy Conjecture by the author. The Dichotomy Conjecture was also proved independently by Zhuk.

Recommendations

• Bounded width problems and algebras
• OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
• Decidability of absorption in relational structures of bounded width.
• Varieties with few subalgebras of powers
• CSP for binary conservative relational structures

Cited in

(14)

• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
• On the width of regular classes of finite structures
• Decidability of absorption in relational structures of bounded width.
• CSP for binary conservative relational structures
• OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• The complexity of valued CSPs
• On the relational width of first-order expansions of finitely bounded homogeneous binary cores with bounded strict width
• The power of Sherali-Adams relaxations for general-valued CSPs
• Binarisation for valued constraint satisfaction problems
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• Relational graph rewritings
• There are no pure relational width 2 constraint satisfaction problems
• Bounded width problems and algebras

This page was built for publication: Graphs of relational structures: restricted types

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635925)