Dichotomy for Digraph Homomorphism
Problems
arXiv:1701.02409v4 [cs.CC] 29 Jul 2017

Tomás Feder∗

Jeff Kinne

†

Arash Rafiey

‡

Abstract
Update – An issue has been found in the correctness of our algorithm, and we are
working to resolve the issue. Until a resolution is found, we retract our main claim
that our approach gives a combinatorial solution to the CSP conjecture. We remain
hopeful that we can resolve the issues. We thank Ross Willard for carefully checking
the algorithm and pointing out the mistake in the version of this manuscript. We briefly
explain one issue at the beginning of the text, and leave the rest of the manuscript
intact for the moment . Ross Willard is posting a more involved description of a
counter-example to the algorithm in the present manuscript. We have an updated
manuscript that corrects some issues while still not arriving at a full solution; we will
keep this private as long as unresolved issues remain.
Previous abstract – We consider the problem of finding a homomorphism from an
input digraph G to a fixed digraph H. We show that if H admits a weak-near-unanimity
polymorphism φ then deciding whether G admits a homomorphism to H (HOM(H))
is polynomial time solvable. This confirms the conjecture of Maroti and McKenzie
[MM08], and consequently implies the validity of the celebrated dichotomy conjecture
due to Feder and Vardi [FV93]. We transform the problem into an instance of the list
homomorphism problem where initially all the lists are full (contain all the vertices of
H). Then we use the polymorphism φ as a guide to reduce the lists to singleton lists,
which yields a homomorphism if one exists.

1 Introduction
Update – discussion of counter-example to correctness of the algorithm in this manuscript
– In this brief update we aim the discussion at those who already are familiar with our
∗

268 Waverley Street, Palo Alto, CA 94301, United States, tomas@theory.stanford.edu
Indiana State University, IN, USA, jkinne@cs.indstate.edu
‡
Indiana State University, IN, USA arash.rafiey@indstate.edu and Simon Fraser University, BC, Canada,
arashr@sfu.ca
†

1

