Decidability of absorption in relational structures of bounded width. (Q2510713)

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.