For relational structures A, B of the same signature, the Promise Constraint Satisfaction Problem PCSP(A,B) asks whether a given input structure maps homomorphically to A or does not even map to B. We are promised that the input satisfies exactly one
of these two cases. If there exists a structure C with homomorphisms $Ato Cto B$, then PCSP(A,B) reduces naturally to CSP(C). To the best of our knowledge all known tractable PCSPs reduce to tractable CSPs in this way. However Barto showed that some PCSPs over finite structures A, B require solving CSPs over infinite C. We show that even when such a reduction to finite C is possible, this structure may become arbitrarily large. For every integer $n>1$ and every prime p we give A, B of size n with a single relation of arity $n^p$ such that PCSP(A, B) reduces via a chain of homomorphisms $ Ato Cto B$ to a tractable CSP over some C of size p but not over any smaller structure. In a second family of examples, for every prime $pgeq 7$ we construct A, B of size $p-1$ with a single ternary relation such that PCSP(A, B) reduces via $Ato Cto B$ to a tractable CSP over some C of size p but not over any smaller structure. In contrast we show that if A, B are graphs and PCSP(A,B) reduces to tractable CSP(C) for some finite C, then already A or B has tractable CSP. This extends results and answers a question of Deng et al.
We show that for a fixed positive integer k one can efficiently decide if a finite algebra A admits a k-ary weak near unanimity operation by looking at the local behavior of the terms of A. We also observe that the problem of deciding if a given fini
te algebra has a quasi Taylor operation is solvable in polynomial time by looking, essentially, for local quasi Siggers operations.
We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at
most $N$, where the number $N$ depends on the arities of basic operations of the algebra and the size of the basic set. For finite idempotent algebras we give a tight bound on $N$ that, in the special case of algebras with more than $binom{|A|}2$ basic operations, improves an earlier result of K. Kearnes and A. Szendrei. On the algorithmic side, we show that deciding the existence of cube terms is in P for idempotent algebras and in EXPTIME in general. Since an algebra contains a $k$-ary near unanimity operation if and only if it contains a $k$-dimensional cube term and generates a congruence distributive variety, our algorithm also lets us decide whether a given finite algebra has a near unanimity operation.
This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation $m$ that satisfies the minority equations $m(y,x,x) approx m(x,y,x) approx m(x,x,y) approx y$. We show that a common po
lynomial-time approach to testing for this type of condition will not work in this case and that this decision problem lies in the class NP.
It is known that any finite idempotent algebra that satisfies a nontrivial Maltsev condition must satisfy the linear one-equality Maltsev condition (a variant of the term discovered by M. Siggers and refined by K. Kearnes, P. Markovic, and R. McKenzi
e): [ t(r,a,r,e)approx t(a,r,e,a). ] We show that if we drop the finiteness assumption, the $k$-ary weak near unanimity equations imply only trivial linear one-equality Maltsev conditions for every $kgeq 3$. From this it follows that there is no nontrivial linear one-equality condition that would hold in all idempotent algebras having Taylor terms. Miroslav Olv{s}ak has recently shown that there is a weakest nontrivial strong Maltsev condition for idempotent algebras. Olv{s}ak has found several such (mutually equivalent) conditions consisting of two or more equations. Our result shows that Olv{s}aks equation systems cant be compressed into just one equation.
In this paper we investigate the computational complexity of deciding if a given finite algebraic structure satisfies a fixed (strong) Maltsev condition $Sigma$. Our goal in this paper is to show that $Sigma$-testing can be accomplished in polynomial
time when the algebras tested are idempotent and the Maltsev condition $Sigma$ can be described using paths. Examples of such path conditions are having a Maltsev term, having a majority operation, and having a chain of Jonsson (or Gumm) terms of fixed length.
The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all
constraints are even $Delta$-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Using a reduction to even $Delta$-matroids, we then extend the tractability result to larger classes of $Delta$-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely co-independent, compact, local, linear and binary, with the following caveat: we represent $Delta$-matroids by lists of tuples, while the last two use a representation by matrices. Since an $ntimes n$ matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary $Delta$-matroids.
We characterize absorption in finite idempotent algebras by means of Jonsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of its basic operations.