approach from reading this or another manuscript. Our algorithm makes a decision based
on the output of a test Tx,a,b on a smaller instance of the homomorphism problem. Here a, b
are possible images for x ∈ V (G), of a homomorphism from G to H.
The present manuscript assumes that the test Tx,a,b outputs“yes” and based on the correctness of the test a is removed from further consideration for x. The test Tx,a,b uses the
properties of the weak-nuf polymorphism φ. However, it is conceivable that the test Tx,a,b
fails and this means we should not remove a from the list of possible images of x. We had
incorrectly claimed in the manuscript that the properties of φ and pre-tests in the algorithm
gaurtanee the test always passes. But we can simply construct such an example where the
test must fail in the algorithm as follows. Let H be a digraph with two weakly connected
components H1 , H2 . The weak nuf polymorphism φ could be of arity 3 and such that for every a ∈ H1 and every b ∈ H2 , φ(a, b, b) = φ(b, b, a) = φ(b, a, b) = c for some c ∈ H2 . Suppose
there exists a homomorphism from G (weakly connected) to H that maps x to a and hence
the entire graph G must be mapped to H1 . Moreover, suppose there is no homomorphism
from G to H2 . The algorithm does consider the test Tx,a,b eventually for such G and H.
According to the test Tx,a,b , we remove a from further consideration for x which leads us to
remove the possible homomorphism from G to H.
Note that one can assume H is weakly connected as follows. Suppose H1 , H2 are balanced
digraphs with ` levels (we can partitioned the vertics of Hi , i = 1, 2, into ` parts where all
the arcs of Hi go from a vertex in some part j to part j + 1). Then an extra vertex a0 can be
added and connected to all the vertices of H1 , H2 on the lowest level. This way we obtain
the weakly connected digraph H = H1 ∪ H2 ∪ {a0 } with ` + 1 levels.
We may assume G is also balanced and has ` levels. An extra vertex x0 can be added to
G with arcs to every vertex of G on the lowest level. Now G0 = G ∪ {x0 } is also a balanced
digraph with ` + 1 levels. Note that in any homomorphism from G0 to H, x0 must be mapped
to a0 and any other vertex of G0 must map to H − {x}.
We note that Ross Willard may post a concrete counter-example (and further discussion of
his example) for which H contains 197 vertices in H. The example is inspired from instances
of the CSP problem, so called Semi-lattice block Maltsev.
Previous introduction – For a digraph G, let V (G) denote the vertex set of G and let
A(G) denote the arcs (aka edges) of G. An arc (u, v) is often written as simply uv to shorten
expressions. Let |G| denote the number of vertices in G.
A homomorphism of a digraph G to a digraph H is a mapping g of the vertex set of G to
the vertex set of H so that for every arc uv of G the image g(u)g(v) is an arc of H. A natural
decision problem is whether for given graphs G and H there is a homomorphism of G to H.
If we view graphs as digraphs in which each edge is replaced by the two opposite directed
arcs, we may apply the definition to graphs as well. An easy reduction from the k-coloring
problem shows that this decision problem is N P -hard: a graph G admits a 3-coloring if
and only if there is a homomorphism from G to K3 , the complete graph on 3 vertices. As
a homomorphism is easily verified if the mapping is given, the homomorphism problem is

2

contained in N P and is thus N P -complete.
The following version of the problem has attracted much recent attention. For a fixed
digraph H the problem HOM (H) asks if a given input digraph G admits a homomorphism
to H. Note that while the above reduction shows HOM (K3 ) is NP-complete, HOM (H)
can be easy (in P ) for some graphs H: for instance if H contains a vertex with a selfloop, then every graph G admits a homomorphism to H. Less trivially, for H = K2 (or
more generally, for any bipartite graph H), there is a homomorphism from G to K2 if and
only if G is bipartite. A very natural goal is to identify precisely for which digraphs H
the problem HOM (H) is easy. In the case of graphs the classification has turned out to
be this: if H contains a vertex with a self-loop or is bipartite, then HOM (H) is in P ,
otherwise it is N P -complete [HN90] (see [B05, S10] for shorter proofs). This classification
result implies a dichotomy of possibilities for the problems HOM (H) when H is a graph,
each problem being N P -complete or in P . However, the dichotomy of HOM (H) remained
open for general digraphs H. It was observed by Feder and Vardi [FV93] that this problem
is equivalent to the dichotomy of a much larger class of problems in N P , in which H is
a fixed finite relational structure. These problems can be viewed as constraint satisfaction
problems with a fixed template H [FV93], written as CSP (H). A constraint satisfaction
problem CSP (H) consists of (a) a relational structure H that specifies a set V of variables
that each come from some domain D and (b) a set C of constraints giving restrictions on
the values allowed on the variables.
The question is whether all constraints can be simultaneously satisfied. 3SAT is a prototypical instance of CSP, where each variable takes values of true or false (a domain size of
two) and the clauses are the constraints. Digraph homomorphism problems can also easily
be converted into CSPs: the variables V are the vertices of G, each must be assigned a vertex
in H (meaning a domain size of |V (H)|), and the constraints encode that each arc of G must
be mapped to an arc in H.
Feder and Vardi argued in [FV93] that in a well defined sense the class of problems
CSP (H) would be the largest subclass of N P in which a dichotomy holds. A fundamental
result of Ladner [L75] asserts that if P 6= N P then there exist N P -intermediate problems
(problems neither in P nor N P -complete), which implies that there is no such dichotomy
theorem for the class of all N P problems. Non-trivial and natural subclasses which do have
dichotomy theorems are of great interest. Feder and Vardi made the following Dichotomy
Conjecture: every problem CSP (H) is N P -complete or is in P . This problem has animated
much research in theoretical computer science. For instance the conjecture has been verified
when H is a conservative relational structure [B11], or a digraph with all in-degrees and
all-out-degrees at least one [BKN09].
Numerous special cases of this conjecture have been verified [ABISV09, B06, BH90, BHM88,
CVK10, D00, F01, F06, FMS04, LZ03, S78].
It should be remarked that constraint satisfaction problems encompass many well known
computational problems, in scheduling, planning, database, artificial intelligence, and constitute an important area of applications, in addition to their interest in theoretical computer

3

science [CKS01, D92, V00, K92].
While the paper of Feder and Vardi [FV93] did identify some likely candidates for the
boundary between easy and hard CSP -s, it was the development of algebraic techniques
by Jeavons [J98] that lead to the first proposed classification [BJK05]. The algebraic approach depends on the observation that the complexity of CSP (H) only depends on certain
symmetries of H, the so-called polymorphisms of H. For a digraph H a polymorphism φ
of arity k on H is a homomorphism from H k to H. Here H k is a digraph with vertex set
{(a1 , a2 , . . . , ak )|a1 , a2 , . . . , ak ∈ V (H)} and arc set {(a1 , a2 , . . . , ak )(b1 , b2 , . . . , bk ) | ai bi ∈
A(H) for all 1 ≤ i ≤ k}. For a polymorphism φ, φ(a1 , a2 , . . . , ak )φ(b1 , b2 , . . . , bk ) is an arc of
H whenever (a1 , a2 , . . . , ak )(b1 , b2 , . . . , bk ) is an arc of H k .
Over time, one concrete classification has emerged as the likely candidate for the dichotomy. It is expressible in many equivalent ways, including the first one proposed in
[BJK05]. There were thus a number of equivalent conditions on H that were postulated to
describe which problems CSP (H) are in P . For each, it was shown that if the condition is
not satisfied then the problem CSP (H) is N P -complete (see also the survey [HN08]). One
such condition is the existence of a weak near-unanimity polymorphism (Maroti and McKenzie [MM08]). A polymorphism φ of H of arity k is a k near unanimity polymorphism (k-nu)
on H, if φ(a, a, . . . , a) = a for every a ∈ V (H), and φ(a, a, . . . , a, b) = φ(a, a, . . . , b, a) =
· · · = φ(b, a, . . . , a) = a for every a, b ∈ V (H). If we only have φ(a, a, . . . , a) = a for every
a ∈ V (H) and φ(a, a, . . . , a, b) = φ(a, a, . . . , b, a) = · · · = φ(b, a, . . . , a) [not necessarily a] for
every a, b ∈ V (H), then φ is a weak k-near unanimity function (weak k-nu).
Given the N P -completeness proofs that are known, the proof of the Dichotomy Conjecture
reduces to the claim that a relational structure H which admits a weak near-unanimity
polymorphism has a polynomial time algorithm for CSP (H). As mentioned earlier, Feder
and Vardi have shown that is suffices to prove this for HOM (H) when H is a digraph. This
is the main result of our paper.
Note that the real difficulty in the proof of the graph dichotomy theorem in [HN90] lies in
proving the N P -completeness. By contrast, in the digraph dichotomy theorem proved here
it is the polynomial-time algorithm that has proven more difficult.
While the main approach in attacking the conjecture has mostly been to use the highly
developed techniques from logic and algebra, and to obtain an algebraic proof, we go in the
opposite direction and develop a combinatorial algorithm.
Our main result is the following.
Theorem 1.1 Let H be a digraph that admits a weak near-unanimity function. Then
HOM (H) is in P . Deciding whether an input digraph G admits a homomorphism to H
can be done in time O(|G|3 |H|k+1 ) (k is the arity of the weak near-unanimity function).
Together with the N P -completeness result of [MM08], this settles the CSP Conjecture in
the affirmative. We note that H is fixed and also k ≤ 2|H| according to [JB17]. Therefore
we may consider O(|G|3 ) as running time in Theorem 1.1.

4

Our Methods, Very High Level View We start with a general digraph H and a weak k-nu
φ 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) ⊆ V (H), and asks whether there is a homomorphism g of G to H such
that for each x ∈ V (G), the image 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 are
known to have nice dichotomies. For instance when H is a reflexive graph (each vertex has
a loop), the problem LHOM (H) is polynomial when H is an interval graph and is N P complete otherwise [FH98]. Similar list homomorphism dichotomies were proved for general
graphs [FHH03, FHH07], and more recently also for digraphs [HR11]. In fact, motivated
by the results in [FH98, FHH03], Bulatov [B11] proved that the list version of constraint
satisfaction problems has a dichotomy for general relational systems.
It is not difficult to see that there are digraphs H such that HOM (H) is polynomial
while LHOM (H) is N P -complete. For instance, the reflexive four-cycle H has loops and
so HOM (H) is trivial, while LHOM (H) is NP-complete since H is not an interval graph.
However, we transform the problem HOM (H) into a restricted version of LHOM (H) in
which the lists satisfy an additional property related to the weak k-nu φ.
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 [HN04] for CSP (H) when H admits a near unanimity function). Our algorithm includes
such a consistency check as a first step. We begin by performing a pair consistency check of
the list of vertices in the input digraph G. For each pair (x, y) of V (G) × V (G) we consider
a list of possible pairs (a, b), a ∈ L(x) (the list in H associated with x ∈ G) and b ∈ 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) ∈ L(x, y) and there exists z such that there is no c for which
(a, c) ∈ L(x, z) and (c, b) ∈ 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.
After performing pair consistency checks (and repeating the consistency checks throughout
the algorithm), 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 ∈ 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. This technique, due to the last author, has been successfully
used in several other papers [HR11, HR12, EHLR14]. In this paper, the choice of which a
or b is eliminated, and how, is governed by the given weak near-unanimity polymorphism
φ. In fact, we define a family of mappings fx , x ∈ V (G) which are each polymorphisms

5

derived from φ and use these polymorphisms as a guide. The heart of the algorithm is a
delicate procedure for updating the lists L(x) and polymorphisms fx in such a way that (i)
feasibility is maintained, and (ii) the polymorphisms fx remain polymorphisms (which is key
to maintaining feasibility). We present two approaches where the first algorithm is recursive
and the second algorithm is not recursive. For the sake of the completeness we repeat the
definitions in both parts. The introduction is presented once. We think the first algorithm
is conceptually is easier to follow.

2 First Approach (recursive algorithm )
An oriented walk (path) is obtained from a walk (path) by orienting each of its edges. The
net-length of a walk W , is the number of forward arcs minus the number of backward arcs
following W from the beginning to the end. An oriented cycle is obtained from a cycle by
orienting each of its edges. We say two oriented walks X, Y are congruent if they follow the
same patterns of forward and backward arcs.
Given digraphs G and H, let G × H k be a digraph on the vertices {(y; a1 , a2 , . . . , ak )|y ∈
V (G), ai ∈ V (H), 1 ≤ i ≤ k} with the arcs (y; a1 , a2 , ..., ak )(y 0 ; b1 , b2 , ..., bk ) where yy 0 is an
arc of G and each ai bi , 1 ≤ i ≤ k, is an arc of H. By convention, we shall further restrict the
use of the symbol G×H k to the digraph induced on the vertices {(y; a1 , a2 , . . . , ak )|y ∈ V (G),
ai ∈ L(y), 1 ≤ i ≤ k} where L(y) is the set of vertices in H that are being considered as
images of a homomorphism from G to H.
Definition 2.1 (Homomorphism consistent with Lists) Let G and H be digraphs. For
each x ∈ V (G), let list of x, L(x), be a subset of H. Let k > 1 be a constant integer.
A function f : G × H k → H is a homomorphism consistent with L if the following hold.
• List property : for every x ∈ V (G) and every a1 , a2 , . . . , ak ∈ L(x), f (x; a1 , a2 , . . . , ak ) ∈
L(x)
• Adjacency property: for every x, y ∈ V (G) and every a1 , ..., ak ∈ L(x), b1 , ..., bk ∈ L(y),
if xy is an arc of G and ai bi is an arc of H for each 1 ≤ i ≤ k then f (x; a1 , ..., ak )f (y; b1 , ..., bk )
is an arc of H.
In addition if f has the following property then we say f has the weak nu property.
• for every x ∈ V (G), {a, b} ⊆ L(x), we have f (x; a, b, b, ..., b) = f (x; b, a, b, ..., b) = ... =
f (x; b, b, b, ...a).
We note that this definition is tailored to our purposes and in particular differs from the
standard definition of weak k-nu as follows.
(a) f is based on two digraphs G and H rather than just H (we think of this as starting
with a traditional weak k-nu on H and then allowing it to vary somewhat for each
x ∈ G),

6

(b) We do not require that f (y; d, d, d, ..., d) = d (this is not required in our algorithm, and
in fact is more convenient to leave out).
Notation For simplicity let (bk , a) = (b, b, . . . , b, a) be a k-tuple of all b’s but with an a in
the k th coordinate. Let (x; bk , a) be a (k + 1)-tuple of x, (k − 1) b’s and a in the (k + 1)th
coordinate.

2.1 Main Procedure
Algorithm 1 The main algorithm for solving the digraph homomorphism problem.
1: function DigraphHom(G, H, φ)
. G and H digraphs, φ a weak k-nu on H
2:
for all x ∈ G, let L(x) = V (H)
3:
for all x ∈ G and a1 , ..., ak ∈ V (H), let f (x; a1 , ..., ak ) = φ(a1 , ..., ak )
4:
PreProcessing(G, H, L)
5:
RemoveNotMinority(G, H, L, f )
6:
Note: now, for all x ∈ V (G) and a, b ∈ L(x) we know f (x; bk , a) = a
7:
RemoveMinority(G, H, L, f )
8:
if RemoveMinority produces a homomorphism then return true
The main algorithm starts with applying the arc consistency and pair consistency on the
lists L by calling Algorithm 2.
Algorithm 4 (RemoveNotMinority function) is the key subroutine of the main algorithm.
It starts with w = (x; bk , a) where f (w) = c 6= a and then it will modify f by setting
f (x; e1 , e2 , . . . , ek ) = f (w) for every k-tuple e1 , e2 , . . . , ek ∈ L(x) with f (x; e1 , e2 , . . . , ek ) = a.
Now in order to have a homomorphism from G × H k to H consistent with L, it recursively
solves an instance of the problem to be able to modify f as necessary.
After the main loop in Algorithm 1, we end up with a so-called Maltsev or minority instance of the problem – in which we have a homomorphism f consistent with L such that
for every y ∈ V (G) and every c, d ∈ L(y) we have f (y; ck , d) = d. We argue in the next
subsection that such instances can be solved by using the known algorithm of [BD06] (see
the remark at the end of Subsection 2.2). The Maltsev/minority instances can also be solved
in a manner similar to our arguments for RemoveNotMinority (see Section 5.7) .
In what follows we give an insight of why the weak nu property of H is necessary for our
algorithm. For contrary suppose w1 = (x; bk , a) with f (w1 ) = c and w2 = (x; a, b, b, . . . , b)
with f (w2 ) = d. If d = a then in RemoveNotMinority we try to remove a from L(x) if we
start with w1 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 6= a but some non-minority pairs becomes
minority pairs during the execution of Algorithm 4. In other words, for some w3 = (x; bk , e)
with f (w3 ) 6= e we may set f (w3 ) to e. So we need to have f (w1 ) = f (w2 ), the weak nu

7

Algorithm 2 Update lists of x, y based on edge constraints and pair constraint. Call by
reference, i.e. the update to L will be reflected in the calling function
1: function PreProcessing(G, H, L)
2:
Input: digraphs G, H, lists L(x) ⊆ V (H) for each x
. L lists are unary and binary
3:
. The update to L would be available for the function calling PreProcessing
4:
ArcConsistency(G, H, L) and PairConsistency(G, H, L)
function ArcConsistency(G, H, L)
update=True
while update do
if ∃xy(yx) ∈ A(G), a ∈ L(x) s.t. @b ∈ L(y) with ab(ba) ∈ A(H) then
remove a from L(x) and set update=True.
else update=False.
11:
if there is an empty list then print ”no homomorphism” and terminate
5:
6:
7:
8:
9:
10:

12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

function PairConsistency(G, H, L)
for all (x, y) ∈ V (G) × V (G) do set L(x, y) = {(a, b)|a ∈ L(x), b ∈ L(y)}
for all x ∈ V (G) do set L(x, x) = {(a, a)|a ∈ L(x)}.
for all xy ∈ A(G), a ∈ L(x), b ∈ L(y) do
if ab 6∈ A(H) then remove (a, b) from L(x, y).
update=True
while update do
if ∃x, y, z s.t. @c ∈ L(z) s.t. (a, c) ∈ L(x, z)&(c, b) ∈ L(z, y) then
remove (a, b) from L(x, y) and set update=True.
else update=False.
if there is an empty list then print ”no homomorphism” and terminate

8

property, to start in the main algorithm, Algorithm 1. We do mention at the end of the
proof of Lemma 3.4 that we can start the entire Algorithm 4 from vertex w2 and following
the first coordinates.
First we give the necessary definition for Algorithm 4.
GL Subdigraph of G×H k : Let GL be the digraph with vertices V (GL ) = {(y; ak1 , a2 ) | y ∈
V (G), a1 , a2 ∈ L(y)} and with arcs :
A(GL ) = {(y; ak1 , a2 )(y 0 ; bk1 , b2 ) | yy 0 ∈ A(G), a1 b1 , a2 b2 ∈ A(H)}∪{(y; ak1 , a2 )(y 0 ; bk1 , b2 ) | y 0 y ∈
A(G), b1 a1 , b2 a2 ∈ A(H)}.
Note that a directed path in GL is an oriented path in G × H k . Let B be a walk in H
starting at some vertex a ∈ V (H). We say a directed path W in GL follows B if B is the
projection of W on the (k + 1)th coordinate, i.e. B is induced by the (k + 1)th coordinates
of the vertices in W .
We say a directed path W in GL follows a walk X in G when X is the projection of W
on the first coordinate, i.e. X is induced by the first coordinates of the vertices in W .
Definition 2.2 (Reachable from w in GL : GL (w), GrL (w)) Let w = (x; bk , a) with f (w) 6=
a.
• Let GL (w) be the induced sub-digraph of GL with vertices w0 = (y; ak1 , a2 ) such that
(b, a1 ) ∈ L(x, y) and w0 is reachable from w in GL . 1
• Let GrL (w) be the induced sub-digraph of GL (w) with vertices w1 = (y; ak1 , a02 ) such that
– (b, a1 ) ∈ L(x, y) and (a, a02 ) ∈ L(x, y)
– w0 is reachable from w in GL .

2

Definition 2.3 (Pair digraph to update f : ) Let L be the lists of the vertices of G. For
y ∈ V (G) and a1 ∈ L(y), let Pl (y, a1 ) denote a subset of vertices in L(y). For a positive
integer t > 1, let Plt (y, c1 ) be a subset of L(y) s.t. Plt (y, c1 ) = Pl (y, Plt−1 (y, c1 )). Here
Pl (y, L0 ) = ∪a1 ∈L0 Pl (y, a1 ) where L0 ⊆ L(y) and Pl1 (y, a1 ) = Pl (y, a1 ).
Let GPl be the digraph of vertices (y, c1 , c2 ) with y ∈ V (G) and c1 , c2 ∈ L(y) such that
c2 ∈ Pli (y, c1 ) for some i ≥ 1 and Pl (y, c2 ) = {c2 }.
The arc set of GPl is A(GPl ) = {(y, c1 , c2 )(z, d1 , d2 ) | yz ∈ A(G), c1 d1 , c2 d2 ∈ A(H) OR zy ∈
A(G), d1 c1 , d2 c2 ∈ A(H)}.
Let GPl (x, a, d) be the induced sub-digraph of GPl induced by the vertices of GPl that are
reachable from (x, a, d).
1
2

Suppose w0 is reachable from w via a path P in Gl . If P contains (x; dk , a0 ) then d = b.
Suppose w0 is reachable from w via a path P in Gl . If P contains (x; bk , a0 ) then a0 = a.

9

Definition 2.4 (f -closure of a list : ) We say a list L0 (y) ⊆ L(y) is closed under f if for
every k-tuple a01 , a02 , . . . , a0k ∈ L1 (y) we have f (y; a01 , a02 , . . . , a0k ) ∈ L0 (y).
For L0 (y) ⊆ L(y), let L0f (y) be a minimal set that includes all the element of L0 (y) and it
is closed under f .
Definition 2.5 (restriction of f to a sub-list:) Let L0 (y) ⊆ L(y) for every y ∈ V (G).
Let f |L0 denote the restriction of f under L0 , i.e. for all y ∈ V (G), and for all a1 , a2 , . . . , ak ∈
L0 (y) we have fL0 (y; a1 , a2 , . . . , ak ) = f (y; a1 , a2 , . . . , ak ).
Let X : x1 , x2 , . . . , xn be an oriented walk in G. Let L(X) denote the vertices of H that
lie in the list of the vertices of X. Let X[xi , xj ], 1 ≤ i ≤ j ≤ n, denote the induced sub-path
of X from xi to xj .
An overview of Algorithm 4 : Algorithm 4 starts with a vertex x ∈ V (G) and two vertices
a, b ∈ L(x) such that f (w = (x; bk , a)) = c. The goal is to modify f by setting f (w1 ) to c for
every w1 = (x; e1 , e2 , . . . , ek ) where f (w1 ) = a initially.
The change to f in x imposes a change to f in the neighbors of x. Let w1 = (y; ak1 , a2 ) be
a neighbor of w and suppose ca2 6∈ A(H). We do need to change f (w0 = (y; a01 , a02 , . . . , a0k ))
from a2 to an out-neighbor of c in L(y) in order to keep f as a homomorphism from G × H k
to H and consistent with the lists L. There are several possibilities to change f (w0 ). One
could consider any out-neighbor of b, say a1 and consider vertex w2 = (y; ak1 , a2 ) and modify
f (w0 ) to f (w2 ) which is an out-neighbor of c (see Figure 1 top). The decision for changing
f in y would also imply a change to f in some vertex z ∈ V (G) which is a neighbor of
y. In order to manage these modifications we construct an instance G0 , H, L0 , f 0 so called
Small-Instance.
We first give a reason of the construction of such an instance. Let X be an oriented
cycle in G. The goal is to replace an oriented cycle B containing vertex a in L(X) with an
oriented cycle C in L(X) that does not contain a. We may view B as an image of X under
a homomorphism from G to H that maps x to a.
The Algorithm 4 starts with empty lists E, L0 . It considers the vertices of GrL (w) and for
each vertex (y; ak1 , a2 ) ∈ GrL (w) it adds f (y; ak1 , a2 ) into E(y). Then it sets L0 (y) = Ef (y),
i.e. the closure of E(y) under f . This means L0 (y) contains f (y; c1 , c2 , . . . , ck ) for every
c1 , c2 , . . . , ck ∈ L0 (y). Now in this new instance, for every y ∈ V (G0 ) it defines f 0 to be the
restriction of f to the vertices in L0 (y). This would imply that f 0 is a homomorphism from
G × H k to H and consistent with the lists L0 . Note that L0 (x) = c and hence in the resulting
instance at least one list becomes smaller.
The algorithm solves the instance G0 , L0 , f 0 , H recursively. Note that the stopping point
is when for every y ∈ G0 and every d, e ∈ L0 (y), f 0 (y; dk , e) = e. In order to keep track
of changes to f 0 , it maintains a list Pl (y, a2 ); list of possible images for a2 , which indicates
f (w0 = (y; a01 , a02 , . . . , a0k )) may need to be changed from a2 to c2 ∈ Pl (y, a2 ) (see Figure 1).
We make the Pl list global so they will be accessible in recursion tree.

10

However, in the recursive call, c2 may change to something else. In other words, d2 ∈
Pl (y, c2 ), and this would mean f (w0 ) should be changed from a2 to d2 . In this case d2 ∈
Pl (y, Pl (y, a2 )) or equivalently d2 ∈ Pl2 (y, a2 ). At the bottom of the recursion tree we would
have an element ct ∈ Plt (y, a2 ) such that Pl (y, ct ) = {ct }.
Now the algorithm modifies f according to the Pl lists. It constructs a triple digraph
GPl (x, a, c) that represents the vertices of G for which the f values need to be changed
because of the initial change in L(x). It starts at w and it changes f (w1 = (x, e1 , e2 , . . . , ek ))
from a to c for any such w1 . Suppose the algorithm modifies f (w0 ) for w0 = (y; a01 , a02 , . . . , a0k )
from a2 to an element ct ∈ Plt (y, a2 ). Then it modifies f for f (z; ...) from b2 to an element
in Plt (z, b2 ) which is an out-neighbor of c2 and (y; ak1 , a2 )(z; bk1 , b2 ) ∈ A(GrL (w) see Figure 2).
This suggests the algorithm does a depth first search in digraph GPl (x, a, c) to update f in
the Update-f function.
At this point for every k-tuple e1 , e2 , . . . , ek in L(x), f (x, e1 , e2 , . . . , ek ) 6= a. However,
the algorithm has not modified f on the entire digraph affected by the initial change to f
in L(x). For this reason it constructs a Big-Instance G0 , H, L0 , f 0 . In the Big-Instance it
considers the GL (w). It constructs the lists L0 based on the already updated f after solving
the Small-Instance. It starts with the empty lists E, L0 . For each vertex (y; ak1 , a2 ) ∈ GL (w)
it does the following :
(a) If (y; ak1 , a2 ) ∈ GrL (w) and f (y; a01 , a02 , . . . , a0k ) changed from a2 to c2 in the Update-f
(after the Small-Instance) then add c2 into E(y). In this case we have Pl (y, c2 ) = {c2 }.
It is also possible that a2 = c2 and in this case a2 is added into E(y).
(b) If (y; ak1 , a2 ) 6∈ GrL (w), i.e. (a, a2 ) 6∈ L(x, y) then add f (y; ak1 , a2 ) into E(y). Now in this
case the f (y; ak1 , a2 ) is added into Pl (y, a2 ).
At the end the algorithm sets L0 (y) = Ef (y). Item (b) ensures that we do not repeat
part of the work done in the Small-Instance. The necessary information after the recursive
call for Small-Instance are still available in Pl lists (see Figure 1 middle). Now it runs
the PreProcessing and in particular the ArcConsistency on G0 , H, L0 to remove unnecessary
elements in L0 . Recall that G0 is the induced sub-digraph of G obtained by the projection
of GL (w) on the first coordinates. Note that because of condition in (a) we only need
to have elements d ∈ L0 (z) where (z; bk1 , b2 ) ∈ GL (w) \ GrL (w), (y; ak1 , a2 ) ∈ GrL (w) where
(c, d) ∈ L0 (y, z) and c ∈ L0 (y). This is achieved by running the ArcConsistency on lists L0 .
Note that by definition, L0 (x) does not contain a because we know that no k-tuple in x has
its f value as a. Therefore the resulting instance is smaller than the original one.
In the Big-Instance we pass f |L0 as f 0 . At the end the algorithm updates f according
to Pl lists as described for the Small-Instance and it removes a from L(x). We argue that
the changes to f can be extended upon the changes occurred to f after solving the SmallInstance. Note that all the information that are needed in the Update-f function can be
obtained by looking at the current values of the Pl lists.

11

c1

c2

c3

a04

b04

d04

c

a4

b4

d4

f (x; b, b, a) = c

a

a2

b2

d2

f (y; a1 , a1 , a2 ) = a4
f (y; a01 , a01 , a02 ) = a04

a01

b01
b1

a1

b

d01

a01

f (y; a4 , a4 , a04 ) = c1
a4 , a04 ∈ Pl (y, a2 )
c1 ∈ Pl2 (y, a2 )
a4 , a04 , c1 ∈ L0 (y)
f (z; b4 , b4 , b04 ) = c2
b4 , b04 ∈ Pl (y, b2 )
c2 ∈ Pl2 (z, b2 )
b4 , b04 , c2 ∈ L0 (z)

f (z; b1 , b1 , b2 ) = b4
f (z; b01 , b01 , b02 ) = b04

d1

b01

d01

b

a1

b1

d1

x

y

z

u

f (u; d1 , d1 , d2 ) = d4
f (u; d01 , d01 , d02 ) = d04

f (u; d4 , d4 , d04 ) = c3
d4 , d04 ∈ Pl (u, d2 )
c3 ∈ Pl2 (u, d2 )
d4 , d04 , c3 ∈ L0 (u)

c1

c2

c3

c4

a04

b04

d04

e004

f (x; b, b, a0 ) = c0
f (x; b, b, a) = c
c

0

f (z; b1 , b1 , b2 ) = b4
f (z; b01 , b01 , b02 ) = b04
f (z; b4 , b4 , b04 ) = c2

e04
b4

a4

c

d4
e02

b2

a2

a
a01

b01
b1

a1

b

d2

a01

b01

d01

e01

d1

e1

d01

e01

a0
a

f (u; d1 , d1 , d2 ) = d4
f (u; d01 , d01 , d02 ) = d04
f (u; d4 , d4 , d04 ) = c3

b

f (v; e1 , e1 , e02 ) = e04
f (v; e01 , e01 , e02 ) = e004
f (v; e04 , e04 , e004 ) = c4

b

a1

b1

d1

e1

b

x

y

z

u

v

x

L0 (y) = c1
c3 ∈ L0 (u)

L0 (z) = c2

e04 , e004 , c4 ∈ L0 (v)

Figure 1: The top figure is an example of small-instance. The middle figure : example of biginstance.

e3
e2
e1

a03
a02
a01

b03
b02
b01

d03
d02
d01

c1

c2

c3

a04

b04

d04

f (x; e1 , e2 , e3 ) = a

f (x; e1 , e2 , e3 ) = c
change

c

a4

b4

f (y; a01 .a02 , a03 ) = a2

f (y; a01 .a02 , a03 ) = c1

f (z; b01 , b02 , b03 ) = b2

f (z; b01 , b02 , b03 ) = c2

f (u; d01 , d02 , d03 ) = d2

f (u; d01 , d02 , d03 ) = c3

d4

a

a2

b2

d2

x

y

z

u

Figure 2: Updating f based on the result of the recursion.

12

Algorithm 3 Initialize Pl lists and call Remove-NM
1: function RemoveNotMinority(G, H, L, f )
2:
Input: digraphs G, H, lists L and, weak nu homomorphism f : G × H k → H
3:
For every y ∈ V (G) and every a1 ∈ L(y) set Pl (y, a1 ) = ∅.
. Pl lists are global
4:
Remove-NM(G, H, L, f )
. call by reference for L, f , i.e, the changes to f, L will be reflected to
RemoveNotMinority function

Algorithm 4 updating f so that it remains a homomorphism of G × H k to H consistent
with L and for every x ∈ V (G), a0 , b0 ∈ L(x), f (x; a0k , b0 ) = b0
1: function Remove-NM(G, H, L, f )
2:
Input: digraphs G, H, lists L and, weak nu homomorphism f : G × H k → H
3:
while ∃x ∈ V (G), & a, b ∈ L(x), a 6= b s.t. f (w = (x; bk , a)) = c 6= a &
∃ w2 ∈ V (G × H k ) with f (w2 ) = a do
4:
Let (G0 , L0 , f 0 )= Small-instance(G, L, f, w)
5:
Remove-NM(G0 , H, L0 , f 0 )
6:
for all y ∈ G0 , d ∈ L0 (y) do set Pl (y, d) = {d}.
7:
Update-f(L, Pl , f, x, a)
. Call by reference for f
0
0
0
8:
Let (G , L , f )= Big-instance(G, L, f, w)
9:
Remove-NM(G0 , H, L0 , f 0 )
10:
for all y ∈ G0 , d ∈ L0 (y) do set Pl (y, d) = {d}.
11:
Update-f(L, Pl , f, x, a)
12:
Remove a from L(x)
13:
PreProcessing(G, H, L)
. Update lists L after removing a

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

function Small-Instance(G, L, f, w )
Set G0 to be the induced sub-digraph of G with vertices y s.t. (y; ak1 , a2 ) ∈ GrL (w)
Create new empty lists E, L0 .
for all y ∈ V (G0 ) do
Set E(y) = {f (w1 = (y; ak1 , a2 ))|w1 ∈ GrL (w1 )}
Set L0 (y) = Ef (y)
. see definitions 2.4
0
for all y ∈ V (G ), a1 ∈ L(y) do
Pl (y, a1 ) = {f (w1 = (y; dk , a1 ))|w1 ∈ GrL (w)}
Set f 0 = f |L0
. see definitions 2.5
0
0
0
Return (G , L , f )

13

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

function Big-Instance(G, L, f, w )
Set G0 to be the induced sub-digraph of G with vertices y s.t. (y; ak1 , a2 ) ∈ GL (w)
Create new empty lists E, L0 .
for all w1 = (y; ak1 , a2 ) ∈ GrL (w) do
add c2 into E(y), where f (w1 = (y; ...)) was initially a2 and now f (w1 ) = c2 .
. Happened in Update-f function. Pl (y, c2 ) = {c2 } and possible that c2 = a2
for all y ∈ V (G0 ) do
E(y) = E(y) ∪ {f (w1 )|w1 = (y; ak1 , a2 ) ∈ GL (w) \ GrL (w)}
L0 (y) = Ef (y)
for all y ∈ V (G0 ), a2 ∈ L(y) s.t. (a, a2 ) 6∈ L(x, y) do
Pl (y, a2 ) = {f (w1 )|w1 = (y; ak1 , a2 )) ∈ GL (w)}
. w1 ∈ GL (w) \ GrL (w)
Set f 0 = f |L0
PreProcessing(G0 , L0 ) and Return (G0 , L0 , f 0 )

function Update-f(L, Pl , f, x, a )
. In Small-Instance GPl (x, a, c)
Construct GPl (x, a, d)
Initialize and empty stack ST
ST.Push((x, a, d)) and set V isit[(x, a, d)] to true
while ST is not empty do
v = (y, a1 , c1 ) = ST.P op()
for all (a01 , a02 , . . . , a0k ) ∈ L(y) s.t f (y; a01 , a02 , . . . , a0k ) = a1 do
set f (y; a01 , a02 , . . . , a0k ) = c1
for all v 0 where vv 0 ∈ A(GPl (x, a, d)) do
if V isit[v 0 ] = f alse then
Set V isit[v 0 ] to true and
ST.P ush(v 0 )

14

Description of the Algorithm 4 line by line
3. We go through list of each vertex x and take a, b with f (x; bk , a) 6= a. Going to
modify f so we don’t need a in the list of x. Note that we should take a such that
∃ f (w1 = (x; e1 , e2 , . . . , ek )) = a.
4. We are going to modify f (w1 ) to c. Construct Small-Instance in which L0 (x) = {c}
only.
5. We call to solve the same problem for instance G0 , H, L0 , f 0 . Here f 0 is the restriction
of f over the k-tuples in L0 . f 0 is a homomorphism from G × H k to H and consistent
with the lists L0 .
6. At this point each L0 (y) is either singleton or for every d, d0 ∈ L0 (y) we have f 0 (y; d0k , d) =
d. That’s why we set Pl (y, d) = {d}.
7. We Update f based on the Pl lists. Pl has the information of what should be the new
value for f (y, a01 , a02 , . . . , a0k ) that was initially a2 . The Update to f is with respect to
the Small-Instance. At this point no k-tuple in L(x) has f value a.
8. In order to update f everywhere we construct the Big-Instance. Since we have run the
Remove-NM for Small-Instance, the Big-Instance is smaller than the original instance.
L0 (x) does not have a.
11. Update f based on the Pl lists. Now at this point f is a homomorphism from G × H k
to H and consistent with the lists L and at this point no k-tuple in L(x) has value a.
12. At this point we remove a from L(x).
13. Since we have removed a from L(x) the L lists should be updated.
2–3. [Small-Instance:] To construct G0 and create the L0 lists.
4–6. [Small-Instance:] To make sure L0 is closed under f we set L0 (y) = Ef (y) for every
y ∈ V (G0 ); the image of each k-tuple in L0 (y) should be in L0 (y). Set f 0 to be the same
as f in L0 lists.
7–8. [Small-Instance :] Fill out Pl lists for Small-Instance.
9. [Small-Instance :] Set f 0 to be the the restriction of f on L0 lists.
4–8. [Big-Instance :] First we look at every w1 = (y; ak1 , a2 ) ∈ GrL (w). If the f value of some
k-tuple in y changed from a2 to c2 (when updating f after running Small-Instance)
then we need to add c2 into L0 (y). The goal is not to recompute L0 and recompute Pl
lists in Small-Instance.

15

11–13. [Big-Instance :] We update Pl for those Pl (y, a2 ) that have not been set in lines 4–7.
In other words, for we go through w1 = (y; ak1 , a2 ) ∈ GL (w) \ GrL (w) and add f (w1 )
into Pl (y, a2 ).
2. [Update-F :] Construct the digraph GPl (x, a, d). In the Small-Instance Pl (x, a) is c. In
the Big-Instance instead of c (when call recursively) we may have Pl (x, c) = c1 and
finally we may end up having d ∈ Plt (x, a) where Pl (x, d) = {d}.
4. [Update-F :] We start a depth first search DFS (using stack ST) starting from (x, a, d).
5–7. [Update-F :] Pop an element v = (y, a1 , c1 ) from the top of ST and if f (w1 ) = a1 for
w1 = (y; a01 , a02 , . . . , a0k ), then we change f (w1 ) to c1 (the f value of each such w1 is
changed once).
8–9. [Update-F :] We look at each neighbor of v in GPl (x, c, d) and if we have not visited
that neighbor we push it on the top of the stack ST.

2.2 Minority Algorithm (RemoveMinority)
In this section we show that once the minority case has been reached in our main algorithm,
we can reduce to an already solved setting for homomorphism testing – namely that of the
Maltsev case. We note that this section is independent of the rest of the algorithm.
Note that at this point for every a, b ∈ L(x) we have f (x; bk , a) = a and in particular when
a = b we have f (x; a, a, . . . , a) = a (idempotent property). This is because when a is in L(x)
then it means the Remove-NM procedure did not consider a and in fact did not change the
value of f (x; ...) from a to something else. Note that for the argument below we just need
the idempotent property for those vertices that are in L(x), x ∈ V (G).
A ternary polymorphism h0 is called Maltsev if for all a 6= b, h0 (a, b, b) = h0 (b, b, a) = a.
Note that the value of h0 (b, a, b) is unspecified by this definition.
Let G and H be as input to Algorithm 1, and suppose line 6 of the algorithm has been
reached. We define a homomorphism h : G × H 3 → H consistent with the lists L by setting
h(x; a, b, c) = f (x; a, b, b, . . . , b, c) for a, b, c ∈ L(x). Note that because f has the minority
property for all x ∈ G, a, b ∈ L(x), h is a Maltsev homomorphism consistent with the lists
L.
Note that for the argument below we just need the idempotent property for those vertices
that are in L(x), x ∈ V (G).
Let G0 be the structure obtained from G by making each arc a different binary relation.
In other words, G0 has vertices V (G) and |E(G)| binary relations Re , e ∈ E(G), where
Re = {xy} if e is the arc e = xy.
Let H 0 be the structure where V (H 0 ) is the disjoint union of L(x), x ∈ V (G), and there
are also |E(G)| binary relations Se , e ∈ E(G), where Se is the set of all ordered pairs ab with
ab ∈ E(H), a ∈ L(x), b ∈ L(y), where e = xy. Note that |V (H 0 )| ≥ |V (G0 )| if each L(x) is
non-empty. This may seem unusual for the homomorphism setting, but is certainly allowed.

16

Now note that there is an L-homomorphism of G to H (i.e., a list homomorphism consistent
with lists L) if and only if there is a homomorphism of G0 to H 0 . Homomorphisms of such
structures are mappings f : V (G0 ) → V (H 0 ) such that xy ∈ Re implies f (x)f (y) ∈ Se for all
e ∈ E(G).
Finally, note that the structure H 0 has a Maltsev polymorphism h0 of the ordinary kind.
Indeed, let hx be our Maltsev polymorphisms defined on L(x) by setting hx (a, b, c) =
h(x; a, b, c). We let h0 (a, b, c) = h(x; a, b, c) if a, b, c are from the same L(x), and for a, b, c
not from the same L(x) define h0 (a, b, c) = a unless a = b, in which case define it as
h0 (a, b, c) = c. The definition ensures that h is Maltsev. To check it is a polymorphism, note
that aa0 , bb0 , cc0 ∈ Se is only possible if a, b, c ∈ L(x), a0 , b0 , c0 ∈ L(y), where e = xy. For
those, we have the polymorphism property by assumption.
Now we have a structure with a Maltsev polymorphism, so the Bulatov-Dalmau [BD06]
algorithm applies and solves the homomorphism problem. Note that Corollary 4.2 of the
Bulatov-Dalmau paper explicitly mentions that it is polynomial in both the sizes of G and
H.
Therefore we have the following theorem.
Theorem 2.6 Suppose h : G × H k → H is a minority homomorphism consistent with lists
L on G. Then the existence of an L-homomorphism of G to H can be decided in polynomial
time.
Remark : We have communicated with the authors of [BD06] and they confirmed that
indeed we can apply their algorithm as explained above. We note that it is also possible
to give a direct algorithm for the minority case that is similar to how we handle the “not
minority” case.

3 Proofs
3.1 PreProcessing and List Update
We first show that the standard properties of consistency checking remain true in our setting
– namely, that if the PreProcessing algorithms succeed then f remains a homomorphism
consistent with the lists L if it was before the PreProcessing.
Lemma 3.1 If f is a homomorphism of G × H k → H consistent with L then f is a homomorphism consistent with L after running the pre-processing.
Proof: We need to show that if a1 , a2 , . . . , ak are in L(y) after the pre-processing then
f (y; a1 , a2 , . . . , ak ) ∈ L(y) after the pre-processing. By definition vertex a is in L(y) after
the pre-processing because for every oriented path Y (of some length m ) in G from y to a
fixed vertex z ∈ V (G) there is a vertex a0 ∈ L(z) and there exists a walk B in H from a to
a0 and congruent with Y that lies in L(Y ).

17

Let a01 , a02 , a03 , . . . , a0k ∈ L(z). Let Ai , 1 ≤ i ≤ k be a walk from ai to a0i in L(Y ) and
0
congruent to Y . Let Ai = ai , ai1 , a2i , . . . , am
i , ai and let Y = y, y1 , y2 , . . . , ym , z.
Since f is a homomorphism consistent with L before the pre-processing, f (y; a1 , a2 , . . . , ak ),
0
0
0
m
m
f (y1 ; a11 , a12 , . . . , a1k ), . . . , f (yi ; ai1 , ai2 , . . . , aik ), . . . , f (ym ; am
1 , a2 , . . . , ak ), f (z; a1 , a2 , . . . , ak ) is
a walk congruent with Y . This would imply that there is a walk from f (y; a1 , a2 , . . . , ak ) to
f (z; a01 , a02 , . . . , a0k ) congruent with Y in L(Y ) and hence f (y; a1 , a2 , . . . , ak ) ∈ L(y).

By a similar argument as in the proof of Lemma 3.1 we have the following lemma.
Lemma 3.2 If f is a homomorphism of G×H k → H, consistent with L and a1 , a2 , . . . , ak ∈
L(x), b1 , b2 , . . . , bk ∈ L(y), and (ai , bi ) ∈ L(x, y), 1 ≤ i ≤ k, after pre-processing then
(f (x; a1 , a2 , . . . , ak ), f (y; b1 , b2 , . . . , bk )) ∈ L(x, y) after the pre-processing.
Lemma 3.3 The pair list L0 (x, y) is not empty.
Proof: Let w = (x; bk , a) with f (w) = c 6= a. Suppose (b, a1 ) ∈ L(x, y), and a2 ∈ L(y).
Now by definition (Small-Instance or Big-Instance) there exists a vertex w1 = (y; ak1 , a2 ) in
GL (w) and hence f (w1 ) ∈ L0 (y). This would mean (c, f (w1 )) ∈ L0 (x, y) because there exists
a path from c to f (w1 ) in L0 (Y ) where Y is a path from x to y in G0 .


3.2 RemoveNotMinority Correctness Proof
The main argument is proving that after RemoveNotMinority function, f still is a homomorphism consistent with the lists and has weak nu property (Lemma 3.4). Moreover, after
RemoveNotMinority there still exists a homomorphism from G to H if there was one before
RemoveNotMinority (Lemma 3.5).
Lemma 3.4 If f is a homomorphism of G × H k → H, consistent with L and with weak nu
property before RemoveNotMinority then the modified f remains a homomorphism consistent
with L and with weak nu property afterwards.
Lemma 3.5 If there is a homomorphism g : G → H then there is a homomorphism from
G to H after RemoveNotMinority.
3.2.1 Proof of Lemma 3.4
It is enough to show the following :
f is a homomorphism of G × H k → H consistent with the lists (with weak nu
property) after removing a from L(x) in the while loop in Algorithm 4.
We need to address items 1,2,3 below.
1. The weak nu property is preserved.
2. The Running time of Remove-NM function is O(|G|3 |H|k+1 ).

18

3. The adjacency property is preserved: for an arbitrary arc yz ∈ A(G) (zy ∈ A(G))
and for every a01 , a02 , . . . , a0k ∈ L(y) and b01 , b02 , . . . , b0k ∈ L(z) where a0i b0i ∈ A(H) (b0i a0i ∈
A(H)), 1 ≤ i ≤ k, we have f (y; a01 , a02 , . . . , a0k )f (z; b01 , b02 , . . . , b0k ) ∈ A(H)
(f (z; b01 , b02 , . . . , b0k )f (y; a01 , a02 , . . . , a0k ) ∈ A(H)).
Proof of 1 : Since in the Update-f function we change the value f (y; a01 , a02 , ..., a0k ) from
a2 to f (y; ak1 , a2 ) for every k-tuple a01 , a02 , . . . , a0k ∈ L(y), we change f (y; b1 , b1 , . . . , b1 , b2 ) =
f (y; b1 , b1 , . . . , b2 , b1 ) = · · · = f (y; b2 , b1 , . . . , b1 ) to the same value. Therefore f still has the
weak k-nu property.
Proof of 2 : In the Algorithm 4 we consider pairs (x, a) ∈ V (G × H) where a ∈ L(x) and
∃w2 ∈ V (G × H k ) with f (w2 ) = a.
In the Update-F function for every y ∈ V (G0 ) and every a2 ∈ L(y), such that (y; ak1 , a2 ) ∈
GL (w), the f value of w1 with f (w1 ) = a2 is going to change to some new value. Once
the f value of some k-tuple in L(y) changed from a2 to something else, there would be no
k-tuple in L(y) that its value is set to a2 in the further steps of the Algorithm. Moreover,
for every (a, e) ∈ L(x, y) the value of f for w1 , w2 with f (w1 ) = a and f (w2 ) = e would
change simultaneously. In other words, if (y; ak1 , a2 ) is in GL (w) and (y; bk1 , a2 ) ∈ GL (w1 ) for
some w1 = (z; dk , e) then there exists some w10 = (z; d0k , e) ∈ GL (w). This implies that in
the main while loop we do not consider any w100 = (z; d00k , e) because there exists no k-tuple
b01 , b02 , . . . , b0k in L(z) such that f (z; b01 , . . . , b0k ) = e. This means that the vertices of GL are
partitioned and when we solve instance G0 , H, L0 , f 0 recursively we deal with one of these
partitions.
Considering all these partitions together, in the worst case we end up processing all the
vertices in G − x together with their lists to be able to process a ∈ L(x). At each step
one element (y, aj ), aj ∈ L(y), y ∈ V (G) is processed (aj is removed) to be able to process
a ∈ L(x); remove a from L(x). The actual work is writing down some new lists (each write
down takes O(|A(G)||H k |)). The overall size of the new lists is one smaller than the previous
lists. So the overall running time is O(|G||A(G)||H|k+1 ). Note that |A(G)| ∈ O(|G|2 ). By
considering the running time of the PreProcessing we conclude that the overall running time
is O(|G|3 |H|k+1 ).
Proof of 3 : Let ak+1 = f (y; a01 , a02 , . . . , a0k ) and bk+1 = f (z; b01 , b02 , . . . , b0k ). We need to show
ak+1 bk+1 ∈ A(H) when (y; a01 , . . . , a0k )(z; b01 , b02 , . . . , b0k ) is an arc of G × H k . In order to show
that we first prove the following claims. In Claims 3.6,3.7,3.8 at each step of the recursive call
we deal with some vertex x of G and two vertices a, b ∈ L(x) such that f (x; bk , a) = c 6= a,
and f (x; c, c, . . . , c) = c considered in Algorithm 4 (line 3). Moreover, the assumption is
that f is a homomorphism consistent with the lists L and if f (y; a01 , a02 , . . . , a0k ) = a1 then
f (y; a1 , a1 , . . . , a1 ) = a1 .
Claim 3.6 Let X : y = y, y1 , y2 , . . . , yn , x be a walk from a vertex y to vertex x in G.
Let C1 : c0 , c1 , c2 , . . . , cn , c and C2 : c00 , c01 , . . . , c0n , c be two oriented walks congruent to X

19

in L(X). Then f (y; ck0 , c00 ), f (y1 ; ck1 , c01 ), . . . , f (yi ; cki , c0i ), . . . , f (yn ; ckn , c0n ), f (x; c, c, . . . , c) is a
walk in L(X) from c0 = f (y; ck0 , c1 ) to c and congruent to X.
Proof: Since f is a homomorphism consistent with the lists, for every 0 ≤ i ≤ n − 1 we
have f (yi ; cki , c0i )f (yi+1 ; cki+1 , c0i+1 ) ∈ A(H) when yi yi+1 ∈ A(G), ci ci+1 , c0i c0i+1 ∈ A(H), and
f (yi+1 ; cki+1 , c0i+1 )f (yi ; cki , c0i ) ∈ A(H) when yi+1 yi ∈ A(G), ci+1 ci , c0i+1 c0i ∈ A(H).

The following claim will be used to show that we can extend the update to f from the
Small-Instance to the Big-Instance.
Claim 3.7 Let W1 , W2 be two cycles from w = (x; bk , a) to w = (x; bk , a) in GL (w) with the
following conditions :
• W1 , W2 are congruent and both follow oriented cycle X : x, x1 , x2 , . . . , xn , x in G.
• the projection of W1 , W2 on the (k + 1)th coordinate yield the same closed walk B :
a, a1 , a2 , . . . , ai , . . . , an , a in L(X).
Let B 0 : a, a1 , a2 , . . . , ai , a0i+1 , a0i+2 , . . . , a0n , a0 be a walk in L(X) congruent with B such that
(a, a0i+1 ) 6∈ L(x, xi+1 ). Let ei = f (wi ) and e0i = f (wi0 ) where wi and wi0 are the ith vertices of
W1 , W2 respectively. Then there exist walks C1 , C2 from ei , e0i to c0 in L0 (X) (constructed in
Big-Instance) that are congruent to B 0 [ai , a0 ] and there exists a walk C from f (xi ; eki , e0i ) to
c0 = f (x; bk , a0 ) in L0 (X) and congruent to B 0 [ai , a0 ].
Proof: Let W3 be the quasi-path from w to w0 = (x; bk , a0 ) and congruent to W1 that follows
X, B 0 and such that the j th vertex of W3 is of form (y; dkj , a0j ), where (y; dkj , aj ) ∈ W1 and
a0j is the j-th vertex of B 0 . Let W4 be the quasi-path from w to w0 = (x; bk , a0 ) and con0
gruent to W2 that follows X, B 0 such that the j th vertex of W4 is of form (y; d0k
j , aj ), where
0
th
(y; d0k
vertex of B 0 . Let f (vi ) = ei and f (ui ) = e0i where vi is
j , aj ) ∈ W2 and aj is the j
the ith vertex of W3 and ui is the ith vertex of W4 . Now C1 : f (vi ), f (vi+1 ), . . . , f (vn ), c0
is a walk in L0 (X) and congruent to B 0 [ai , a0 ]. This is because we add f (vj ), i ≤ j ≤ n
(and c0 ) into L0 (X) in the construction of the Big-Instance, and L0 (X) is closed under f .
Similarly C2 : f (ui ), f (ui+1 ), . . . , f (un ), c0 is a walk in L0 (X) and congruent to B 0 [ai , a0 ]. Now
according to Claim 3.6 the walk C : f (xi ; eki , e0i ), f (xi+1 ; eki+1 , e0i+1 ), . . . , f (xn ; ekn , en ), c0 where
ej ∈ C1 and e0j ∈ C2 , i ≤ j ≤ n, is from f (xi ; eki , e0i ) to c0 and it is congruent to B 0 [ai , a0 ].
Note that C is in L0 (X[xi , xn ], x) ⊂ L(X).

Claim 3.8 Let X : x, x1 , x2 , . . . , xn , x be an oriented cycle in G containing vertex x. Suppose
f (x; bk , a0 ) = c0 . Let B : a, a1 , a2 , . . . , ai , . . . , an , a and B 0 : a, a1 , a2 , . . . , ai , a0i+1 , a0i+2 , . . . , a0n , a0
be two congruent walks in L(X) such that (a, a0i+1 ) 6∈ L(x, xi+1 ). Let t ≥ 1 be an integer such
that ci ∈ Plt (xi , ai ) (Pl constructed during the execution of Remove-NM). Then there exists
a walk in L0 (X) from ci to c0 congruent with B 0 [ai , a0 ].

20

c1

c2

c3

c4

c0
e01

e02
e2

e03
e3

e04
e4

e1

c

a1

a
d01

a2
d02

d1

b
d01

d2
d02

a03

a04

a0

a3

a4

a

d03

d04

d3

d4

d03

d04

b

b

d1

d2

d3

d4

b

x

y

z

u

v

x

f (y; d1 , d1 , a1 ) = e1
f (y; d01 , d01 , a1 ) = e01

f (u; d3 , d3 , a03 ) = e3
f (u; d03 , d03 , a03 ) = e03
f (u; e3 , e3 , e03 ) = c3

Figure 3: An illustration for Claim 3.7.
Proof: Let W1 , W2 be two cycles from w = (x; bk , a) to w = (x; bk , a) in GL (w) that both
follow B and such that f (wi ), f (wi0 ) ∈ Pl (xi , ai ) where wi is the ith vertex of W1 and wi0 is
the ith vertex of W2 . According to Claim 3.7, there exist walks C1 , C2 in L0 (X) from c1 , c2 to
c0 where c1 , c2 ∈ Pl (y, ai ) and there exists a walk C 0 in L0 (X) from c3 = f (y; ck1 , c2 ) to c0 and
congruent with B 0 [ai , a0 ]. Now according to the Remove-NM in the recursive call we place
c3 into L0 (y) and also into Pl (y, c2 ). By applying Claim 3.6 on c3 , c1 we conclude that there
exists a walk from f (y; ck1 , c3 ) to c0 and congruent to C1 if the recursive call considers vertex
(y; ck1 , c3 ). We note that since L0 (y) is closed under f , f (y; ck1 , c3 ) ∈ L0 (y).
Note that in this case Pl2 (y, ai ) would contain c3 . Similarly we would have a walk from
f (y; ck3 , c1 ) to c0 congruent to C1 if the recursive call considers vertex (y; ck3 , c1 ). By repeatedly
applying Claim 3.6 we conclude that there exists a walk in L0 (X) from ci to c0 and congruent
to B 0 [ai , a0 ]

Claim 3.9 Consider the current lists L at some stage of Remove-NM algorithm. For every
(y, a2 ) where (y; ak1 , a2 ) ∈ GL (w) there exists d ∈ L0 (y) ∩ Plt (y, a2 ) for some integer 1 ≤ t ≤
|L(y)| such that Pl (y, d) = {d}.
0
Proof: Let a01 ∈ Pl (y, a2 ). Suppose there exists a02 ∈ Pl (y, a2 ) such that c1 = f (y; a0k
1 , a2 ) 6=
0
0
0
a2 . Now in the recursive call Pl (y, a2 ) is updated (we write down some vertices of L into
Pl (y, a02 )) and in particular c1 ∈ Pl (y, a02 ) and by definition c1 ∈ Pl2 (y, a2 ). To see that, L0 is
a subset of L where every a02 ∈ L0 (y) L0 is on a walk C 0 from c inside L0 (Y ). Here Y is a
walk in G that some path W in GL (w) from w to (y; ak1 , a02 ) follows Y, C 0 . Now according to
construction of Small-Instance and Big-Instance with respect to lists L0 , c1 ∈ Pl (y, a02 ).

21

Since at line 6 and 10 of the Remove-NM we set Pl (y, d) = {d}, and because at each step
of the recursion one element from L0 (y) will disappear from the rage of f 0 = f |L0 , after some
t ≤ |L| steps of the nested recursive calls for all d, e ∈ Lt , f (t) (y; dk , e) = e. Here Lt are
the lists passed to the Remove-NM after t steps of recursions, and f t is the corresponding
homomorphism (from G × H k to H) to Lt . Note that all the information that are needed in
the Update-f function can be obtained by looking at the current values of the Pl lists.

From Small-Instance to Big-Instance We need to argue that in the Big-Instance the
modification to f would be consistent with the update to f after calling the Remove-NM
on Small-Instance. In the function Update-f(L,Pl ,f, x, a) after Small-Instance we follow an
oriented path inside L(X) where X is an oriented cycle in G containing x ∈ V (G). We
modify the f value for (y; a01 , a02 , . . . , a0k ) from a2 to some element d2 ∈ Plt (y, a2 ) where y ∈ X
and (y, a2 , d2 ) is reachable from (x, a, d) in GPl (x, a, d) (t and d2 exist according to Claim
3.9). Now consider a vertex b2 in L(z) where yz ∈ A(X) but (a, b2 ) 6∈ L(x, z). In the
Big-Instance we consider an oriented path B 0 : a2 , b2 , . . . , a0 such that
• B 0 is congruent to yX[z, x] (portion of X from y to x) in L(X)
• a directed path W from (y; ak1 , a2 ) to (x; bk , a0 ) follows B 0 .
By Claim 3.8, there exists a walk C 0 from d2 ∈ Plt (y, a2 ) to c0 in L0 (X) which is congruent to
B 0 . This would imply that if we fix vertex c0 in L0 (x) in the recursive call, then corresponding
to B 0 in L(X) we would have walk C 0 in L0 (X) and the f value along B 0 would change to
elements in C 0 . Note that we may change the f value for some k-tuples in x from c0 ∈ L(x).
To be more precise, we would have the elements in C 0 to be considered for further changes
to f . Therefore the updates in f in the Big-Instance can be build upon the updated f on
the Small-Instance.
Why the adjacency preserved : Suppose the value of f (y; a01 , a02 , . . . , a0k ) changed from
a2 to c2 ∈ Plt (y, a2 ). Let b2 = f (z; b01 , b02 , . . . , b0k ). We note that a2 b2 ∈ A(H) because f was
initially a homomorphism consistent with the lists. Since f (y; b01 , b02 , . . . , a0k ) changed from
a2 to c2 , we have (y, a2 , c2 ) ∈ GPl (x, a, d).
There exists a1 ∈ L(y) such that (b, a1 ) ∈ L(x, y) (according to Lemma 3.3 at each step
of the recursion) and hence (y; ak1 , a2 ) ∈ GL (w). Let c2 ∈ Plt (y, a2 ) (c2 , t exist by Claim
3.9 ) and let c02 ∈ Pl (y, a2 ). Now there exists a vertex b1 ∈ L(z) such that (b, b1 ) ∈ L(x, z)
and a1 b1 ∈ A(H). According to Remove-NM we add an out-neighbor of c02 into L0 (z) and
hence Pl (z, b2 ) has an out-neighbor of c02 say d02 . By following the recursive calls we would
conclude that there exists some vertex d2 ∈ Plt (z, a2 ) which is an out-neighbor of c2 and
Pl (y, d2 ) = {d2 }. Therefore according to the function Update-f (note that each (y, a2 ) is
visited once in Update-f) we change f (z; b01 , b02 , . . . , b0k ) from b2 to d2 .

22

Closing remark Once we change the value of f (x; a1 , a2 , . . . , ak ) from a to c then potentially we need to modify the value for f (y; b1 , b2 , . . . , bk ) from an out-neighbor of a, say
a0 in L(y) to an out-neighbor of c. As far as the modifying f is concern it would yield the
same result if we start from (x; b, . . . , a, b, . . . , b), a is in the ith coordinate.

3.2.2 Proof of Lemma 3.5
It is enough to show that the following:
If there is a homomorphism g : G → H with g(x) = a then there is a homomorphism from G to H after removing a from L(x) in Algorithm 4 (line 12).
The Update-f function performs a depth first search in GPl (x, a, c), c = f (w, bk , a). For
simplicity we may assume that c ∈ Plt (x, a) with Pl (x, c) = {c}. The argument is similar for
the case when (x, a, d) ∈ GPl . We note that if vertex (y, a2 , c2 ) is visited in Update-f function
first and then after a while a vertex (y; a2 , c02 ) is visited then no changes would apply into f .
This is because there is no k-tuple a01 , a02 , . . . , a0k in L(y) such that f (y; a01 , a02 , . . . , a0k ) = a2 .
Let G3 be the induced sub-digraph of GPl (x, a, c) with the arcs ê = (y, a1 , c1 )(z, b1 , c2 )
such that ê ∈ A(GPl (x, a, c)) and c1 b1 6∈ A(H) when a1 b1 ∈ A(H) and b1 c1 6∈ A(H) when
b1 c1 ∈ A(H). Note that G3 contains (x, a, c).
Let G0 be the induced sub-digraph of G with vertices y such that (y, g(y), c2 ) ∈ G3 is
visited for the first time by the depth first search in function Update-f.

Observation 3.10 Let X be an oriented cycle in G containing vertex x. By construction
of Small-Instance, corresponding to g(X) say B, there exists a closed cycle C containing c
and congruent to B. Here g(X) is the image of X under g.
For every vertex y ∈ G0 set h(y) = c2 where (y, g(y), c2 ) ∈ GPl (x, a, c). For every y ∈
V (G) \ V (G0 ) set h(y) = g(y).
We need to show that h is a homomorphism from G to H. Let zz 0 (z 0 z) be an arc of
G where z ∈ V (G0 ). We only need to consider the case z ∈ V (G0 ). By definition we have
(z, g(z), c2 ) ∈ G3 .
Since zz 0 is an arc of G and g is a homomorphism from G to H, g(z)g(z 0 ) ∈ A(H).
If h(z)g(z 0 ) ∈ A(H) then we are done because in this case we have z 0 6∈ G0 . Suppose
h(z)g(z 0 ) 6∈ A(H). Now in the Small-Instance there exist vertices w1 = (z; ak1 , g(z)) and
w2 = (z 0 ; bk1 , g(z 0 )) that are in GrL (w). This means there exists a vertex c02 in L0 (z 0 ) that is an
out-neighbor of c2 and hence by definition (z 0 , g(z 0 ), c02 ) ∈ G3 . This would imply z 0 ∈ V (G0 )
and hence h(z 0 ) = c02 , implying that h(z)h(z 0 ) ∈ A(H).
Note that in the special case when z 0 = x we have g(z 0 ) = a and by the Observation above
we have h(z 0 ) = c. Therefore h is a homomorphism from G to H with h(x) = c.


23

3.3 Proof of Theorem 1.1
By Lemma 3.5 we preserve the existence of a homomorphism from G to H after Algorithm
4. By Lemma 3.4 f is still a homomorphism from G × H k → H consistent with the lists L
of G after Algorithm 4. Now we can apply Theorem 5.4. We observe that the running time
of PreProcessing function is O(|G|3 |H|2 ).
According to the proof of Lemma 3.4 (2) the running time of Algorithm 4 is O(|G|3 |H|k+1 ).
The running time of Algorithm 2.2 (O(|G||A(G)||H|k+1 ). Therefore the running time of the
Algorithm 1 is O(|G|3 |H|k+1 ).

4 Additional Algorithms and Proofs (New Minority
Algorithm)
This section collects additional statements and proofs mainly related to new Minority algorithm. We develops a direct algorithm to handle the minority case in our main algorithm.
Of course, it would be easier to appeal to Bulatov-Dalmau Maltsev result as explained in
Subsection 2.2.
A direct proof for Theorem 5.4 Let M 3 be the digraph of triple (y, c, d), x ∈ G, c, d ∈
L(y). There is an arc from (y, c, d) to (y 0 , c0 , d0 ) where yy 0 ∈ A(G), cc0 , dd0 ∈ A(H) and
cd0 6∈ A(H) or y 0 y ∈ A(G) and c0 c, d0 d ∈ A(H), d0 c 6∈ A(H). Note that M 3 is a graph but we
view M 3 as digraph and when we talk about a path in M 3 we mean an oriented path that
reflect the direction of the edge xy when (y, c, d)(y 0 , c0 , d0 ) is an arc of M 3 . Let Gx (a, b) be
the strong component of M 3 containing (x, a, b) such that for each vertex (y, c, d) ∈ Gx (a, b),
(a, c) ∈ L(x, y) and (b, d) ∈ L(x, y). We say a strong component Gx (a, b) of M 3 is invertible
if both (x, a, b) and (x, b, a) are in Gx (a, b).
Again the idea is similar to the one handling the RemoveNotMinority case. At each step we
consider a vertex x of G and two vertices a, b ∈ L(x) and try to eliminate one of the a, b from
L(x). To decide whether remove a or b we construct an instance of the problem say (G0 , H, L0 )
and solve this instance recursively. Based on the existence of a L0 -list homomorphism from
G0 to H we decide to remove a or b. Depending on Gx (a, b) being invertible or not two
different instances for the sub-problem are constructed. At the end we have singleton lists
and if there is a homomorphism from G to H with the singleton lists then success otherwise
we report there is no homomorphism from G to H. We denote the underline graph of digraph
G by U N (G). If Gx (a, b) is invertible we construct a new instance G0 , H, L0 and to construct
the lists L0 we use the Maltsev property.
Lemma 4.1 Let X be an oriented path in G and let B, C, D be three walks in L(X) all
congruent to X where B is from a to c and C is from b to c and D is from b to D. Then
there exists a walk E from a to d in L(X) that is congruent with X.

24

Algorithm 5 RemoveMinority – Using Matlsev Operations
1: function RemoveMinority(G, H, L)
2:
Input: x, a, b such that f (x; bk |i←a ) = a
3:
Define Maltsev consistent homomorphism h : G × H 3 → H where
h(x; a, b, c) = f (x; a, b, b, . . . , b, c) for a, b, c ∈ L(x).
4:
while ∃ x ∈ V (G) with |L(x)| ≥ 2 do
5:
Matlsev(G, H, L )
6:
if ∃ a list homomorphism from G to H then return True
7:
else return False.

8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

20:
21:
22:
23:
24:
25:
26:

function Maltsev(G, H, L)
Let a, b ∈ L(x) be two distinct vertices. Construct Gx (a, b).
if Gx (a, b) is not invertible then
Set L0 (x) = a and L0 (y) = ∅ for every x 6= y.
Set G00 = ∅, and let G0 be an induced sub-digraph of G constructed as below.
for all y ∈ G s.t. ∃ a path from (x, a, b) to (y, c, d) in Gx (a, b) do
add y to G0 and c to L0 (y),
let yy 0 an arc of G0 when (y, c, d)(y 0 , c0 , d0 ) ∈ Gx (a, b).
if Gx (a, b) is invertible then
Set L0 (x) = a and L0 (y) = ∅ for every x 6= y.
Let G00 be the set of vertices y ∈ V (G) where (y, c, d, e) lies on an oriented path
P from (x, a, b, b) to (x, b, b, a) in U N (G × H 3 ) s.t. no intermediate vertex in P
is (x, a0 , b0 , c0 ) for a0 , b0 , c0 ∈ L(x)
for all arc (y, c, d, e)(y 0 , c0 , d0 , e0 ) ∈ P do
add h(y, c, d, e) to L0 (y), h(y 0 , c0 , d0 , e0 ) to L0 (y 0 ), and add arc yy 0 (y 0 y) to G00
Let G0 be the induced sub-digraph of G with vertices
y ∈ G \ G00 and arcs yy 0 where (y, c, d)(y 0 , c0 , d0 ) ∈ Gx (a, b) and add c into L0 (y)
when (y, c, d) ∈ Gx (a, b)
if Matlsev(G0 ∪ G00 , H, L0 ) then
remove b from L(x)
else remove a from L(x).

25

Proof: By following B, C, D on the vertices in X and applying the definition of polymorphism h, we conclude that E exists.

Lemma 5.10 implies the following corollary.
Corollary 4.2 If (a, c) ∈ L(x, y) and (b, c), (b, d) ∈ L(x, y) then (a, d) ∈ L(x, y).
Lemma 4.3 The Algorithm 9 runs in O(|A(G)||H|k+1 ). Moreover, if there is a homomorphism g from G to H with g(x) ∈ {a, b} then there is a homomorphism from G to H after
removing a or b from L(x) according to Maltsev-(G, H, L, h).
Proof: We spend O(|G||H|k+1 ) to define h. For every pair a, b ∈ L(x) the algorithm construct an instance of the problem which takes O(|A(G)||A(H)|3 ). The algorithm is recursive
and the depth of the recursion in |G||H|. Now by similar analysis as in Algorithm 4 we
conclude that the running time of function Maltsev(G, H, L) is O(|G||A(G)||H|4 ) (replace
|A(H)| by |H|2 ). Therefore the running time of the Algorithm 2.2 is O(|A(G)||H|k+1 ).
First consider the case that Gx (a, b) is not invertible. The Algorithm 9 is recursive
but at each recursive call the size of the input decreases by at least one. This is because we
do not add b into L0 (x) and hence we have an instance (G0 , L0 , H) of the problem in which at
least one vertex has a smaller size list. We also note that once we make a decision to remove
a vertex from a list the decision is not changed. Therefore the overall procedure in this
case is polynomial (assuming in each call Gx (a, b) is not invertible). According to Maltsev(G, H, L, h) if G0 does not admit a homomorphism to H then there is no homomorphism
from G to H that maps x to a since G0 is a sub-digraph of G.
No suppose b is removed according to Maltsev-(G, H, L, h) and there exists a homomorphism g from G to H with g(x) = b. Let ψ be the homomorphism from G0 to H. Note that
ψ(x) = a.
Define G1 be a sub-digraph of G0 consists of the vertices y such that (y, ψ(y), g(y)) is
reachable from (x, a, b) in Gx (a, b).
Now for every vertex y ∈ G1 set φ(x) = ψ(x) and for every y ∈ G \ G1 set φ(y) = g(y).
Now let zz 0 be an arc of G. If none of the z, z 0 ∈ G1 then clearly since g is a homomorphism, φ(z)φ(z 0 ) ∈ A(H). If both z, z 0 ∈ G1 then again since ψ is a homomorphism, we have
φ(z)φ(z 0 ) ∈ A(H). Suppose z ∈ G1 and z 0 6∈ G1 . Since z ∈ G1 there exists a path in Gx (a, b)
from (x, a, b) to (z, ψ(z), g(z)). Now if ψ(z)g(z 0 ) is an arc then we are done. Otherwise
(z 0 , c, g(z 0 )) ∈ Gx (a, b) where c ∈ L(z 0 ) and ψ(z)c ∈ A(H) (note that since ψ(z) is in L(z) it
must have an out-neighbor in L(z 0 )). This would mean z 0 ∈ G1 , a contradiction. Note that
when z 0 = x and z ∈ G1 then because (ψ(z), a) ∈ L(z, x) we have ψ(z)a ∈ A(H).
Second consider the case that Gx (a, b) is invertible. Again as we argued in the
previous case the algorithm is recursive but at each recursive call the size of the input
decreases and once a decision made (removing a or b ) it won’t change.

26

Observe that if there exists a homomorphism g that maps x to a then for every closed
walk X from x to x, the image of g(X) is a closed walk from a to a in H. Since there is
a walk BB from b to b in L(X) congruent and since (a, b) ∈ L(x, x), there is a walk BA
in L(X) congruent to X. Now by Lemma 5.10 there is a walk AB from a to b in L(X)
and congruent with X. These would imply that there exists a path P in U (G × H 3 ) from
(x, b, b, a) to (x, a, b, b). Now according to the definition of G00 for every walk BB in L(X)
from b to b congruent with X we keep a walk AA in L0 (X) congruent with X and is obtained
by adding h(y, c1 , c2 , c3 ) into L0 (y) where (y, c1 , c2 , c3 ) is in P .
This would mean that in the list of L0 (X), corresponding to ψ(X) (ψ is a homomorphism
from G to H where ψ(x) = a if there exists one) we have a path from a to a in L0 (X).
Therefore if there exists no homomorphism from G0 ∪ G00 → H that maps x to a then there
is no homomorphism from G to H that maps x to a.
Now suppose b is removed according to Maltsev-(G, H, L, h) and there exists a homomorphism g from G to H with g(x) = b. Let ψ1 be the homomorphism from G0 to H and ψ2 be
a homomorphism from G00 to H. Note that ψ1 (x) = ψ2 (x) = a. First we show that there is
no arc e (forward or backward) from a vertex y in G0 to a vertex in G00 . If this is the case
then there is a walk Q from x to y and there is a walk Q0 from y to x. Now since yz is an
arc then Qee−1 Q0 is a closed walk from x to x and hence we should have added z into G00 .
Note that G00 consists of all the induced oriented cycles including x and also all the paths
reaching out of vertices of these cycles except x.
Define G1 be a sub-digraph of G0 consists of vertices y such that (y, ψ1 (y), g(y)) is reachable
from (x, a, b) in Gx (a, b).
Now for every vertex y ∈ V (G1 ) set φ1 (y) = ψ(y) and for every y ∈ V (G) \ V (G1 )
set φ1 (y) = g(y). Define G2 be a sub-digraph of G00 consisting of vertices y such that
(y, ψ2 (y), g(y)) is reachable from (x, a, b) in Gx (a, b).
Now for every vertex y ∈ V (G2 ) set φ2 (y) = ψ2 (y) and for every y ∈ V (G) \ V (G2 )
set φ2 (y) = g(y). And finally let φ(y) = φ1 (y) when y ∈ V (G0 ) and φ(y) = φ2 (y) when
y ∈ V (G00 ). Now let zz 0 be an arc of G. We need to verify that φ(z)φ(z 0 ) is an arc of H.
If none of the z, z 0 ∈ V (G1 ∪ G2 ) then clearly since g is a homomorphism, φ(z)φ(z 0 ) ∈
A(H). If both z, z 0 ∈ V (Gi ) (i = 1, 2) then again since ψi is a homomorphism, we have
φ(z)φ(z 0 ) ∈ A(H). Suppose z ∈ V (G2 ) and z 0 6∈ V (G2 ). Since z ∈ V (G2 ), there exists a
closed walk ZZ 0 that contains z where Z is a path from x to z and Z 0 is a walk from z
to x. Note that ψ2 (ZZ 0 ) is a walk from a to a in L(ZZ 0 ) and g(ZZ 0 ) is a walk from b to
b in L(ZZ 0 ) and since (b, a) ∈ L(x × x) there exists a walk BA in L(ZZ 0 ) congruent with
ZZ 0 . These would imply that corresponding to ZZ 0 there exists a path P from (x, b, b, a) to
(x, a, b, b) containing vertex (z, ψ2 (z), d, g(z)). Now since g(z) ∈ L(z) there exists a vertex
c ∈ L(z 0 ) such that g(z)c ∈ A(H) and there exists e0 ∈ L(z 0 ) such that dd0 ∈ A(H).
Now we add the two arcs (z, ψ2 (z), d, g(z))(z 0 , c, d0 , g(z 0 )), (z 0 , c, d0 , g(z 0 ))(z, ψ2 (z), d, g(z))
into P and hence we obtain a path P 0 from (x, b, b, a) to (x, a, b, b) that goes through vertex
(z 0 , c, d0 , g(z 0 )) and hence z 0 ∈ G00 . Now since φ2 (z)g(z 0 ) 6∈ A(H), by definition z 0 ∈ V (G2 ), a
contradiction.

27

As we argue before one can show that φ1 is also a homomorphism from G to H. Therefore
φ is a homomorphism from G to H with φ(x) = a.


5 Second Approach (none recursive algorithm)
5.1 An introduction to the Algorithm
In this section we introduce the main parts of our algorithm. We encourage the reader to
take time to read and internalize as much of this section as possible, while consulting the
figures that are referenced.
1. We associate to each vertex x ∈ V (G) a list L(x), with each L(x) initially V (H). We
also consider pair lists L(x, y), where (a, b) ∈ L(x, y) means that it may be possible for
x and y to simultaneously map to a and b (respectively) for the same homomorphism.
2. We let the polymorphism on H be specialized for each vertex in G. We define a
homomorphism f : G × H k → H, i.e. f (x; a1 , a2 , . . . , ak ) for x ∈ V (G) and a1 , ..., ak ∈
V (H). Initially f (x; a1 , ..., ak ) = φ(a1 , ..., ak ) where φ is the weak k-nu polymorphism
given to us. We call f a weak k-nu homomorphism from G to H (see Def 5.1).
3. PreProcessing. We perform standard consistency checks that are done in CSP algorithms to prune the lists L(x) for every x, and pair lists L(x, y) for each x and y.
4. We refine f and work towards building a homomorphism g from G to H. The main
loop in the algorithm picks a vertex x ∈ V (G) and tries to remove one of the vertices
a ∈ V (H) from consideration for being g(x). At any given time, we have lists L(x) ⊆ H
for each x ∈ V (G) that have the vertices in H that are being considered for g(x).
5. For a, b ∈ L(x), if f (x; b, b, ..., b, a) = a we say this is the minority case. The minority
case is similar to a case of the homomorphism problem that is already solved, namely
the setting where the underlying polymorphism is Maltsev (see subsection 5.4). We
thus have our main loop choose x, b, a where f (x; b, b, ..., b, a) 6= a and attempt to
remove a from consideration. If f (x; b, b, ..., b, a) = a then we leave it alone. This is
the first place the existence of weak k-nu would be essential.
6. The main procedure, then, is to take an x ∈ V (G), special a, b ∈ L(x) such that
f (x; b, b, ..., b, a) 6= a and remove a from consideration – that is for any e1 , e2 , ..., ek ∈
L(x) if f (x; e1 , e2 , ..., ek ) = a then we would set f (x; e1 , e2 , . . . , ek ) = c.
This change to set f (x; e1 , ..., ek ) = c could break the homomorphism property of f (for
k = 3 if (y; a01 , a02 , a03 ) exists with xy ∈ A(G), ei a0i ∈ A(H) and cf (y; a01 , a02 , a03 ) ∈
/ A(H)).
If so, we update the values of f on these neighbors of x. See Figure 4.

28

e3
e2
e1

a03
a02
a01

b03
b02
b01

change
f (...)

c

a4

b4

a

a2

b2

f (x; e1 , e2 , e3 ) = a
f (y; a01 , a02 , a03 ) = a2
f (z; b01 , b02 , b03 ) = b2

f (x; e1 , e2 , e3 ) = c
f (y; a01 , a02 , a03 ) = a4
f (z; b01 , b02 , b03 ) = b4

H

H

b

a1

b1

b

a1

b1

x

y

z

f (x; b, b, a) = c
f (y; a1 , a1 , a2 ) = a4
f (z; b1 , b1 , b2 ) = b4

H

G

Figure 4: The solid lines are arcs, dotted lines are missing arcs, and no line means either could
be true. In the first column, initially f (x; e1 , e2 , e3 ) = a but we set f (x; e1 , e2 , e3 ) = c
where c = f (x; b, b, a). In the second column, initially f (y; a01 , a02 , a03 ) = a3 but we change
it to f (y; a01 , a02 , a03 ) = a4 where a4 = f (y; a1 , a1 , a2 ). The change in the first column
is so we can remove a from L(x); the change in the second column is to preserve the
homomorphism property (this change is only needed if there is a missing arc from c to
a neighbor a2 of a).

7. DFS of updates to f . We begin by changing f values from a to something else (c) on x,
and this forces some changes for f on y’s that are neighbors of x, which in turn forces
some changes for f on neighbors of y. This results in a DFS through G × H k . We can
imagine a subgraph Gf of G × H k where the vertices are the columns in Figure 4 (for
k = 3) and there is a connection between (y; a1 , a1 , a2 ) and (z; b1 , b1 , b2 ) if a change to
f occurs on the DFS.
8. Cycles in DFS and weak k-nu property. The DFS of updates to f should be careful of
difficulties such as cycles.
An almost-cycle is a cycle in the DFS of updates from some vertex (x; b, b, .., b, a) to
itself where the only change in the vertex is the coordinate of the a (see Figure 6).
DFS moves along such cycles and update f .
Since f is a weak k-nu, update to f starting at (x; b, b, .., b, a) would be consistent with
the changes starting at (x; b, b, ...., b, a, b, ..., b), a at ith coordinate.
9. At each step in the DFS, one of the coordinates (e.g., a2 in the second column of
Figure 4) is forced due to a missing arc (the dotted lines in the figures). The remaining
coordinates (e.g., a1 in the second column of Figure 4) are more free, and these are
chosen to ensure that the DFS of updates to f always moves in the direction of a

29

shortest almost-cycle (Figure 6). Different choices for the ”more free” coordinates
result in different paths through Gf because they use different values for updating f .
10. The goal is that the DFS can complete, and we have fixed any places the homomorphism property for f was broken. If we can fix all the problems, then f would still be
a homomorphism after the procedure is done. Then we remove a from L(x). Further,
for the proof of correctness we need to make sure that if we had a correct homomorphism g in mind, then after removing a from L(x) we could change g to remain a
homomorphism with respect to the lists L and set g(x) to something other than a.
Outline We have given most of the main ideas that are part of the algorithm and proofs.
We give definitions to setup the algorithm in Section 5.2, precisely define the algorithm in
Section 5.3, and give the correctness proof in Section 5.5. We encourage the reader to begin
by reading Section 5.3 and consult back to Section 5.2 as needed. We also encourage the
reader to look forward to Section 5.5 to keep in mind the main structure of the proofs.

5.2 Definitions
This section contains definitions that are used in the algorithms in Section 5.3 and the proofs
in Section 5.5.
An oriented walk (path) is obtained from a walk (path) by orienting each of its edges. The
net-length of a walk W , is the number of forward arcs minus the number of backward arcs
following W from the beginning to the end. An oriented cycle is obtained from a cycle by
orienting each of its edges. We say two oriented walks X, Y are congruent if they follow the
same patterns of forward and backward arcs.
Given digraphs G and H, let G × H k be a digraph on the vertices {(y; a1 , a2 , . . . , ak )|y ∈
V (G), ai ∈ V (H), 1 ≤ i ≤ k} with the arcs (y; a1 , a2 , ..., ak )(y 0 ; b1 , b2 , ..., bk ) where yy 0 is an
arc of G and each ai bi , 1 ≤ i ≤ k, is an arc of H. By convention, we shall further restrict the
use of the symbol G×H k to the digraph induced on the vertices {(y; a1 , a2 , . . . , ak )|y ∈ V (G),
ai ∈ L(y), 1 ≤ i ≤ k} where L(y) is the set of vertices in H that are being considered as
images of a homomorphism from G to H.
Definition 5.1 (Homomorphism consistent with Lists) Let G and H be digraphs. For
each x ∈ V (G), let L(x) ⊆ V (H). Let k > 1 be a constant integer.
A function f : G × H k → H is a homomorphism consistent with L if the following hold.
• List property : for every x ∈ V (G) and every a1 , a2 , . . . , ak ∈ L(x), f (x; a1 , a2 , . . . , ak ) ∈
L(x)
• Adjacency property: for every x, y ∈ V (G) and every a1 , ..., ak ∈ L(x), b1 , ..., bk ∈ L(y),
if xy is an arc of G and ai bi is an arc of H for each 1 ≤ i ≤ k then f (x; a1 , ..., ak )f (y; b1 , ..., bk )
is an arc of H.

30

In addition if f has the following property then we say f has the weak nu property.
• for every x ∈ V (G), {a, b} ⊆ L(x), we have f (x; a, b, b, ..., b) = f (x; b, a, b, ..., b) = ... =
f (x; b, b, b, ...a).
We note that this definition is tailored to our purposes and in particular differs from the
standard definition of weak k-nu as follows.
(a) f is based on two digraphs G and H rather than just H (we think of this as starting
with a traditional weak k-nu on H and then allowing it to vary somewhat for each
x ∈ G),
(b) We do not require that f (y; d, d, d, ..., d) = d (this is not required in our algorithm, and
in fact is more convenient to leave out).
Notation For simplicity let (bk , a) = (b, b, . . . , b, a) be a k-tuple of all b’s but with an a in
the k th coordinate. Let (x; bk , a) be a (k + 1)-tuple of x, (k − 1) b’s and a in the (k + 1)th
coordinate.
Digraph of Updates to f

Let Gf be a digraph where V (Gf ) = V (G × H k ) and with arcs :

A(Gf ) = {(y; ak1 , a2 )(y 0 ; bk1 , b2 ) | yy 0 ∈ A(G), a1 b1 , a2 b2 ∈ A(H), f (y; ak1 , a2 )b2 6∈ A(H)} ∪
{(y; ak1 , a2 )(y 0 ; bk1 , b2 ) | y 0 y ∈ A(G), b1 a1 , b2 a2 ∈ A(H), b2 f (y; ak1 , a2 ) 6∈ A(H)}.
When (y; ak1 , a2 )(y 0 ; bk1 , b2 ) is an arc of Gf then we say (y; ak1 , a2 ) avoids (y 0 ; bk1 , b2 ) in coordinate k, or simply say the avoidance appears in the k th coordinate. In Figure 4, (z; b1 , b1 , b2 )
is an out-neighbor of (y; b1 , b1 , b2 ) in Gf with avoidance in the third coordinate.
Note that a directed path in Gf would be an oriented path in G × H k . Let B be a walk in
H starting at some vertex a ∈ V (H). We say a directed path W in Gf (with avoidance in
coordinate k) follows B if B is a walk in H induced by (k + 1)th coordinates of the vertices
in W (see Figure 5).
We say directed path W in Gf follows walk X in G when X is the walk induced by the
first coordinates of the vertices in W .
For a fixed vertex x ∈ V (G) and fixed vertex b ∈ V (H), let Gx,b be a digraph of vertices
a0 ∈ L(x) where f (x; bk , a0 ) 6= a0 . The arcs of Gx,b are of form a0 a00 where there exists a
directed path in Gf from w0 = (x; bk , a0 ) to w00 = (x; bk , a00 ).
Definition 5.2 Let w = (x; bk , a) and w1 = (x; bk , a0 ) with f (w) 6= a and f (w1 ) 6= a0 . We
say directed path W from w to w1 in Gf is quasi-cycle when vertex (x; dk , d1 ) is in W then
d = b. If a0 = a then we say W is an almost-cycle.

31

c

a4

b4

c4

a

a2

b2

c2

b

a1

b1

c1

b

a1

b1

c1

x

y

z

u

f (x; b, b, a) = c
f (y; a1 , a1 , a2 ) = a4
f (z; b1 , b1 , b2 ) = b4
f (u; c1 , c1 , c2 ) = c4
A path from (x; b, b, a) to (u; c1 , c1 , c2 )

Figure 5: An illustration of the graph Gf , with each column representing a vertex in Gf . Solid
lines are arcs, dotted lines are missing arc, and no line means either could be true.
(x; b, b, a) is connected to (y; a1 , a1 , a2 ) with avoidance at coordinate 3, which in turn is
connected to (z; b1 , b1 , b2 ) with avoidance at coordinates 3, etc. The figure depicts a path
P in Gf – where the avoidance began on the 3rd coordinate, proceeding by the walk
a, a2 , b2 , c2 in H.

f (x; b, b, a) = c
f (y; b1 , b1 , b2 ) = b4

W :

f (z; c1 , c1 , c2 ) = c4
f (w; d1 , d1 , d2 ) = d4

f (v; i1 , i1 , i2 ) = i4
f (u; `1 , `1 , `2 ) = `4

c

b4

c4

d4

i4

`4

