CSP for binary conservative relational structures (Q2634708): Difference between revisions

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.