Digraph homomorphism problems and weak near unanimity polymorphisms

We start with a general digraph $H$ and a weak $k$-NU $\phi$ of $H$. We turn the problem $HOM(H)$ into a related problem of seeking a homomorphism with lists of allowed images. The list homomorphism problem for a fixed digraph $H$, denoted $LHOM(H)$, has as input a digraph $G$, and for each vertex $x$ of $G$ an associated list (set) of vertices $L(x)\subseteq V(H)$, and asks whether there is a homomorphism $g$ of $G$ to $H$ such that for each $x\in V(G)$, the image of $x$; $g(x)$, is in $L(x)$. Such a homomorphism is called a list homomorphism of $G$ to $H$ with respect to the lists $L$. List homomorphism problems have been extensively studied, and are known to have nice dichotomies [23, 26, 35]. However, we can not use the algorithms for finding list homomorphism from $G$ to $H$, because in the $HOM(H)$ problem, for every vertex $x$ of $G$, $L(x)=V(H)$.

One of the common ingredients in $CSP$ algorithms is the use of consistency checks to reduce the set of possible values for each variable (see, for example the algorithm outlined in [32] for $CSP(H)$ when $H$ admits a near unanimity function). Our algorithm includes such a consistency check (also known as (2,3)-consistency check [29]) as a first step which we call PreProcessing. PreProcessing procedure begins by performing arc and pair consistency check on the list of vertices in the input digraph $G$. For each pair $(x,y)$ of $V(G)\times V(G)$ we consider a list of possible pairs $(a,b)$, $a\in L(x)$ (the list in $H$ associated with $x\in V(G)$) and $b\in L(y)$. Note that if $xy$ is an arc of $G$ and $ab$ is not an arc of $H$ then we remove $(a,b)$ from the list of $(x,y)$. Moreover, if $(a,b)\in L(x,y)$ and there exists $z$ such that there is no $c$ for which $(a,c)\in L(x,z)$ and $(c,b)\in L(z,y)$ then we remove $(a,b)$ from the list of $(x,y)$. We continue this process until no list can be modified. If there are empty lists then clearly there is no list homomorphism from $G$ to $H$.

The main structure of the algorithm is to perform pairwise elimination, which focuses on two vertices $a,b$ of $H$ that occur together in some list $L(x),x\in V(G)$, and finds a way to eliminate $a$ or $b$ from $L(x)$ without changing a feasible problem into an unfeasible one. In other words if there was a list homomorphism with respect to the old lists $L$, there will still be one with respect to the updated lists $L$. This process continues until either a list becomes empty, certifying that there is no homomorphism with respect to $L$ (and hence no homomorphism at all), or until all lists become singletons specifying a concrete homomorphism of $G$ to $H$ or we reach an instance that has much simpler structure and can be solved by the existing CSP algorithms. This method has been successfully used in other papers [20, 35, 36].

In this paper, the choice of which $a$ or $b$ is eliminated, and how, is governed by the given weak near unanimity polymorphism $\phi$. The heart of the algorithm is a delicate procedure for updating the lists $L(x)$ in such a way that (i) feasibility is maintained, and the polymorphism $f$ keep its initial property (which is key to maintaining feasibility).

An interesting question arising from the study of CSP Dichotomy theorem is known as the meta-question. Given a relational structure $\mathcal{H}$, decide whether or not $\mathcal{H}$ admits a polymorphism from a class–for various classes of polymorphims. For many cases hardness results are known. Semmilattice, majority, Maltsev, NU, and weak NU, are among the popular polymorphisms when it comes to study of CSP. Having one or more of these polymorphisms on relation $\mathcal{H}$, would make the CSP($\mathcal{H}$) (or variation) instance tractable. Therefore, knowing structural characterization and polynomial time recognition for these polymorphisms would help in designing efficient algorithms for solving CSP. A binary polymorphism $f$ on $\mathcal{H}$ is called semilattice if $f(a,b)=f(b,a)$, and $f(a,a)=a$, $f(a,f(a,c))=f(f(a,b),c)$ for every $a,b,c\in V(\mathcal{H})$. A ternary polymorphism $g$ on $\mathcal{H}$ is majority if $g(a,a,a)=g(a,a,b)=g(a,b,a)=g(b,a,a)=a$. A polymorphism $h$ of arity three on $\mathcal{H}$ is called Maltsev if for every $a,b\in V(\mathcal{H})$, $h(a,a,a)=h(a,b,b)=h(b,b,a)=a$.

It was shown in [14] that deciding if a relational structure admits any of the following polymorphism is NP-complete; a semilattice polymorphism, a conservative semilattice polymorphism, a commutative, associative polymorphism (that is, a commutative semigroup polymorphism). However, when $\mathcal{H}$ is a single binary relation(digraph) then deciding whether $\mathcal{H}$ admits a conservative semmilattice is polynomial time solvable [34]. Relational structure and digraphs with majority/ near unanimity polymorphism have studied in [5, 14, 27, 35, 37, 44].