c

a

b2

c2

d2

i2

`2

a

b

b1

c1

d1

i1

`1

b

b

b1

c1

d1

i1

`1

b

x

y

z

w

u

x

(x; b, b, a), (y; b1 , b1 , b2 ), (z; c1 , c1 , c2 ), (w; d1 , d2 , d3 ),

v
(v; i1 , i1 , i2 ),

(u; `1 , `1 , `2 ), (x; b, b, a)

Figure 6: An almost-cycle in Gf . Each column is a vertex in Gf , and dotted lines are missing
arcs.

32

Consider the digraph Gx,b . Let S = Gx,b (a) be a strong component of Gx,b containing a.
We say S is a sink component if there is no arc from an element in S to any other vertex
in Gx,b outside S. We also say S is trivial if it has only one element.
Let w = (x; bk , a) where Gx,b (a) is a sink component in Gx,b . Let Grf (w) (r for restricted)
be the induced sub-digraph of Gf (w) containing vertices w0 = (y; ak1 , a2 ) reachable from w
such that (b, a1 ) ∈ L(x, y).

5.3 Main Procedure
In this subsection we present the main algorithm. The main algorithm is Algorithm 6.
Subroutines that are used by the main algorithm are Algorithms 7, 8, and a known result
discussed in Section 5.4. Algorithm 7 (PreProcessing) simply updates the lists L of vertices
in G based on local edge constraints, and also updates the pair lists of vertices in G (pair
consistency); standard textbook CSP algorithms for the homomorphism problem would repeatedly invoke the PreProcessing routine, and then make a decision (often greedy, or trying
all possible choices that remain).
Algorithm 6 The main algorithm for solving the digraph homomorphism problem.
1: function DigraphHom(G, H, φ)
. G and H digraphs, φ a weak k-nu on H
2:
for all x ∈ G, let L(x) = V (H)
3:
for all x ∈ G and a1 , ..., ak ∈ V (H), let f (x; a1 , ..., ak ) = φ(a1 , ..., ak )
4:
PreProcessing(G, H, L)
5:
while ∃x ∈ V (G), a, b ∈ L(x), a 6= b s.t. f (x; bk , a) 6= a & Gx,b (a) is a sink do
6:
RemoveNotMinority((x; bk , a))
7:
Remove a from L(x)
8:
PreProcessing(G, H, L)
9:
Note: now, for all x ∈ V (G) and a, b ∈ L(x) we know f (x; bk , a) = a
10:
RemoveMinority(G, H, L, f )
11:
if RemoveMinority produces a homomorphism then return true
Algorithm 8 (RemoveNotMinority function) is the key subroutine of the main algorithm.
It starts with w = (x; bk , a) where f (w) = c 6= a and then it starts modifying f by setting
f (x; e1 , e2 , . . . , ek ) = f (w) for every k-tuple e1 , e2 , . . . , ek ∈ L(x) with f (x; e1 , e2 , . . . , ek ) = a.
Now in order to have a homomorphism from G × H k to H consistent with L it performs a
depth first search (in Grf (w) ) to modify f as necessary. After the execution of Algorithm 8
we remove a from L(x) in Algorithm 6. We construct Gf once and then construct Gx,b and
then consider a sink component of Gx,b , to identify the vertex w = (x; bk , a).
After the main loop in Algorithm 6, we end up with a so-called Maltsev or minority instance of the problem – in which we have a homomorphism f consistent with L such that
for every y ∈ V (G) and every c, d ∈ L(y) we have f (y; ck , d) = d. We argue in the next
subsection that such instances can be solved by using the known algorithm of [BD06] (see

33

the remark at the end of Subsection 5.4). The Maltsev/minority instances can also be solved
in a manner similar to our arguments for RemoveNotMinority (see Section 5.7) .
Algorithm 7 Update lists of x, y based on edge constraints and pair constraint
1: function PreProcessing(G, H, L)
2:
Input: digraphs G, H, lists L(x) ⊆ V (H) for each x
3:
ArcConsistency(G, H, L);
4:
PairConsistency(G, H, L)
function ArcConsistency(G, H, L)
update=True
while update do
if ∃xy(yx) ∈ A(G), a ∈ L(x) s.t. @b ∈ L(y) with ab(ba) ∈ A(H) then
remove a from L(x) and set update=True.
else update=False.
11:
if there is an empty list then return no homomprphism
5:
6:
7:
8:
9:
10:

