Constraint satisfaction problem with a semilattice polymorphism is polynomial-soluble

Question

Let $\mathbb{A}=(A;R)$ be a relation structure, where $A$ is a finite set, $\varnothing\neq R\subseteq A^2$ is a relation preserved by a semilattice operation $f$. This means that $f:A^2\to A$ is idempotent, associative and commutative. Show that $\mathrm{CSP}(\mathbb A)\in \mathsf P$.

I encounter the problem as a generalisation of the version when $R$ is subdirect, in which case the CSP is clearly polynomial-soluble, as each primitive positive sentence naturally holds. However, in general when $R$ is not subdirect, this claim clearly fails. I am considering using clone homomorphism and interpretation to prove the general case, but so far I have not got any clue.

Thank you very much for help!

Answer 1

We may assume $\mathbb{A}$ is an idempotent core structure. (If it isn't, read the chapter "Polymorphisms and how to use them" by Barto, Kozik, and Willard. You want Theorems 16 and 17.)

Now that $\mathbb{A}$ is idempotent, every non-empty subuniverse of $\mathbf{A}=\mathrm{Pol}(\mathbb{A})$ has a 1-element subuniverse that is absorbed via $f$.

Before we talk about Prague instances, I first want to make sure we're on the same page. $\mathrm{CSP}(\mathbb{A})$ is a decision problem whose input is a finite relational structure $\mathbb{X}$ of the same signature as $\mathbb{A}$ and whose output is 'yes' if there is a homomorphism $\mathbb{X}\to\mathbb{A}$ and is 'no' if there is not. To show $\mathrm{CSP}(\mathbb{A})$ belongs to $\mathsf{P}$, we must exhibit a polynomial-time algorithm that decides it. I'll describe an algorithm below:

1. Collect all partial homomorphisms $\mathbb{X}\to\mathbb{A}$ whose domain has at most 3 elements. Call this collection $H$.
2. For every subset $L$ of $X$ of size 3, if a partial homomorphism $p$ in $H$ whose domain is $K$ (where $K$ is a subset of $L$ of size at most 2) does not have an extension in $H$ to all of $L$, then remove $p$ from $H$. Repeat until all choices of $L$, $K$, and $p$ have been checked.
3. If $H$ is empty, return 'no'. Else return 'yes'.

The runtime of this algorithm is polynomial in the size of $X$ and if $H$ is empty, then there cannot be a homomorphism $\mathbb{X}\to\mathbb{A}$. To get that a nonempty $H$ implies existence of a homomorphism, we need to analyze the structure of $H$.

For $x,y\in X$, let $H_x=H\cap A^{\{x\}}$ and $H_{xy}=\{(h_1,h_2)\in H_x\times H_y:h_1,h_2\text{ have a common extension in }H\}$.

Let $\mathcal{H}=\{H_x:x\in X\}\cup\{H_{xy}:x,y\in X\}$.

This $\mathcal{H}$ satisfies the property that for any $x,y,z\in X$, and any $(h_1,h_3)\in H_{xz}$, there is $h_2\in H_y$ such that $(h_1,h_2)\in H_{xy}$ and $(h_2,h_3)\in H_{yz}$.

This property is stronger than being a Prague instance (the book chapter mentioned above in the comments asks you to show this as an exercise, but I think you can find the proof in the appendix of "Constraint satisfaction problems of bounded width" by Barto and Kozik)

Once you have that, you can just follow along with Proposition 10 like I mentioned in the comments.