CSP for binary conservative relational structures
For a fixed finite relational structure \(\mathbb A\), the nonuniform Constraint Satisfaction Problem (\(\mathrm{CSP}(\mathbb A)\)) asks whether a given input structure \(\mathbb X\) admits a homomorphism to \(\mathbb A\). This problem received a lot of attention following \textit{T. Feder} and \textit{M. Y. Vardi}'s conjecture P versus NP-complete dichotomy [SIAM J. Comput. 28, No. 1, 57--104 (1998; Zbl 0914.68075)] and the development of the so-called algebraic approach: using polymorphisms of \(\mathbb A\) to control the complexity of \(\mathrm{CSP}(\mathbb A)\). The algebraic dichotomy conjecture [\textit{A. Bulatov} et al., SIAM J. Comput. 34, No. 3, 720--742 (2005; Zbl 1071.08002)] states that if a core structure \(\mathbb A\) admits a Taylor polymorphism, then \(\mathrm{CSP}(\mathbb A)\) is in P, and otherwise it is NP-complete. One of the major successful steps towards resolving this conjecture was the case of conservative structures (also known as the list homomorphism problem) [\textit{A. A. Bulatov}, ACM Trans. Comput. Log. 12, No. 4, Article No. 24, 66 p. (2011; Zbl 1351.68113)]. In [\textit{P. Hell} and \textit{A. Rafiey}, ``The dichotomy of list homomorphisms for digraphs, in: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23--25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1703--1713 (2011; \url{doi:10.1137/1.9781611973082.131})], combinatorial methods were used to characterize conservative digraphs with tractable CSP. Moreover, the authors proved that all of them can be solved using local consistency checking (so-called bounded width). In this paper, combinatorial ideas from the digraph case are combined with advanced algebraic techniques from the general case to obtain a short and elegant proof of the CSP dichotomy for binary 3-conservative structures (that is, at most binary relations and every at most 3-element subset is a unary relation). The main result is the following: If a binary 3-conservative structure admits a Taylor polymorphism, then its polymorphism algebra generates a congruence meet semidistributive variety. As a consequence, all tractable cases have bounded width, as is the case with conservative digraphs.
- Characterizations of several Maltsev conditions.
- Classifying the Complexity of Constraints Using Finite Algebras
- Closed systems of functions and predicates
- Complexity of conservative constraint satisfaction problems
- Constraint Satisfaction Problems of Bounded Width
- scientific article; zbMATH DE number 3677917 (Why is no real title available?)
- On digraph coloring problems and treewidth duality
- On the reduction of the CSP dichotomy conjecture to digraphs
- The complexity of satisfiability problems
- The dichotomy of list homomorphisms for digraphs
- The shape of congruence lattices
- The structure of finite algebras
- Universal algebra and hardness results for constraint satisfaction problems
- Tractability in constraint satisfaction problems: a survey
- CSP dichotomy for special polyads
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- Graphs of relational structures: restricted types
- Algebra and the complexity of digraph CSPs: a survey
- Hybrid VCSPs with crisp and valued conservative templates
- On the relational width of first-order expansions of finitely bounded homogeneous binary cores with bounded strict width
- On the reduction of the CSP dichotomy conjecture to digraphs
- Full Constraint Satisfaction Problems
- The smallest hard trees
- The algebraic structure of the densification and the sparsification tasks for CSPs
- Network satisfaction problems solved by k-consistency
- Conservative constraint satisfaction re-revisited
This page was built for publication: CSP for binary conservative relational structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2634708)