12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

function PairConsistency(G, H, L)
for every (x, y) ∈ V (G) × V (G) set L(x, y) = {(a, b)|a ∈ L(x), y ∈ L(y)}.
for all xy ∈ A(G), a ∈ L(x), b ∈ L(y) do
if ab 6∈ A(H) then remove (a, b) from L(x, y).
update=True
while update do
if ∃x, y, z s.t. @c ∈ L(z) s.t. (a, c) ∈ L(x, z)&(c, b) ∈ L(z, y) then
remove (a, b) from L(x, y) and set update=True.
else update=False.
if there is an empty list then return no homomorphism

An overview of Algorithm 8 : Algorithm 8 starts with vertex x ∈ V (G) and two
vertices a, b ∈ L(x) such that Gx,b (a) is a sink component. The Algorithm 8 has a depth
first search function so called NM-DFS that modifies f . The advantage of taking such a, b
is that we only need to modify f in Grf (w) where w = (x; bk , a) and this allows us to direct
the NM-DFS along the almost-cycles in Grf (w).
The crucial observation is that we construct Grf (w) once with the initial values. Then we
change f (x; e1 , e2 , . . . , ek ) from a to f (x; bk , a). Now updating f is translated into taking
different directed paths in Grf (w) starting at vertex w. All the step taken by the NM-DFS
along the paths in Grf (w) are guided based on the current values of f .
Suppose at the current step of the NM-DFS we are at vertex w0 = (y; ak1 , a2 ). Suppose we
have changed the image of some (y; a01 , a02 , . . . , a0k ) from a2 to f (w0 ). Note that if this is not