One remaining open question is whether the existence of a weak NU polymorphism for a given relational structure can be decided in polynomial time [6]. We transform this problem into a graph list homomorphism problem from an input graph $G$ to a target graph $H$, in which $G\times H^{4}$ admits a Siggers polymorphism (i.e. a weak NU polymorphism of arity $k$ for some $k\geq 3$) with respect to the lists. To solve this problem, we need some modules of our algorithm for finding a homomorphism from $G$ to $H$ when $H$ admits a weak NU. Moreover, we also need an algorithm for solving the list homomorphism problem from an input graph $G$ to a target graph $H$ where $G\times H^{3}$ admits a Maltsve polymorphism with respect to the lists; such an algorithm would only assume the existence of a Maltsev polymorphism without knowing the actual values. The later algorithm has been designed in [38]. Deciding whether a relational structure admits a Malstve polymorphims has been an open problem [6, 47]. We prove the following theorem.

For simplicity let $(b^{k},a)=(b,b,\dots,b,a)$ be a $k$-tuple of all $b$’s but with an $a$ in the $k^{th}$ coordinate. Let $(x;b^{k},a)$ be a $(k+1)$-tuple of $x$, $(k-1)$ $b$’s and $a$ in the $(k+1)^{th}$ coordinate.

Let $X:x_{1},x_{2},\dots,x_{n}$ be an oriented path in $G$. Let $X[x_{i},x_{j}]$, $1\leq i\leq j\leq n$, denote the induced sub-path of $X$ from $x_{i}$ to $x_{j}$. Let $L(X)$ denote the vertices of $H$ that lie in the list of the vertices of $X$.

Let $a_{1},a_{2}\in L(x)$ and suppose there exist $b_{1},b_{2}\in L(y)$ such that $(a_{1},b_{1}),(a_{1},b_{2}),(a_{2},b_{1}),(a_{2},b_{2})\in L(x,y)$. Then it follows from the property of $f$, that $\widehat{f}_{x,\{a_{1},a_{2}\}}$ and $\widehat{f}_{y,\{b_{1},b_{2}\}}$ induce a bi-clique on $x,y$.

Inside function Not-Minority we first check whether the instance is Maltsev or Minority instance – in which we have a homomorphism $f$ consistent with $L$ such that for every $a,b\in L(x)$, $(b,a)$ is a minority pair, i.e. $f(x;b^{k},a)=a$, and in particular when $a=b$ we have $f(x;a,a,\dots,a)=a$ (idempotent property).

In our setting a homomorphism $h:G\times_{L}H^{3}\rightarrow H$ is called Maltsev list homomorphism if $h(x;a,a,b)=h(x;b,a,a)=b$ for every $a,b\in L(x)$, $x\in V(G)$.

Let $G,H,L,f$ be an input to our algorithm, and suppose all the pairs are minority pairs. We define a homomorphism $h:G\times_{L}H^{3}\rightarrow H$ (consistent with $L$) by setting $h(x;a,b,c)=f(x;a,b,b,\dots,b,c)$ for $a,b,c\in L(x)$. Note that since $f$ has the minority property for all $x\in V(G)$, $a,b\in L(x)$, $h$ is a Maltsev homomorphism consistent with the lists $L$. This is because when $b=c$ then $h(x;a,b,b)=f(x;a,b,\dots,b)=a$, and when $a=b$, $h(x;a,a,c)=f(x;b,b,\dots,b,c)=c$, for every $a,c$, and hence, $h(x;b,b,a)=a$.

The Maltsev/Minority instances can be solved using the algorithm in [10]. Although the algorithm in [10] assumes there is a global Maltsev, it is straightforward to adopt that algorithm to work in our setting. We can also use the Algorithm in [38].

Not-Minority algorithm (Algorithm 2) first checks whether the instance is a minority instance, and if the answer is yes then it calls RemoveMinority function. Otherwise, it starts with a not-minority pair $(b,a)$ in $L(x)$, i.e., $w=(x;b^{k},a)$ with $f(w)=c\neq a$. Roughly speaking, the goal is not to use $f$ on vertices $w_{1}=(x;e_{1},e_{2},\dots,e_{k})$ with $f(w_{1})=a$; which essentially means setting $f(w_{1})=f(w)$. In order to make this assumption, it recursively solves a smaller instance of the problem (smaller test), say $G^{\prime}\subseteq G$, and $L^{\prime}\subset L$, and if the test is successful then that particular information about $f$ is no longer needed. More precisely, let $w=(x;b^{k},a)\in G^{\prime}\times_{L^{\prime}}H^{k}$ so that $f(w)=c\neq a$ and where $(x,a),(x,c)$ are in the same connected component of $G^{\prime}\times_{L^{\prime}}H$. The test $T_{x,c}$ is performed to see whether there exists an $L^{\prime}$-homomorphism $g$ from $G^{\prime}$ to $H$ with $g(x)=c$. If $T_{x,c}$ for $G^{\prime},L^{\prime}$ succeeds then the algorithms no longer uses $f$ for $w^{\prime}=(x;a_{1},a_{2},\dots,a_{k})\in G^{\prime}\times_{L^{\prime}}H^{k}$ with $f(w^{\prime})=a$. We often use a more restricted test, say $T_{x,c,y,d}$ on $G^{\prime},L^{\prime}$ in which the goal is to see whether there exists an $L^{\prime}$-homomorphism $g$, from $G^{\prime}$ to $H$ with $g(x)=c$, $g(y)=d$.

