Decidability of absorption in relational structures of bounded width.
Given an algebra \(\mathbf A\), a subuniverse \(B\leq\mathbf A\) is \textit{absorbing} if there exists an idempotent term \(t(x_1,\ldots,x_n)\) of \(\mathbf A\) such that \(t(B,\ldots,B,A,B,\ldots,B)\subseteq B\) for all of the \(n\) positions for ``\(A\). In some sense, \(t\) behaves as a near unanimity (NU) term with respect to \(B\). Absorbing subuniverses have been used by Barto and Kozik in the algebraic approach to the Constraint Satisfaction Problem (CSP). A relational structure \(\mathbb A\) has \textit{bounded width} if its CSP problem can be solved by \textit{local consistency checking} and hence is tractable. It was conjectured by \textit{B. Larose} and \textit{L. Zádori} [Algebra Univers. 56, No. 3--4, 439--466 (2007; Zbl 1120.08002)] that a structure has bounded width if and only if its algebra of polymorphisms lies on a \(\wedge\)-semidistributive variety. \textit{L. Barto} and \textit{M. Kozik} [in: 2009 IEEE 50th annual symposium on foundations of computer science -- FOCS 2009. Proceedings of the symposium. Los Alamitos, CA: IEEE Computer Society. 595--603 (2009; Zbl 1292.68088)] answer this question on the affirmative. Further, Barto applies these techniques to solve another problem by Zadori, proving that finite, finitely related algebras that generate a congruence distributive variety have NU terms [\textit{L. Barto}, Can. J. Math. 65, No. 1, 3--21 (2013; Zbl 1283.08009)]. The paper under review relies heavily on this last work. The main result of the paper is a \texttt{co-NEXPTIME} algorithm to decide whether a subset \(B\) of a \(\wedge\)-semidistributive algebra \(\mathbf A\) is an absorbing subuniverse (actually, \texttt{EXPTIME} once \(B\) is known to be a subuniverse of \(\mathbf A\)). The author explores a generalization of the notion of absorption and shows that it coincides with the ordinary concept in the case of \(\wedge\)-semidistributive varieties. Then the problem at hand is codified as an instance of CSP and the author adapts a proof from Barto's paper concerning realization of trees to obtain a criterion of solution of this instance. The exponential bound comes from the fact that trees having at most \(4^{8^{|\mathbf A|}}\) vertices have to be checked to fulfill this criterion. Afterwards, it is recalled from \textit{J. Bulín} et al. [Lect. Notes Comput. Sci. 8124, 184--199 (2013; Zbl 1432.68170)] a way to associate a digraph \(\mathcal D(\mathbb A)\) to a finite relational structure \(\mathbb A\) in such a way the respective algebras of polymorphisms share many important properties. In the present paper, the author shows that also absorption is preserved by this construction.
- Bounded width problems and algebras
- On tractability and congruence distributivity
- Graphs of relational structures: restricted types
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- Asking the Metaquestions in Constraint Tractability
- scientific article; zbMATH DE number 1944123
- Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
- Solving CSPs using weak local consistency
- On the reduction of the CSP dichotomy conjecture to digraphs
- Finitely related algebras in congruence distributive varieties have near unanimity terms
- Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
- Bounded width problems and algebras
- Classifying the Complexity of Constraints Using Finite Algebras
- Congruence distributivity implies bounded width
- Constraint Satisfaction Problems of Bounded Width
- Finitely related algebras in congruence distributive varieties have near unanimity terms
- Mal'tsev conditions, lack of absorption, and solvability.
- On the (un)decidability of a near-unanimity term
- On the reduction of the CSP dichotomy conjecture to digraphs
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- CD(4) has bounded width
- Testing for edge terms is decidable
- Deciding absorption in relational structures
- Deciding absorption
- On absorption in semigroups and n-ary semigroups.
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- Congruence distributivity implies bounded width
- Absorption and directed Jónsson terms
- Graphs of relational structures: restricted types
- Absorption in universal algebra and CSP
- Algebra and the complexity of digraph CSPs: a survey
- Bounded width problems and algebras
This page was built for publication: Decidability of absorption in relational structures of bounded width.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2510713)