34

the case then there is no need to continue from w0 and it would mean retreat from w0 .
Now we look at each neighbor of y, say z. Then in the list of z we look for an out-neighbor
(in-neighbor) of a2 , say b2 , for which the f value of w1 = (z; b01 , b02 , . . . , b0k ) should be changed
to an out-neighbor of f (w0 ) because the f value of some vertex (y; a01 , . . . , a0k ) was changed
from a2 to f (w0 ). There are two possibilities :
In the first case the f value of w1 is b2 and it should be changed from b2 to an out-neighbor
of f (w0 ) because f (w0 )b2 6∈ A(H) (b2 f (w0 ) 6∈ A(H)).
In the second case, the f value of w1 has already been changed to some vertex d ∈ L(z) at
some earlier step and now this value should be changed to an out-neighbor of f (w0 ) because
f (w0 )b2 , f (w0 )d 6∈ A(H) (b2 f (w0 ), df (w0 ) 6∈ A(H)).
Therefore we find a neighbor of w0 , say w00 = (z; bk1 , b2 ) in Grf (w) to change f (w1 ) to f (w00 )
and take arc w0 w00 ∈ Gfr (w) in the NM-DFS.
Since w0 ∈ Grf (w), we have (b, a1 ) ∈ L(x, y) and hence there exists a vertex b1 ∈ L(z) such
that a1 b1 ∈ A(H), and (b, b1 ) ∈ L(x, z) (because of the PreProcessing).
Definition 5.3 Let w0 = (y; ak1 , a2 ) be a vertex in Grf (w). We say an arc w0 w00 ∈ Grf (w) is
nice if it lies on a shortest directed path (cycle) Q (starting at w) in Grf (w) and if there is a
choice we may assume Q is a shortest almost-cycle, i.e. Q ends at (x; bk , a).
To simplify the proof of the correctness we may direct the NM-DFS to take an w0 w00 when
f (w0 )f (w00 ) is an arc of H. If no such arc w0 w00 exists, then we place w0 w00 into queue Q
(pause) and go back to take different branches. Later NM-DFS comes back and will resume
from w0 w00 . We will explain how such situation occurs. Once NM-DFS retreat at some point
it considers vertex w1 where w1 = (y; dk1 , d2 ) and then take arc w1 w2 where w2 = (z; ek1 , e2 )
and f (w0 ) = d2 and f (w00 ) = e2 . If there is no branch to take NM-DFS removes an arc w0 w00
from Q and it resumes from there.
For simplicity one can assume that DFS does not put anything into queue Q.
In Algorithm 8 the vertices (x; bk |i←a ) and (x; bk |`←a ) of Gf are considered as the same
vertex.
The NM-DFS is used for two purposes.
1. To modify f such that at the end f is a homomorphism consistent with lists L and for
any k-tuple e1 , e2 , . . . , ek , f (x; e1 , e2 , . . . , ek ) 6= a.
2. To show that if there exists a homomorphism g : G → H consistent with lists L with
g(x) = a then there exists a homomorphism h : G → H consistent with lists L and
with h(x) 6= a. We use NM-DFS as a guide to define h.
We will show that in order to repair f we only need to do the NM-DFS inside Grf (w). Let
Gaf (w) (’a’ for almost-cycle) be the sub-digraph of Grf (w) containing vertices w0 such that
w0 lies on an almost cycle containing w. We observe that in order to update f in Gaf (w),

35

e3
e2
e1

a03
a02
a01

b03
b02
b01

d03
d02
d01

d

f (z; b1 , b1 , b2 ) = b4
c

a4

b4

d4
change

a

a2

b2

d2

b

a1

b1

d1

b

a1

b1

d1

x

y

z

u

f (y; a01 , a02 , a03 ) = a2
f (z; b01 , b02 , b03 ) = b2

f (y; a01 , a02 , a03 ) = a4
f (z; b01 , b02 , b03 ) = b4

f (z; b01 , b02 , b03 ) = d

Figure 7: Line 10 from Algorithm 8 where f (z; b01 , b02 , b03 ) changed from b2 to d at an earlier step
in the NM-DFS, and so now is changed to b4 along with other points that map to b2 .

we need to go through the cycles in Gaf (w) and hence we direct NM-DFS to go through the
shortest almost-cycles one by one.
Let Gof (w) (’o’ is for other) be the sub-digraph of Grf (w) containing those vertices that
do not lie on an almost-cycle. Therefore in order to update f in Gof (w) we need to direct
NM-DFS to go through the directed paths in Gof (w) and hence we direct NM-DFS to go
through the shortest paths one by one.
In what follows we argue how things could go wrong if H does not have the weak nu
property.
For contrary suppose w1 = (x; bk , a) with f (w1 ) = c and w2 = (x; a, b, b, . . . , b) with
f (w2 ) = d. If d = a then according to the NM-DFS we try to remove a from L(x) if we start
with w1 while we do need to keep a in L(x) because we later use the Maltsev algorithm. It
might not be the case that d 6= a but as one can see (shown in the proof of Lemma 3.3 (4))
some non-minority pairs becomes minority pairs. In other words, during NM-DFS for some
w3 = (x; bk , e) with f (w3 ) 6= e we may set f (w3 ) to e.
So we need to have f (w1 ) = f (w2 ), the weak nu property, to start. We do mention at
the end of the proof of Lemma 5.7 that it does not matter to start the NM-DFS from w1 or w2 .
In Conclusion : NM-DFS modifies f and the reason we use almost-cycles is because of
(2) above and the need for weak nu property is because modifying f starting at any of the
(x; bk , a), (x; b, b, . . . , b, a, b, . . . , b) (ith coordinate) would keep the property of f .

36

Algorithm 8 Remove a from L(x), updating f so it remains a homomorphism of G × H k
to H consistent with L.
1: function RemoveNotMinority(w = (x; bk , a))
2:
Input: x, a, b such that f (w) = c 6= a and Gx,b (a) is a sink
3:
if ∃ w1 = (x; a01 , a02 , . . . , a0k ) with f (w1 ) = a then
4:
for all w1 = (x; a01 , a02 , . . . , a0k ) with f (w1 ) = a do set f (w1 ) = c
5:
NM-DFS(w = (x; bk , a))
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

function NM-DFS(w0 = (y; ak1 , a2 ))
if w0 already visited then return
do
Let w00 = (z; bk1 , b2 ) 6= (x; bk , a) s.t w0 w00 is a nice arc of Grf (w)
. a2 b2 ∈ A(H), f (w0 )b2 6∈ A(H) & f (y; ...) changed from a2 to f (w0 )
if f (w0 )f (w00 ) 6∈ A(H) then add w0 w00 into queue Q and return
Let d ∈ L(z) s.t. f (z; ...) was changed from b2 to d.
. d = b2 if no change
0
if f (w )d 6∈ A(H) then
for all w2 = (z; ...) if f (w2 ) was changed from b2 to d or f (w2 ) = b2 do
set f (w2 ) = f (w00 )
NM-DFS(w00 )
while ∃ a neighbor of w0 that has non been considered
. It considers the neighbors of w0 and for each b2 only one NM-DFS(w00 ) call
while Q is not empty do remove w0 w00 from Q
if w0 w00 is an arc of Grf (w) then NM-DFS(w00 )

37

5.4 Minority Algorithm (RemoveMinority)
In this section we show that once the minority case has been reached in our main algorithm,
we can reduce to an already solved setting for homomorphism testing – namely that of the
Maltsev case. We note that this section is independent of the rest of the algorithm.
Note that at this point for every a, b ∈ L(x) we have f (x; bk |i←a ) = a and in particular
when a = b we have f (x; a, a, . . . , a) = a (idempotent property). This is because when a is
in L(x) then it means the RemoveNotMinority procedure did not consider a and in fact did
not change the value of f (x; ...) from a to something else. Note that for the argument below
we just need the idempotent property for those vertices that are in L(x), x ∈ V (G).
A ternary polymorphism h0 is called Maltsev if for all a 6= b, h0 (a, b, b) = h0 (b, b, a) = a.
Note that the value of h0 (b, a, b) is unspecified by this definition.
Let G and H be as input to Algorithm 6, and suppose line 9 of the algorithm has been
reached. We define a homomorphism h : G × H 3 → H consistent with the lists L by setting
h(x; a, b, c) = f (x; a, b, b, . . . , b, c) for a, b, c ∈ L(x). Note that because f has the minority
property for all x ∈ G, a, b ∈ L(x), h is a Maltsev homomorphism consistent with the lists
L.
Note that for every a, b ∈ L(x) we have f (x; bk |k←a ) = a and in particular if a = b
we have f (x; a, a, . . . , a) = a (idempotent property). Since a is in L(x), this means the
RemoveNotMinority procedure did not considered a and in fact did not change the value
of f (x; ...) from a to something else. Note that for the argument below we just need the
idempotent property for those vertices that are in L(x), x ∈ V (G).
Let G0 be the structure obtained from G by making each arc a different binary relation.
In other words, G0 has vertices V (G) and |E(G)| binary relations Re , e ∈ E(G), where
Re = {xy} if e is the arc e = xy.
Let H 0 be the structure where V (H 0 ) is the disjoint union of L(x), x ∈ V (G), and there
are also |E(G)| binary relations Se , e ∈ E(G), where Se is the set of all ordered pairs ab with
ab ∈ E(H), a ∈ L(x), b ∈ L(y), where e = xy. Note that |V (H 0 )| ≥ |V (G0 )| if each L(x) is
non-empty. This may seem unusual for the homomorphism setting, but is certainly allowed.
Now note that there is an L-homomorphism of G to H (i.e., a list homomorphism consistent
with lists L) if and only if there is a homomorphism of G0 to H 0 . Homomorphisms of such
structures are mappings f : V (G0 ) → V (H 0 ) such that xy ∈ Re implies f (x)f (y) ∈ Se for all
e ∈ E(G).
Finally, note that the structure H 0 has a Maltsev polymorphism h0 of the ordinary kind.
Indeed, let hx be our Maltsev polymorphisms defined on L(x) by setting hx (a, b, c) =
h(x; a, b, c). We let h0 (a, b, c) = h(x; a, b, c) if a, b, c are from the same L(x), and for a, b, c
not from the same L(x) define h0 (a, b, c) = a unless a = b, in which case define it as
h0 (a, b, c) = c. The definition ensures that h is Maltsev. To check it is a polymorphism, note
that aa0 , bb0 , cc0 ∈ Se is only possible if a, b, c ∈ L(x), a0 , b0 , c0 ∈ L(y), where e = xy. For
those, we have the polymorphism property by assumption.
Now we have a structure with a Maltsev polymorphism, so the Bulatov-Dalmau [BD06]

38

algorithm applies and solves the homomorphism problem. Note that Corollary 4.2 of the
Bulatov-Dalmau paper explicitly mentions that it is polynomial in both the sizes of G and
H.
Therefore we have the following theorem.
Theorem 5.4 Suppose h : G × H k → H is a minority homomorphism consistent with lists
L on G. Then the existence of an L-homomorphism of G to H can be decided in polynomial
time.
Remark : We have communicated with the authors of [BD06] and they confirmed that
indeed we can apply their algorithm as explained above. We note that it is also possible
to give a direct algorithm for the minority case that is similar to how we handle the “not
minority” case.

5.5 Proofs
5.5.1 PreProcessing and List Update
We first show that the standard properties of consistency checking remain true in our setting
– namely, that if the PreProcessing algorithms succeed then f remains a homomorphism
consistent with the lists L if it was before the pre-processing.
Lemma 5.5 If f is a homomorphism of G × H k → H consistent with L then f is a homomorphism consistent with L after running the pre-processing.
Proof: We need to show that if a1 , a2 , . . . , ak are in L(y) after the pre-processing then
f (y; a1 , a2 , . . . , ak ) ∈ L(y) after the pre-processing. By definition vertex a is in L(y) after
the pre-processing because for every oriented path Y (of some length m ) in G from y to a
fixed vertex z ∈ V (G) there is a vertex a0 ∈ L(z) and there exists a walk B in H from a to
a0 and congruent with Y that lies in L(Y ). L(Y ) denote the vertices that are in the list of
the vertices of Y .
Let a01 , a02 , a03 , . . . , a0k ∈ L(z). Let Ai , 1 ≤ i ≤ k be a walk from ai to a0i in L(Y ) and
0
congruent to Y . Let Ai = ai , ai1 , a2i , . . . , am
i , ai and let Y = y, y1 , y2 , . . . , ym , z.
Since f is a homomorphism consistent with L before the pre-processing, f (y; a1 , a2 , . . . , ak ),
m
m
0
0
0
f (y1 ; a11 , a12 , . . . , a1k ), . . . , f (yi ; ai1 , ai2 , . . . , aik ), . . . , f (ym ; am
1 , a2 , . . . , ak ), f (z; a1 , a2 , . . . , ak ) is
a walk congruent with Y . This would imply that there is a walk from f (y; a1 , a2 , . . . , ak ) to
f (z; a01 , a02 , . . . , a0k ) congruent with Y in L(Y ) and hence f (y; a1 , a2 , . . . , ak ) ∈ L(y).

By a similar argument as in the proof of Lemma 5.5 we have the following lemma.
Lemma 5.6 If f is a homomorphism of G×H k → H, consistent with L and a1 , a2 , . . . , ak ∈
L(x), b1 , b2 , . . . , bk ∈ L(y), and (ai , bi ) ∈ L(x, y), 1 ≤ i ≤ k, after pre-processing then
(f (x; a1 , a2 , . . . , ak ), f (y; b1 , b2 , . . . , bk )) ∈ L(x, y) after the pre-processing.

39

5.5.2 RemoveNotMinority Correctness Proof
The main argument is proving that after each step of the RemoveNotMinority function
f still is a homomorphism consistent with the lists and has weak nu property (Lemma
5.7). Moreover, after removing a vertex from the list of a vertex of G there still exists a
homomorphism from G to H if there was one before removing that vertex from the list
(Lemma 5.8).
Lemma 5.7 If f is a homomorphism of G × H k → H, consistent with L with weak nu
property before RemoveNotMinority(w = (x; bk , a)) then the modified f remains a homomrphism consistent with L with weak nu property afterwards. Moreover for every k-tuple
a1 , a2 , . . . , ak ∈ L(x), f (x; a1 , . . . , ak ) 6= a.
Lemma 5.8 If there is a homomorphism g : G → H with g(x) = a then there is a homomorphism from G to H after removing a from L(x) according to RemoveNotMinority((x; bk , a)).
5.5.3 Proof of Lemma 5.7
In order to show that f still is a homomorphism consistent with L with weak nu property,
we need to address items 1,2,3,4 below.
1. The weak nu property is preserved.
2. The RemoveNotMinority function stops in O(|A(G)||H|k+1 ).
3. The adjacency property is preserved: for an arbitrary arc yz ∈ A(G) (zy ∈ A(G))
and for every a01 , a02 , . . . , a0k ∈ L(y) and b01 , b02 , . . . , b0k ∈ L(z) where a0i b0i ∈ A(H) (b0i a0i ∈
A(H)), 1 ≤ i ≤ k, we have f (y; a01 , a02 , . . . , a0k )f (z; b01 , b02 , . . . , b0k ) ∈ A(H)
(f (z; b01 , b02 , . . . , b0k )f (y; a01 , a02 , . . . , a0k ) ∈ A(H)).
4. We argue that we only need to fix the problems caused by changing f (x; ...) from a
to c in Grf (x; bk , a). We show that if f (x; bk , a) = c 6= a and f (x; e1 , e2 , . . . , ek ) = a
then f (x; e1 , e2 , . . . , ek ) is changed to c (in the simple case) or to some other fixed
element (which will be used in the next lemma) not equal to a after the execution of
RemoveNotMinority((x; bk , a)).
Proof of 1 : Since we change the value f (y; a01 , a02 , ..., a0k ) from a2 to f (y; ak1 , a2 ) for every
k-tuple a01 , a02 , . . . , a0k ∈ L(y), we change f (y; b1 , b1 , . . . , b1 , b2 ) = f (y; b1 , b1 , . . . , b2 , b1 ) = · · · =
f (y; b2 , b1 , . . . , b1 ) to the same value. Therefore f still has the weak k-nu property.
Proof of 2 : Observe that during the NM-DFS the value of f (y; a01 , a02 , . . . , a0k ), y 6= x may
change several times. This is because after changing f (y; a01 , a02 , . . . , a0k ) from a2 to some ak+1
there might be the case that there is a path A0 from a to ak+1 in H and some directed path
Q in Grf (w) to some vertex (y; ck1 , ak+1 ).

40

However, the value of f (θ), θ = (x; e1 , e2 , . . . , ek ) is changed once or the value of f (θ) may
change a number of times while going through a circuit (explained in Case 2 in the proof of
(4)) but each time to a new value.
Note that the NM-DFS algorithm may end up traversing all the vertices in Gf but each
vertex at most once. There are at most |G||H k | vertices in Gf . The running time of the
NM-DFS is O(|A(G)|H|2k+1 ). Note that the size of Gf is at most |A(G)|H|k+1 and at each
step of the NM-DFS we may change a value of some k-tuple in a list of a vertex of G and
there are |H|k of them.
Proof of 3 : Let ak+1 = f (y; a01 , a02 , . . . , a0k ) and bk+1 = f (z; b01 , b02 , . . . , b0k ). If ak+1 bk+1 is an
arc of H then we are done. Otherwise without loss of generality we consider the following
two cases.
(a) The value of f (y; a01 , a02 , . . . , a0k ) changed from a2 to ak+1 for the last time and the value
of f (z; b01 , b02 , . . . , b0k ) was not changed.
(b) The value of f (y; a01 , a02 , . . . , a0k ) changed from a2 to ak+1 for the last time and the value
of f (z; b01 , b02 , . . . , b0k ) was changed after changing the value of f (y; a01 , a02 , . . . , a0k ).
Note that ak+1 is the last value of f (y; a01 , a02 , . . . , a0k ) and bk+1 is the last value of f (x; b01 , b02 , . . . , b0k ).
Observe that the original value of f (y; a01 , a02 , . . . , a0k ) may not be a2 and it could have been
changed several times before finally being set to ak+1 . For the sake of simplicity, we may
assume that a2 is the original value of f (y; a01 , a02 , . . . , a0k ). Otherwise we may consider an arc
(y; a001 , a002 , . . . , a00k )(z; b001 , b002 , . . . , b00k ) with f (y; a001 , a002 , . . . , a00k ) = a2 instead of arc
(y; a01 , a02 , . . . , a0k )(z; b01 , b02 , . . . , b0k ) and then we could look back at the earlier step of the NMDFS and apply the same argument as below.
According to the RemoveNotMinority function, there is a directed path W from w =
(x; bk , a) to w0 = (y; ak1 , a2 ) in Grf (w). Here w0 is the vertex visited by NM-DFS function.
Let b2 be the original value of f (z; b01 , b02 , . . . , b0k ). We note that a2 b2 is an arc of H because
initially f is a homomorphism consistent with L.
Proof of (a) : Here bk+1 = b2 . Now since ak+1 b2 6∈ A(H), there exists w00 = (y; bk1 , b2 )
such that w0 w00 ∈ A(Grf (w)). The NM-DFS considers all such arcs w0 w00 ∈ Gfr (w) and by
Claim 5.9 we may assume that w0 w00 is a nice arc (f (w00 ) is an out-neighbor of ak+1 ). Therefore NM-DFS should have changed the value of f (z; b01 , b02 , . . . b0k ) from b2 to f (w00 ) which is
a contradiction.
Proof of (b): Case 1. Suppose ak+1 b2 6∈ A(H).
Observe that there exists w00 = (z; bk1 , b2 ) such that w0 w00 ∈ A(Grf (w)). Recall that the
assumption is : f (z; b01 , b02 , . . . , b0k ) changed after f (y; a01 , a02 , . . . , a0k ). There are two scenarios
:
1. w00 is visited right after w0 .

41

a03
a02
a01

−
−
−

b03
b02
b01

d03
d02
d01

a5
a4 = d

b4
e4

c
a2

f (x; b, b, a) = c
f (y; a1 , a1 , a2 ) = a4
f (z; c1 , c1 , b2 ) = b4
f (u; e1 , e1 , e2 ) = e4
f (y; d1 , d1 , a2 ) = a5
change

b2
e2

a
a1
b

d1
a1

b

x

d1

y

b1
c1

f (y; a01 , a02 , a03 ) = a2
f (z; b01 , b02 , b03 ) = b2
f (u; d01 , d02 , d03 ) = e2

f (y; a01 , a02 , a03 ) = a4
f (z; b01 , b02 , b03 ) = b4
f (u; d01 , d02 , d03 ) = e4

f (y, a01 , a02 , a03 ) = a4

f (y, a01 , a02 , a03 ) = a5

e1

b1
c1

e1

z

u
z

0

Figure 8: Keep in mind for the proof of 3 (b) in the proof of Lemma 5.7
2. We reach w00 by following a directed path R in Grf (w) starting at w0 .
Suppose (1) occurs. This would mean we should have changed the value of f (z; b01 , b02 , . . . , b0k )
as we discussed in the proof of (a). Note that again here we appeal to Claim 5.9 for the nice
arc w0 w00 . We also note that in this case the value of f (z; b01 , b02 , . . . , b0k ) is going to change
for the first time in the NM-DFS.
Suppose (2) occurs. This means the value of f (z; b01 , b02 , . . . , b0k ) did change (from b2 ) following
R. Let Z : y, y1 , . . . , yr , z be the oriented path in G that R follows.
By adding arc yz (zy) we get an oriented cycle in G. Since Z(yz) is a cycle it may be that
the last vertex of R is w00 = (z; bk1 , b2 ) and hence by following the modification of f along the
path R we set f (z; b01 , b02 , . . . , b0k ) = bk+1 . Since f is a homomorphism for the vertices in R (by
Claim 5.9), f (w0 )f (w00 ) is an arc and hence ak+1 bk+1 must be an arc of H, a contradiction.
In other words, the modification is consistent.
Now let us assume that the last vertex of R is not w00 .
Let α = (z; ck1 , b2 ) be the last vertex of R (α 6= w00 ). Now in this case according to line 10
of the NM-DFS (see y as z and z as y in the algorithm, see also Figure 8) we have d = ak+1
and dbk+1 is not an arc of H.
First suppose a2 bk+1 6∈ A(H) (in Figure 8, a2 b4 6∈ A(H)) then according to NM-DFS
we should have considered the vertex α0 = (y; dk1 , a2 ) where αα0 is a nice arc and hence
we should have changed the value of f (y; a01 , a02 , . . . , a0k ) from ak+1 to an in-neighbor of
bk+1 , a contradiction (by Claim 5.9 we consider the nice arc αα0 and f (α)f (α0 ) is an arc
of H). Second suppose a2 bk+1 is an arc of H (in Figure 8, a2 b4 ∈ A(H)). In this case
there exists a nice arc w0 w2 in Grf where w0 = (y; ak1 , a2 ) and w2 = (z; bk1 , bk+1 ) (in Figure

42

8, (y; a1 , a1 , a2 )(z; b1 , b1 , b4 ) ∈ A(Grf (w)). Therefore we should have changed the value of
f (z; b01 , b02 , . . . , b0k ) from bk+1 , a contradiction that was the last value (here again by Claim
5.9 f (w0 )f (w2 ) is an arc of H).
Remark : Note that w00 could be one of the visited vertices but the important thing is
we change the value of some k-tuple in z to f (w00 ) (if necessary) and once the NM-DFS is
called with vertex w00 it returns. What is important to notice is that in the NM-DFS we
consider the arcs of Grf (w) (we visit each arc) and makes the update to f accordingly. Once
the NM-DFS traces back and come back to w00 it starts taking a different branch and it
continues updating f from w00 (the visited) accordingly.
Case 2. ak+1 b2 ∈ A(H). In this case the NM-DFS does not proceed to some vertex w00 = (z; bk1 , b2 ) where a2 b2 ∈ A(H). However, NM-DFS proceeds to some vertex
w1 = (z; dk1 , , b2 ) with f (w1 ) = bk+1 because f (z; b01 , b02 , ..., b0k ) has changed to bk+1 . Now
since ak+1 b2 ∈ A(H) and ak+1 bk+1 6∈ A(H), NM-DFS should have continued considering
some vertex w2 = (y; ek1 , ak+2 ) which is a neighbor of w1 in Grf (w) and should have changed
f (y; a01 , a02 , ..., a0k ) from ak+1 to an in-neighbor of bk+1 . But this is a contradiction because
ak+1 was the last value of f (y; a01 , a02 , ..., a0k ).
Claim 5.9 Suppose the NM-DFS is at vertex w0 = (y; ak1 , a2 ). Let b2 be an out-neighbor
(in-neighbor) of a2 . Then at some stage of the NM-DFS there exists a vertex w00 = (z; bk1 , b2 )
such that w0 w00 is a nice arc and f (w0 )f (w00 ) ∈ A(H).
Proof: Set w00 = (z; bk1 , b2 ) such that w0 w00 ∈ Grf (w). Initially f (w0 )f (w00 ) (f (w00 )f (w0 ) ∈
A(H)) is an arc of H because f is a homomorphism consistent with the lists. For contradiction suppose f (w0 )f (w00 ) is not an arc of H. This means either f (w0 ) did change and f (w00 )
did not change immediately or f (w00 ) did change and f (w0 ) did not change.
Case 1. f (w0 ) did change first. This means there is a directed path Q1 from w to some
α = (y; ck1 , c2 ) in Grf (w) and the NM-DFS went along Q1 and did change f (w0 ) from c2 to
f (α). But according to the rules of NM-DFS we don’t take arc w0 w00 and we will wait till we
take arc λ = (y; ck1 , c2 )(z; dk1 , d2 ) such that f (w00 ) = d2 is an is an out-neighbor (in-neighbor)
of c2 . Note that f (w0 ) is changed to f (α) according to the NM-DFS. If f (α)d2 6∈ A(H) then
the arc λ should have been taken by NM-DFS.
Case 2. f (w00 ) did change and f (w0 ) did not change immediately. This means there is a
path Q1 from w to β = (z; dk1 , d2 ) where f (w00 ) changed from d2 to f (β). Now the NM-DFS
moved along some path Q2 starting at β and reach w0 . At this point if f (w0 )d2 6∈ A(H) and
f (w0 )f (β) 6∈ A(H) then according to line 13 of the Algorithm 8 the NM-DFS should change
f (w00 ) from f (β) to an out-neighbor of f (w0 ). So this case can not happen.


43

c

d1

d2

a

c

a

c

d1

d2

a

b

b

b

b

b

b

b

b

b

b

x

x

x

x

x

Figure 9: Circuit of length 2
Proof of 4 : The NM-DFS starts from vertex w where w = (x; bk , a). The changes to f are
forced in the list of vertices y where w0 = (y; ak1 , a2 ) ∈ Gf , i.e. f (y; . . . ) should be changed
from a2 to something else. This means there exists a path from w to w0 . Since we only need
to change the image of f in y from a2 , we are free to choose a1 ∈ L(y) and hence we may
assume that NM-DFS is performed in Grf (w). We also note that since a is a sink component
of Gx,b (a), any shortest almost-cycle lies entirely in Grf (w).
Now in the remaining we analyze the behavior of NM-DFS depending on the final value of
f (x; e1 , e2 , . . . , ek ) that is initially a. The final value is used in Lemma 5.8. Let C = Gx,b (a)
be sink strong component of Gx,b containing a.
We say vertex a ∈ C is a source if there is no path from a to c in C where f (x; bk , a) = c.
We say the sink component C is invertible if it does not have a source.
Suppose C does not have a source. Now according to the definition of invertible, there is
a path in C starting at a that goes through the vertices c, d1 , d2 , . . . , dt−1 , dt in this order.
Thus there exist corresponding vertices α = (x; bk , a), β = (x; bk , c), λj = (x; bk , dj ), 1 ≤ j ≤ t
and there exists a quasi-cycle Q in Grf from α to λt that goes through β, λ1 , λ2 , . . . , λt in
this order and f (α) = c, f (β) = d1 , f (λ1 ) = d2 , . . . , f (λt−1 ) = dt , f (λt ) = a. If t = 1
then d1 = a and λt+1 = α. We say Q is a circuit in Grf (α) (see Figure 9). Let Q(t) be an
almost-cycle obtained from concatenating Q and a directed path Q0 from λt to α0 = (x; bk , a)
in Grf (α). Note that path Q0 exists because C is a strong component of Gx,b . Note that here
for simplicity we may assume that the last vertex of the circuit is λt with f (λt ) = a. It could
be the case the di plays the role of a.
Observe that if there exists an arc from a to a00 in C then this means we do need to modify
f (x; β10 , β20 , . . . , βk0 ) from a00 to f (w1 ) where w1 = (x; bk , a00 ).
Now we consider two cases depending on whether C is invertible or not.

44

Case 1. C is not invertible.
Note that since a is a source and C is a sink component, there is no arc from a to some
c where f (w) = c, and hence there is no path in Grf (α) from α to (x; bk , c). This means we
do not end up changing a value of f (x; α10 , α20 , . . . , αk0 ) after changing it from a to c and then
changing it from c to something else.
Case 2. C is invertible. We need to show that if there is an arc from a to c in C then
function NM-DFS would handle this situation and it fixes the value of f (x; b01 , b02 , . . . , b0k )
from a to some element not a. The main purpose of this case would be finding that fixed
element.
Since C is invertible, there exists a directed path P in C from a to dt which goes
through the vertices a, c, d1 , d2 , . . . , dt−1 (at this order). Consequently this means there
exist vertices : α, β = (x; bk , c), λi = (x; bk , di ), 1 ≤ i ≤ t and there exists a path Q :
α, . . . , β, . . . , λ1 , . . . , λ2 , . . . , λt in Grf (α) where f (α) = c, f (β) = d1 , f (λ1 ) = d2 , . . . ,
f (λt−1 ) = dt , f (λt ) = a.
Now according to the definition of a circuit there exists an almost-cycle Q(t). in Grf (α).
According to the function NM-DFS at some point the NM-DFS starts with α and it moves
along an almost-cycle Q(t) and changes the value of f (λt ) from a to c. As it moves along
Q(t), once it reaches β the NM-DFS algorithm changes the value of f (λt ) from c to d1 and
also changes the value of f (α) from c to d1 , once NM-DFS reaches λ1 on Q(t), it changes the
value of f (β) from d1 to d2 and the value of f (α) from d1 to d2 . It continues, until it reaches
λt−1 , and at this point the value of all f (λi ), 1 ≤ i ≤ t is set to dt as well as the value of
f (α), f (β). Now there does not exists a path from α in Grf (α) to some vertex α0 = (x; bk , dt )
with f (α0 ) = dt . This is because of the following observations :
Observation: There is no directed path R in Grf (ψ), ψ = (x; ck , d) with f (ψ) 6= d to some
vertex φ = (x; c0k , d0 ) with f (φ) = d0 . To see that suppose such a path R exists. Consider the
last arc of R say e = (y; dk1 , d2 )(x; c0k , d0 ) where we may assume yx ∈ A(G). Since e is an arc
of Grf (ψ) we have f (y; dk1 , d2 )d0 6∈ A(H) and f (y; dk1 , d2 )f (x; c0k , d0 ) ∈ A(H), a contradiction.
Observation: Since C is a source we do not need to consider circuits in other components
of Gx,b .
Now α becomes a source, since f (α) = dt . NM-DFS has changed f (x; a1 , a2 , . . . , ak ) from
a to dt and it does not change it anymore. NM-DFS starts the usual procedure as if there
is no circuit Q. Moreover since C is a sink component there is no path from C to another
invertible component.
Note that the NM-DFS goes through the vertices of λ1 , λ2 , . . . , λt−1 and it continues the
usual NM-DFS from λt−1 . In the next step it returns back and it starts from λt−2 and so on.

45

Closing remark We run the function NM-DFS(x; bk , a). Once we change the value of
f (x; a1 , a2 , . . . , ak ) from a to c (or dt when C is invertible) then potentially we need to modify
the value for f (y; b1 , b2 , . . . , bk ) from an out-neighbor of a, say a0 in L(y) to an out-neighbor
of c. As far as the modifying f is concern it would yield the same result if we start from
(x; a, b, . . . , b).

5.5.4 Proof of Lemma 5.8
Suppose g is a homomorphism from G to H with g(x) = a. We may assume that there exists
a (x; e1 , e2 , . . . , ak ) with f (x; e1 , e2 , . . . , ak ) = a. Otherwise in some previous step we have
shown that there exists a homomorphism that does not map x to a if there exists one that
maps x to a. Let w = (x; bk , a) and let c = f (w).
Let G0f be the induced sub-digraph of Grf (w) with vertices w0 = (y; ak1 , a2 ) such that :
• f (w1 ) = a2 , for w1 = (y; a01 , a02 , . . . , a0k ) where f (w1 ) was initially g(y),
• a2 is the value before the last time f (w1 ) is going be to change to f (y; ak1 , a2 ).
. the value of f (w1 ) is going to be changed to f (y; ak1 , a2 ) according to NM-DFS for
the last time.
Let G0 be the induced sub-digraph of G with the vertices y ∈ V (G) where (y; ak1 , a2 ) ∈ G0f .
Observation : Consider a path W in G0f from (x; bk , a) to (x; bk , a). Now let X be a
walk in G from x to x corresponding to W , i.e. W follows X. We note that by replacing a2
with f (y; ak1 , a2 ) for every y ∈ X where (y; ak1 , a2 ) is on path W , we get a mapping from X
to H and under this mapping the beginning of X and end of X are mapped to same vertex
c. Moreover this mapping is a homomorphism from X to H because f is a homomorphism
consistent with L.
Let Y be a path in G0 from x to y. Corresponding to Y there is a path in G0f from
(x; bk , a) to some (y; ak1 , a2 ). Now define h(y) = f (y; ak1 , a2 ). For every y ∈ V (G) \ V (G0 )
set h(y) = g ∗ (y) (here g ∗ (y) is the last value of f (y; a01 , a02 , . . . , a0k ) where initially was g(y)).
Note that h(x) = c.
We need to show that h is a homomorphism from G to H. Let zz 0 (z 0 z) be an arc of G
where z ∈ V (G0 ). We only need to consider the case z ∈ V (G0 ). By definition there exists a
path W from w to some w0 = (z; bk1 , b2 ) ∈ G0f with f (w0 ) = bk+1 . Note that if there does not
exists such path W , then by definition z 6∈ V (G0 ).
Since zz 0 is an arc of G and g is a homomorphism from G to H, g(z)g(z 0 ) ∈ A(H).
Moreover, according to the NM-DFS b2 d2 ∈ A(H) (here d2 is the value in which some vertex
w10 = (z 0 ; d01 , d02 , . . . , d0k ) is going to change from g(z 0 ) after visiting the arc zz 0 by the NMDFS). Note that d2 is in L(z 0 ). This is because either d2 = g(z 0 ) and hence it passes the

46

PreProcessing test or d2 = f (z 0 ; ...) and hence by Lemma 5.5 d2 ∈ L(z 0 ). Now if bk+1 d2 is an
arc of H then we are done. Otherwise according to the NM-DFS there exist vertex d1 ∈ L(z 0 )
such that b1 d1 , b2 d2 ∈ A(H), and w0 w00 , w00 = (z 0 ; dk1 , d2 ), is an arc of G0f . Since this is the
last time NM-DFS change the value of some f (w10 ) from g(z), we have w00 ∈ G0f and hence
z 0 ∈ V (G0 ). This would imply that h(z 0 ) = f (w00 ). Since f is a homomorphism consistent
with L, we have f (w0 )f (w00 ) ∈ A(H) and because we set h(z) = f (w0 ) and h(z 0 ) = f (w00 ) we
have h(z)h(z 0 ) ∈ A(H). Note that in the special case when z 0 = x we have g(z 0 ) = a and
by the Observation above we have h(z 0 ) = c. Therefore h is a homomorphism from G to H
with h(x) = c.
The argument is the same when the strong component Gx,b (a) does not have a source. 

5.6 Proof of Theorem 1.1 (second approach)
By Lemma 5.8 we preserve the existence of a homomorphism from G to H after Algorithm
8. By Lemma 5.7 f is still a homomorphsim from G × H k → H consistent with the lists L
of G after Algorithm 8. Now we can apply Theorem 5.4.
According to the proof of Lemma 5.7 (2) the running time of Algorithm 4 is O(|A(G)||H|2k+1 ).
The running time of Algorithm 2.2 is O(|G||A(G)||H|k+1 ). In the Algorithm 6 we call
Algorithm 8 at most |G||H| times. We observe that the running time of PreProcessing
O(|G|3 |H|2 ). However, one single run but at each step of while loop in the Algorithm 6
we only remove one element of H therefore the overall time for PreProcessing would be
O(|G|3 |H|2 ). Therefore the running time of Algorithm 6 is O(|G|3 |H|2k+2 ).

5.7 Additional Algorithms and Proofs (New Minority Algorithm)
This section collects additional statements and proofs mainly related to new Minority algorithm. We develops a direct algorithm to handle the minority case in our main algorithm.
Of course, it would be easier to appeal to Bulatov-Dalmau Maltsev result as explained in
Subsection 5.4.
A direct proof for Theorem 5.4 Let M 3 be the digraph of triple (y, c, d), x ∈ G, c, d ∈
L(y). There is an arc from (y, c, d) to (y 0 , c0 , d0 ) where yy 0 ∈ A(G), cc0 , dd0 ∈ A(H) and
cd0 6∈ A(H) or y 0 y ∈ A(G) and c0 c, d0 d ∈ A(H), d0 c 6∈ A(H). Note that M 3 is a graph but we
view M 3 as digraph and when we talk about a path in M 3 we mean an oriented path that
reflect the direction of the edge xy when (y, c, d)(y 0 , c0 , d0 ) is an arc of M 3 . Let Gx (a, b) be
the strong component of M 3 containing (x, a, b) such that for each vertex (y, c, d) ∈ Gx (a, b),
(a, c) ∈ L(x, y) and (b, d) ∈ L(x, y). We say a strong component Gx (a, b) of M 3 is invertible
if both (x, a, b) and (x, b, a) are in Gx (a, b).
Again the idea is similar to the one handling the RemoveNotMinority case. At each step we
consider a vertex x of G and two vertices a, b ∈ L(x) and try to eliminate one of the a, b from
L(x). To decide whether remove a or b we construct an instance of the problem say (G0 , H, L0 )

47

and solve this instance recursively. Based on the existence of a L0 -list homomorphism from
G0 to H we decide to remove a or b. Depending on Gx (a, b) being invertible or not two
different instances for the sub-problem are constructed. At the end we have singleton lists
and if there is a homomorphism from G to H with the singleton lists then success otherwise
we report there is no homomorphism from G to H. We denote the underline graph of digraph
G by U N (G). If Gx (a, b) is invertible we construct a new instance G0 , H, L0 and to construct
the lists L0 we use the Maltsev property.
Lemma 5.10 Let X be an oriented path in G and let B, C, D be three walks in L(X) all
congruent to X where B is from a to c and C is from b to c and D is from b to D. Then
there exists a walk E from a to d in L(X) that is congruent with X.
Proof: By following B, C, D on the vertices in X and applying the definition of polymorphism h, we conclude that E exists.

Lemma 5.10 implies the following corollary.
Corollary 5.11 If (a, c) ∈ L(x, y) and (b, c), (b, d) ∈ L(x, y) then (a, d) ∈ L(x, y).
Lemma 5.12 The Algorithm 9 runs in O(|E(G)||H|k+1 ). Moreover, if there is a homomorphism g from G to H with g(x) ∈ {a, b} then there is a homomorphism from G to H after
removing a or b from L(x) according to Maltsev-(G, H, L, h).
Proof: We spend |G||H|k+1 to define h. For every pair a, b ∈ L(x) the algorithm construct an instance of the problem which takes O(|A(G)||A(H)|3 ). The algorithm is recursive
and the depth of the recursion in |G||H|. We conclude that the running time of function
Maltsev(G, H, L) is O(|G||A(G)||H|4 ) (replaces |A(H)| by |H|2 ) (see the analysis of Algorithm 4). Therefore the running time of the Algorithm 2.2 is O(|A(G)||H|k+1 ).
First consider the case that Gx (a, b) is not invertible. The Algorithm 9 is recursive
but at each recursive call the size of the input decreases by at least one. This is because we
do not add b into L0 (x) and hence we have an instance (G0 , L0 , H) of the problem in which at
least one vertex has a smaller size list. We also note that once we make a decision to remove
a vertex from a list the decision is not changed. Therefore the overall procedure in this
case is polynomial (assuming in each call Gx (a, b) is not invertible). According to Maltsev(G, H, L, h) if G0 does not admit a homomorphism to H then there is no homomorphism
from G to H that maps x to a since G0 is a sub-digraph of G.
No suppose b is removed according to Maltsev-(G, H, L, h) and there exists a homomorphism g from G to H with g(x) = b. Let ψ be the homomorphism from G0 to H. Note that
ψ(x) = a.
Define G1 be a sub-digraph of G0 consists of the vertices y such that (y, ψ(y), g(y)) is
reachable from (x, a, b) in Gx (a, b).

48

Algorithm 9 RemoveMinority – Using Matlsev Operations
1: function RemoveMinority(G, H, L)
2:
Input: x, a, b such that f (x; bk |i←a ) = a
3:
Define Maltsev consistent homomorphism h : G × H 3 → H where
h(x; a, b, c) = f (x; a, b, b, . . . , b, c) for a, b, c ∈ L(x).
4:
while ∃ x ∈ V (G) with |L(x)| ≥ 2 do
5:
Matlsev(G, H, L )
6:
if ∃ a list homomorphism from G to H then return True
7:
else return False.

8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

21:
22:
23:
24:
25:
26:
27:

function Maltsev(G, H, L)
Let a, b ∈ L(x) be two distinct vertices. Construct Gx (a, b).
if Gx (a, b) is not invertible then
Set L0 (x) = a and L0 (y) = ∅ for every x 6= y.
Set G00 = ∅, and let G0 be an induced sub-digraph of G constructed as below.
for all y ∈ G s.t. ∃ a path from (x, a, b) to (y, c, d) in Gx (a, b) do
add y to G0 and c to L0 (y),
let yy 0 an arc of G0 when (y, c, d)(y 0 , c0 , d0 ) ∈ Gx (a, b).
if Gx (a, b) is invertible then
Set L0 (x) = a and L0 (y) = ∅ for every x 6= y.
Let G00 be the set of vertices y ∈ V (G) where (y, c, d, e) lies on an oriented path
P from (x, a, b, b) to (x, b, b, a) in U N (G × H 3 ) s.t. no intermediate vertex in P
is (x, a0 , b0 , c0 ) for a0 , b0 , c0 ∈ L(x)
for all arc (y, c, d, e)(y 0 , c0 , d0 , e0 ) ∈ P do
add h(y, c, d, e) to L0 (y), h(y 0 , c0 , d0 , e0 ) to L0 (y 0 ), and add arc yy 0 (y 0 y) to G00
Let G0 be the induced sub-digraph of G with vertices
y ∈ G \ G00 and arcs yy 0 where (y, c, d)(y 0 , c0 , d0 ) ∈ Gx (a, b) and add c into L0 (y)
when (y, c, d) ∈ Gx (a, b)
if Matlsev(G0 ∪ G00 , H, L0 ) then
remove b from L(x)
else remove a from L(x).

49

Now for every vertex y ∈ G1 set φ(x) = ψ(x) and for every y ∈ G \ G1 set φ(y) = g(y).
Now let zz 0 be an arc of G. If none of the z, z 0 ∈ G1 then clearly since g is a homomorphism, φ(z)φ(z 0 ) ∈ A(H). If both z, z 0 ∈ G1 then again since ψ is a homomorphism, we have
φ(z)φ(z 0 ) ∈ A(H). Suppose z ∈ G1 and z 0 6∈ G1 . Since z ∈ G1 there exists a path in Gx (a, b)
from (x, a, b) to (z, ψ(z), g(z)). Now if ψ(z)g(z 0 ) is an arc then we are done. Otherwise
(z 0 , c, g(z 0 )) ∈ Gx (a, b) where c ∈ L(z 0 ) and ψ(z)c ∈ A(H) (note that since ψ(z) is in L(z) it
must have an out-neighbor in L(z 0 )). This would mean z 0 ∈ G1 , a contradiction. Note that
when z 0 = x and z ∈ G1 then because (ψ(z), a) ∈ L(z, x) we have ψ(z)a ∈ A(H).
Second consider the case that Gx (a, b) is invertible. Again as we argued in the
previous case the algorithm is recursive but at each recursive call the size of the input
decreases and once a decision made (removing a or b ) it won’t change.
Observe that if there exists a homomorphism g that maps x to a then for every closed
walk X from x to x, the image of g(X) is a closed walk from a to a in H. Since there is
a walk BB from b to b in L(X) congruent and since (a, b) ∈ L(x, x), there is a walk BA
in L(X) congruent to X. Now by Lemma 5.10 there is a walk AB from a to b in L(X)
and congruent with X. These would imply that there exists a path P in U (G × H 3 ) from
(x, b, b, a) to (x, a, b, b). Now according to the definition of G00 for every walk BB in L(X)
from b to b congruent with X we keep a walk AA in L0 (X) congruent with X and is obtained
by adding h(y, c1 , c2 , c3 ) into L0 (y) where (y, c1 , c2 , c3 ) is in P .
This would mean that in the list of L0 (X), corresponding to ψ(X) (ψ is a homomorphism
from G to H where ψ(x) = a if there exists one) we have a path from a to a in L0 (X).
Therefore if there exists no homomorphism from G0 ∪ G00 → H that maps x to a then there
is no homomorphism from G to H that maps x to a.
Now suppose b is removed according to Maltsev-(G, H, L, h) and there exists a homomorphism g from G to H with g(x) = b. Let ψ1 be the homomorphism from G0 to H and ψ2 be
a homomorphism from G00 to H. Note that ψ1 (x) = ψ2 (x) = a. First we show that there is
no arc e (forward or backward) from a vertex y in G0 to a vertex in G00 . If this is the case
then there is a walk Q from x to y and there is a walk Q0 from y to x. Now since yz is an
arc then Qee−1 Q0 is a closed walk from x to x and hence we should have added z into G00 .
Note that G00 consists of all the induced oriented cycles including x and also all the paths
reaching out of vertices of these cycles except x.
Define G1 be a sub-digraph of G0 consists of vertices y such that (y, ψ1 (y), g(y)) is reachable
from (x, a, b) in Gx (a, b).
Now for every vertex y ∈ V (G1 ) set φ1 (y) = ψ(y) and for every y ∈ V (G) \ V (G1 )
set φ1 (y) = g(y). Define G2 be a sub-digraph of G00 consisting of vertices y such that
(y, ψ2 (y), g(y)) is reachable from (x, a, b) in Gx (a, b).
Now for every vertex y ∈ V (G2 ) set φ2 (y) = ψ2 (y) and for every y ∈ V (G) \ V (G2 )
set φ2 (y) = g(y). And finally let φ(y) = φ1 (y) when y ∈ V (G0 ) and φ(y) = φ2 (y) when
y ∈ V (G00 ). Now let zz 0 be an arc of G. We need to verify that φ(z)φ(z 0 ) is an arc of H.
If none of the z, z 0 ∈ V (G1 ∪ G2 ) then clearly since g is a homomorphism, φ(z)φ(z 0 ) ∈

50

A(H). If both z, z 0 ∈ V (Gi ) (i = 1, 2) then again since ψi is a homomorphism, we have
φ(z)φ(z 0 ) ∈ A(H). Suppose z ∈ V (G2 ) and z 0 6∈ V (G2 ). Since z ∈ V (G2 ), there exists a
closed walk ZZ 0 that contains z where Z is a path from x to z and Z 0 is a walk from z
to x. Note that ψ2 (ZZ 0 ) is a walk from a to a in L(ZZ 0 ) and g(ZZ 0 ) is a walk from b to
b in L(ZZ 0 ) and since (b, a) ∈ L(x × x) there exists a walk BA in L(ZZ 0 ) congruent with
ZZ 0 . These would imply that corresponding to ZZ 0 there exists a path P from (x, b, b, a) to
(x, a, b, b) containing vertex (z, ψ2 (z), d, g(z)). Now since g(z) ∈ L(z) there exists a vertex
c ∈ L(z 0 ) such that g(z)c ∈ A(H) and there exists e0 ∈ L(z 0 ) such that dd0 ∈ A(H).
Now we add the two arcs (z, ψ2 (z), d, g(z))(z 0 , c, d0 , g(z 0 )), (z 0 , c, d0 , g(z 0 ))(z, ψ2 (z), d, g(z))
into P and hence we obtain a path P 0 from (x, b, b, a) to (x, a, b, b) that goes through vertex
(z 0 , c, d0 , g(z 0 )) and hence z 0 ∈ G00 . Now since φ2 (z)g(z 0 ) 6∈ A(H), by definition z 0 ∈ V (G2 ), a
contradiction.
As we argued before one can show that φ1 is also a homomorphism from G to H. Therefore
φ is a homomorphism from G to H with φ(x) = a.

Acknowledgements : We would like to thank Ross Willard and Pavol Hell for so many
helpful discussions and their useful comment as well as their enormous support. We would
like to thank Vı́ctor Dalmau for so many useful questions and helpful comments. We would
also like to thank Geoffrey Exoo, László Egri, for their comments.

References
[ABISV09]

E. Allender, M. Bauland, N. Immerman, H. Schnoor, and H. Vollmer. The complexity of satisfiability problems: refining schaefer’s theorem. Journal of Computer and
System Sciences, 75(4): 245–254 (2009).

[BHM88]

J. Bang-Jensen, P. Hell, G. MacGillivray. The complexity of colouring by semicomplete
digraphs. SIAM J. Discrete Math., 1 : 281–298 (1988).

[BH90]

J. Bang-Jensen, P. Hell. The effect of two cyles on the complexity of colourings by
directed graphs. Discrete Appl. Math., 26 : 1–23 (1990).

[BKN09]

L. Barto, Marcin Kozik, and Todd Niven. The CSP Dichotomy Holds for Digraphs
with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen
and Hell). SIAM J. Comput, 38(5) : 1782–1802 (2009).

[B02b]

A.A. Bulatov. A dichotomy constraint on a three-element set. In Proceedings of STOC
649–658 (2002).

[B05]

A.Bulatov. H-Coloring dichotomy revisited. Theoret. Comp. Sci., 349 (1) : 31-39
(2005).

[B06]

A. Bulatov. A dichotomy theorem for constraints on a three-element set. Journal of
the ACM, 53(1): 66–120 (2006).

51

[B11]

A.Bulatov. Complexity of conservative constraint satisfaction problems. Journal of
ACM Trans. Comput. Logic, 12(4) : 24–66 (2011).

[BD06]

A. Bulatov and V. Dalmau. A Simple Algorithm for Mal’tsev Constraints. SIAM J.
Comput., 36(1): 16–27 (2006).

[BJK05]

A.A. Bulatov, P. Jeavons, and A. Krokhin. Classifying the complexity of constraints
using finite algebras. SIAM journal on computing, 34(3): 720-742 (2005).

[JB17]

J. Bulin. Private communication.

[CCL13]

J.Y. Cai, X. Chen, P. Lu. Graph Homomorphisms with Complex Values: A Dichotomy
Theorem. SIAM J. Comput., 42(3): 924–1029 (2013).

[CVK10]

C. Carvalho, V.Dalmau, and A.A. Krokhin. CSP duality and trees of bounded pathwidth. Theor. Comput. Sci., 411(34–36): 3188–3208 (2010).

[CKS01]

N. Creignou, S. Khanna, and M. Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Math. and Applications,
vol. 7 (2001).

[CL14]

P. Csikvári and Z. Lin. Graph homomorphisms between trees. Elec. J. Combin., 21 :
4–9 (2014).

[D92]

R. Dechter. Containt networks. Encyclopedia of Artificial Intelligence 276–285 (1992).

[D00]

V. Dalmau. A new tractable class of constraint satisfaction problems. In Proceedings
6th International Symposium on Artificial Intelligence and Mathematics, 2000.

[DF03]

V. Dalmau, D. Ford. Generalized satisfiability with k occurrences per variable: A
study through delta-matroid parity. In Proceedings of MFCS 2003, Lecture Notes in
Computer Science, 2747 : 358–367 (2003).

[EHLR14]

L.Egri, P.Hell, B.Larose, and A.Rafiey. Space complexity of List H-coloring : a dichotomy. In Proceedings of SODA, (2014).

[F01]

T. Feder. Homomorphisms to oriented cycles and k-partite satisfiability. SIAM J.
Discrete Math., 14 : 471–480 (2001).

[F06]

T. Feder A dichotomy theorem on fixed points of several nonexpansive mappings.
SIAM J. Discrete Math., 20 : 291–301 (2006).

[FHH99]

T.Feder, P.Hell, J.Huang. Bi-arc graphs and the complexity of list homomorphisms.
J. Graph Theory, 42 : 61–80 (1999).

[FH98]

T. Feder, P. Hell. List homomorphisms to reflexive graphs. J. Comb. Theory Ser., B
72 : 236–250 (1998).

[FHH99]

T. Feder, P. Hell, J. Huang. List homomorphisms and circular arc graphs. Combinatorica, 19 : 487–505 (1999).

52

[FHH03]

T. Feder, P. Hell, J. Huang. Bi-arc graphs and the complexity of list homomorphisms.
J. Graph Theory, 42 : 61–80 (2003).

[FHH07]

T. Feder, P. Hell, J. Huang. List homomorphisms of graphs with bounded degrees.
Discrete Math., 307 : 386–392 (2007).

[FMS04]

T. Feder, F. Madelaine, I.A. Stewart. Dichotomies for classes of homomorphism problems involving unary functions. Theoret. Comput. Sci., 314 : 1–43 (2004).

[FV93]

T.Feder and M.Vardi. Monotone monadic SNP and constraint satisfaction. In Proceedings of STOC, 612–622 (1993).

[FV98]

T. Feder and M.Y. Vardi. The computational structure of monotone monadic SNP
constraint satisfaction: A study through Datalog and group theory. SIAM Journal on
Computing, 28(1): 57–104 (1998).

[HN90]

P. Hell and J. Nešetřil. On the complexity of H-colouring. J. Combin. Theory B, 48 :
92–110 (1990).

[HN04]

P. Hell, J. Nešetřil. Graphs and Homomorphisms, Oxford University Press, 2004.

[HN08]

P.Hell, J.Nešetřil. Colouring, Constraint Satisfaction, and Complexity. Computer Science Review , 2(3): 143–163 (2008).

[HR11]

P.Hell and A.Rafiey. The Dichotomy of List Homomorphisms for Digraphs. In Proceedings of SODA 1703–1713 (2011).

[HR12]

P. Hell and A. Rafiey. The Dichotomy of Minimum Cost Homomorphism Problems
for Digraphs. SIAM J. Discrete Math., 26(4): 1597–1608 (2012).

[KSDR96]

L.G. Kroon, A. Sen, H. Deng, A. Roy. The optimal cost chromatic partition problem for trees and interval graphs. In Graph-Theoretic Concepts in Computer Science
(Cadenabbia, 1996), Lecture Notes in Computer Science, 1197 : 279–292 (1997).

[K92]

V. Kumar. Algorithms for constraint-satisfaction problems. AI Magazine, 13 :32–44
(1992).

[J98]

P. Jeavons. On the Algebraic Structure of Combinatorial Problems. Theor. Comput.
Sci., 200(1-2): 185-204 (1998).

[L75]

R. Ladner. On the Structure of Polynomial Time Reducibility. Journal of the ACM
(JACM), 22(1): 155–171 (1975).

[LZ03]

B. Larose, L. Zádori. The complexity of the extendibility problem for finite posets.
SIAM J. Discrete Math., 17 : 114–121 (2003).

[MM08]

M. Maroti, and R. McKenzie. Existence theorems for weakly symmetric operations.
Algebra Universalis, 59 : 463–489 (2008).

53

[S78]

T.J. Schaefer. The complexity of satisfiability problems. In Proceedings of STOC, 216–
226 (1978).

[S10]

M.Sigge. A new proof of the H-coloring dichotomy. SIAM J. Discrete Math., 23 (4) :
2204–2210 (2010).

[V00]

M.Y. Vardi. Constraint satisfaction and database theory: a tutorial. Proceedings of
the 19th Symposium on Principles of Database Systems (PODS), 76–85 (2000).

54