The Algorithm 2 is recursive, and we use induction on $\sum_{x\in V(G)}|L(x)|$ to show its correctness. In what follows we give an insight of why the weak $k$-NU ($k>2$) property of $H$ is necessary for our algorithm. For contradiction, suppose $w_{1}=(x;b^{k},a)$ with $f(w_{1})=c$ and $w_{2}=(x;a,b,b,\dots,b)$ with $f(w_{2})=d$. If $d=a$ then in Not-Minority algorithm we try to remove $a$ from $L(x)$ (not to use $a$ in $L(x)$) if we start with $w_{1}$ while we do need to keep $a$ in $L(x)$ because we later need $a$ in $L(x)$ for the Maltsev algorithm. It might be the case that $d\neq a$ but during the execution of Algorithm 2 for some $w_{3}=(x;b^{k},e)$ with $f(w_{3})\neq e$ we assume $f(w_{3})$ is $e$. So we need to have $f(w_{1})=f(w_{2})$, the weak NU property, to start in Algorithm 1.

Let $y,z\in V(G)$ and $d_{1},d_{2}\in L(y)$ and $e_{1}\in L(z)$ such that $(d_{1},e_{1}),(d_{2},e_{1})\in L(y,z)$. Let $L_{1}=L_{z,e_{1}}$. We consider the instances $G^{\prime},H,L^{\prime},f$ of the problem as follows. The induced sub-digraph $G^{\prime}$ consists of vertices $v$ of $G$ such that for every $(d_{1},j)\in L_{1}(y,v)$ we have $(d_{2},j)\not\in L_{1}(y,v)$. Now for each $v\in G^{\prime}$, $L^{\prime}(v)=\{i\mid(d_{1},i)\in L_{1}(y,v)\}$. Such an instance is constructed by function Sym-Diff($G,L,y,d_{1},d_{2},z,e_{1}$).

Let $B(G^{\prime})$ denote a set of vertices $u$ in $G\setminus G^{\prime}$ that are adjacent (via an out-going or in-coming arc) to some vertex $v$ in $G^{\prime}$. $B(G^{\prime})$ is called the boundary of $G^{\prime}$. We do not add $B^{\prime}(G^{\prime})$ into $G^{\prime}$ which makes it easier to argue about running time. However, we some extra care it is also possible to have an algorithm that include the boundary vertices. Note that for every $v\in V(G^{\prime})$, $|L^{\prime}(v)|<|L(v)|$. Moreover, $L^{\prime}(z)=\{e_{1}\}$, and $L^{\prime}(y)=\{d_{1}\}$.

For $y,z\in V(G)$ and $d_{1},d_{2}\in L(y)$ and $e_{1}\in L(z)$ we solve the instance $G^{\prime},H,L^{\prime},f$, by calling the Not-Minority($G^{\prime},H,L^{\prime},f$) function. The output of this function call is either a non-empty $L^{\prime}$-homomorphism $g^{y,z}_{d_{1},e_{1}}$ from $G^{\prime}$ to $H$ or there is no such homomorphism. If $g^{y,z}_{d_{1},e_{1}}$ does not exist then there is no homomorphism from $G$ to $H$ that maps $y$ to $d_{1}$, and $z$ to $e_{1}$. In this case we remove $(d_{1},e_{1})$ from $L(y,z)$, and remove $(e_{1},d_{1})$ from $L(z,y)$. This should be clear because $G^{\prime}$ is an induced sub-digraph of $G$, and for every vertex $v\in V(G^{\prime})\setminus\{y,z\}$, $L^{\prime}(v,z)=L(v,z)$, $L^{\prime}(v,y)=L(v,y)$. Moreover, it is easy to see (will be shown later) that $L^{\prime}$ is closed under $f$. The homomorphism $g^{y,z}_{d_{1},e_{1}}$ is used in the correctness proof of the Algorithm 2.

In order to avoid several redundant tests, when a sub-digraph $G^{\prime}$ constructed by Sym-Diff($G,L,y,d_{1},d_{2},z,e_{1}$) is the same as $G$; and the test returns true, then we no longer need to run the test for any other sub-instance $(G^{\prime\prime},L^{\prime\prime})$ because we just need to return yes to the parent sub-routine calling the current sub-routine.