Algorithms and Complexity Group, TU Wien, Vienna,
<EMAIL_ADDRESS>Ganian acknowledges
support by the Austrian Science Fund (FWF, projects Y1329 and P31336).
Algorithms and Complexity Group, TU Wien, Vienna,
<EMAIL_ADDRESS>Hamm acknowledges
support by the Austrian Science Fund (FWF, projects P31336 and Y1329).
Algorithms and Complexity Group, TU Wien, Vienna,
<EMAIL_ADDRESS>Korchemna acknowledges support by
the Austrian Science Fund (FWF, project Y1329). Faculty of Matematics and
Information Science, Warsaw University of Technology, Warsaw, Poland, and
Faculty of Mathematics, Informatics and Mechanics, University of Warsaw,
<EMAIL_ADDRESS>Okrasa acknowledges
support by the European Research Council, grant agreement No 714704. Parts of
this work were performed while visiting TU Wien, Vienna, Austria. Algorithms
and Complexity Group, TU Wien, Vienna<EMAIL_ADDRESS>Simonov acknowledges support by the Austrian Science Fund (FWF, project
P31336). Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa,
Kirill Simonov [300]Theory of computation Parameterized complexity and exact
algorithms

# The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-
Width

Robert Ganian  Thekla Hamm  Viktoriia Korchemna  Karolina Okrasa  Kirill
Simonov

###### Abstract

The generic homomorphism problem, which asks whether an input graph $G$ admits
a homomorphism into a fixed target graph $H$, has been widely studied in the
literature. In this article, we provide a fine-grained complexity
classification of the running time of the homomorphism problem with respect to
the clique-width of $G$ (denoted ${\operatorname{cw}}$) for virtually all
choices of $H$ under the Strong Exponential Time Hypothesis. In particular, we
identify a property of $H$ called the signature number $s(H)$ and show that
for each $H$, the homomorphism problem can be solved in time
$\mathcal{O^{*}}(s(H)^{{\operatorname{cw}}})$. Crucially, we then show that
this algorithm can be used to obtain essentially tight upper bounds.
Specifically, we provide a reduction that yields matching lower bounds for
each $H$ that is either a projective core or a graph admitting a factorization
with additional properties—allowing us to cover all possible target graphs
under long-standing conjectures.

###### keywords:

homomorphism, clique-width, fine-grained complexity

##  1 Introduction

A _homomorphism_ from a graph $G$ to a graph $H$ is an edge-preserving mapping
from the vertices of $G$ to the vertices of $H$. Homomorphisms are fundamental
constructs which have been studied from a wide variety of perspectives [13, 3,
2]. Our focus here will be on the class of problems which ask whether an input
$n$-vertex graph $G$ admits a homomorphism to a fixed target graph $H$. This
“meta-problem”—which we simply call Hom($H$)—captures, among others, the
classical $c$-Coloring problems when $H$ is set to the complete graph on $c$
vertices. Famously, Hell and Nešetřil [15] proved that Hom($H$) is polynomial-
time solvable if $H$ is bipartite or has a loop, and NP-complete otherwise.
While the aforementioned result provides a basic classification of the
complexity of Hom($H$), it does not say much in terms of how quickly one can
actually solve these problems. Indeed, the usual assumption that P $\neq$ NP
is not sufficient to obtain tight bounds for the running times of algorithms.
While upper bounds can be straightforwardly obtained by designing a suitable
algorithm, the corresponding lower bounds usually rely on the Exponential Time
Hypothesis (ETH) or the Strong Exponential Time Hypothesis (SETH), which
allows for even tighter bounds [19, 18, 23]. It is not difficult to design a
brute-force algorithm for the homomorphism problem that runs in time
$\mathcal{O^{*}}(|V(H)|^{n})$ for every choice of $H$, and thanks to the
breakthrough result of Cygan et al. we now know that this running time is
essentially tight under the Exponential Time Hypothesis (ETH) [6] as long as
one considers only the dependency on $n$ and $|V(H)|$. Still, it is often
possible to circumvent this lower bound and obtain significantly better
runtime guarantees. One approach to do so is to consider restrictions on the
class of targets: if $H$ is a complete graph then Hom($H$) can be solved in
time $\mathcal{O^{*}}(2^{n})$, and there are also several algorithms that
achieve running times of the form $\mathcal{O^{*}}(\alpha(H)^{n})$ where
$\alpha(H)$ is some structural parameter of $H$ [12, 30, 29]. The other is to
exploit the properties of the input graph $G$, which are commonly captured by
a suitably defined structural parameter. The most commonly used graph
parameter in this respect is _treewidth_ [28], which informally measures how
“tree-like” a graph is. When considering treewidth, it is once again not
difficult to obtain an algorithm that runs in time
$\mathcal{O^{*}}(|V(H)|^{\operatorname{tw}})$, where ${\operatorname{tw}}$ is
the treewidth of $G$; as before, it was much more difficult to show that this
is essentially optimal. The first SETH-based tight lower bound in this setting
was actually shown for special cases of the related problem of LHom($H$),
where each vertex in the graph $G$ comes with a list of admissible targets for
the homomorphism [9]; this was later lifted to a full classification [24]. A
nearly-complete SETH-based lower bound result for Hom($H$) itself was only
obtained recently by Okrasa and Rzążewski [25]; in particular, the result
covers all targets which are so-called _projective cores_. It is known that
almost all graphs are projective cores [16, 31, 25], and it is worth noting
that the authors showed that their result can be lifted to all targets under
long-standing conjectures on the properties of projective cores [22, 21].
While treewidth is the most prominent structural graph parameter, it is not
the most general111There is a hierarchy of graph parameters (see, e.g., [1,
Figure 1]), where parameter $\mathbb{A}$ is more general than parameter
$\mathbb{B}$ if there are graph classes of bounded $\mathbb{A}$ and unbounded
$\mathbb{B}$ but the opposite is not true. one that can be used to efficiently
solve Hom($H$). Indeed, standard dynamic programming techniques can be used to
obtain a $\mathcal{O^{*}}((2^{|V(H)|})^{\operatorname{cw}})$ time algorithm
for the problem, where ${\operatorname{cw}}$ stands for _clique-width_ [4]: a
well-studied graph parameter that is bounded not only on all graph classes of
bounded treewidth, but also on well-structured dense classes such as complete
graphs. But is this basic algorithm generally optimal (mirroring the situation
for treewidth [25]), or can one obtain better runtime dependencies on clique-
width?

Contribution. Our aim is to obtain a detailed understanding of the fine-
grained complexity of Hom($H$) in terms of the clique-width of $G$ and the
fixed target $H$. As a starting point for our investigation, we note that
Lampis used the SETH to obtain tight bounds for $c$-Coloring with respect to
clique-width [20]. Interestingly, already for this special case, the upper and
lower bounds differ from those of the aforementioned simple dynamic
programming algorithm: if $H$ is a complete graph, then Hom($H$) can be solved
in time $\mathcal{O^{*}}((2^{|V(H)|}-2)^{\operatorname{cw}})$ [20] and this is
tight under the SETH. However, as noted by Piecyk and Rzążewski [27], it was
not at all obvious how these bounds can be lifted to general choices of $H$.
In order to achieve our goals we need to improve upon the basic dynamic
programming idea to identify a “hopefully correct” base of the exponent for
every choice of $H$. Towards our first result, we identify a structural
property of $H$ called the _signature number_ (denoted $s(H)$) which,
intuitively, captures the number of non-trivial neighborhood classes of vertex
subsets in $H$ (the _signature set_). We then obtain a non-trivial dynamic
programming algorithm that solves Hom($H$) in time where the base of the
exponent is precisely the signature number. We note that $s(H)$ is
$2^{|V(H)|}-2$ for complete graphs $H$, and so this result also provides a
succinct and broader explanation for the running time of Lampis’ algorithm
[20].

######  Theorem 1.1.

Let $H$ be a fixed graph. Hom($H$) can be solved in time
$\mathcal{O}^{*}(s(H)^{\operatorname{cw}(G)})$ for each input graph $G$,
assuming an optimal clique-width expression of $G$ is provided as part of the
input.

With this upper bound, we proceed to the main technical contribution of this
paper: establishing a corresponding lower bound under the SETH. The main
difficulty here is that we need a reduction that is delicate on one hand,
since it needs to preserve the clique-width, but is on the other hand also
flexible enough to work for many different choices of $H$; moreover, the
reduction has to rely on the signature numbers of these graphs in some way. To
provide an intuitive description of the reduction, let us focus for now on the
case where $H$ is a projective core. On a high level, the main building block
is an _$S$ -gadget_ which, given an arbitrary set $S$ of pairs of vertices in
$H$ and two vertices $p$ and $q$ of the input graph $G$, ensures that every
homomorphism $f$ satisfies $(f(p),f(q))\in S$. After providing a generic
construction for such $S$-gadgets which is clique-width preserving and works
for every valid choice of $H$, we use these to obtain _implication gadgets_
and _or gadgets_ which restrict how a solution homomorphism can behave on a
selected set of vertices in $G$. The formalization of these gadgets is the
main technical hurdle towards the desired result; once that is done, we can
lift the idea used in the earlier reduction of Lampis [20] that established
clique-width lower bounds for $c$-Coloring by reducing from Constraint
Satisfaction (CSP) to Hom($H$). One crucial distinction in our reduction is
that we use elements of the signature set (as opposed to color sets) to
represent domain values in the CSP instance. To lift these considerations to
cases where $H$ is not a projective core, we unfortunately need to add an
extra layer of complexity. Similarly as in the previous treewidth-based lower
bound for Hom($H$) [25], one can base this step on conjectures of Larose and
Tardif [22, 21] that classify all remaining targets as certain graph products
with special properties (notably, all of the factors must be “truly
projective”). The approach used for treewidth [25] was then to essentially
repeat all steps of the proof for projective cores, with the added difficulty
that one uses the properties of products instead of dealing directly with
projective cores. While this approach could be used here as well, instead we
unify the two cases ($H$ being a projective core, and $H$ being a product) by
defining the notion of $W$-projectivity for some factor $W$ of $H$. In
particular, if $H$ is a projective core then it itself is $H$-projective,
while if $H$ is a product with truly projective factor $H_{i}$ then it is
$H_{i}$-projective. As our main result, we obtain an SETH-based lower bound
which essentially shows that for each $W$-projective graph $H$, $s(W)$ is the
optimal base of the clique-width exponent for solving $\textsc{Hom}(H)$:

######  Theorem 1.2.

If $H$ is $H_{i}$-projective for some $i\in[m]$ then there is no algorithm
solving Hom($H$) in time
$\mathcal{O}^{*}((s(H_{i})-\varepsilon)^{{\operatorname{cw}(G)}})$ for any
$\varepsilon>0$, unless the SETH fails.

By also deliberately considering prime factorizations in the algorithm which
we provide for Theorem 1.1, we can obtain an upper bound on the complexity of
Hom($H$) that matches the lower bound from Theorem 1.2. For a discussion
explicitly relating these complexity bounds in the context of the
aforementioned conjectures of Larose and Tardif, we refer to Section 6.

##  2 Preliminaries

We use standard terminology for graph theory [7]. Let $[i]$ denote the set
$\\{1,\dots,i\\}$. For a mapping $f:A\rightarrow B$ and $A^{\prime}\subseteq
A$, let $f|_{A^{\prime}}$ denote the restriction of $f$ to $A^{\prime}$. We
will use the $\mathcal{O}^{*}(\cdot)$ notation to suppress factors polynomial
in the input size.

### Homomorphisms and Cores

For two graphs $G$ and $H$, a _homomorphism_ from $G$ to $H$ is a mapping
$h:V(G)\to V(H)$, such that for every $uv\in E(G)$ we have $h(u)h(v)\in E(H)$.
If there exists a homomorphism from $G$ to $H$, we denote this fact by $G\to
H$, and if $h$ is a homomorphism from $G$ to $H$, we denote that by $h:G\to
H$. If there is no homomorphism from $G$ to $H$, we write $G\not\to H$. If
$G\to H$ and $H\to G$, we say that $G$ and $H$ are _homomorphically
equivalent_. In particular, since the composition of homomorphisms is a
homomorphism, if $G$ and $H$ are homomorphically equivalent, then for every
graph $F$ we have that $F\to G$ if and only if $F\to H$. It is straightforward
to verify that homomorphic equivalence is an equivalence relation on the class
of all graphs. On the other hand, if $G\not\to H$ and $H\not\to G$ for some
graphs $G,H$, we say that $G$ and $H$ are _incomparable_.

We note that if $H$ is a clique on $c$ vertices, then homomorphisms form $G$
to $H$ are precisely proper vertex $c$-colorings of $G$.

We say that a graph $H$ is a _core_ if every homomorphism $h:H\to H$ is an
automorphism. Equivalently, $H$ is a core if for every proper induced subgraph
$H^{\prime}$ of $H$ it holds that $H\not\to H^{\prime}$. We say that a core
$H^{\prime}$ is a _core of $H$_ if $H^{\prime}$ is an induced subgraph of $H$
and $H\to H^{\prime}$. Clearly, each core graph is a core of itself. Each
graph has a unique (up to isomorphism) core, and the core of $H$ can be
equivalently defined as the smallest (with respect to the number of vertices)
graph that is homomorphically equivalent with $H$ [16].

A graph $H$ is _ramified_ if $N(u)\not\subseteq N(v)$ for every two distinct
vertices $u,v$ of $H$. Observe that each core is ramified; otherwise one could
define $f:H\to H$ that is an identity on all vertices of $H$ but $u$ and set
$f(u)=v$. This would be a homomorphism to a proper subgraph of $H$,
contradicting the fact that $H$ is a core.

We say that a graph $H$ is _trivial_ if its core has at most two vertices.
[[15]] A graph $H$ is trivial if and only if it is either bipartite or
contains a vertex with a loop.

######  Proof 2.1.

It is straightforward to observe that there exist three trivial cores:
$K_{1}$, $K_{2}$, and $K^{*}_{1}$, where by $K_{1}^{*}$ we denote the graph
that consists of one vertex with a loop.

If $H$ contains a vertex $a$ with a loop, then $K_{1}^{*}$ is the core of $H$,
as mapping every vertex of $H$ to $v$ yields a homomorphism. If $H$ is
bipartite, then the core of $H$ is either $K_{1}$ (if $H$ has no edges) or
$K_{2}$ (since mapping the vertices of one bipartition class to one vertex of
$K_{2}$, and another bipartition class to the other, is a homomorphism).

For the other direction, assume that $H$ is a non-bipartite loopless graph.
Since it is loopless, $K_{1}^{*}$ cannot be its core. Clearly, $H$ has at
least one edge, and therefore $H\not\to K_{1}$ Moreover, $H$ contains an odd
cycle $C_{2k+1}$ as a subgraph, hence, $C_{2k+1}\to H$. If now $H\to K_{2}$,
composition of these homomorphism gives that $C_{2k+1}\to K_{2}$, which is
equivalent to stating that $C_{2k+1}$ is 2-colorable, a contradiction.

Observe that trivial cores $H$ correspond precisely to the polynomial cases of
the Hom($H$) problem. Since our aim is to focus on the NP-hard cases of the
problem, from here onward we will assume that the target graph is non-trivial.

### Signature Sets

For a vertex $v$ of a graph $H$, let $N_{H}(v)$ denote the set of neighbors of
$v$ in $H$. If the graph is clear from the context, we will omit the subscript
$H$ and write $N(v)$.

For a non-empty set $T\subseteq V(H)$ we say that $S(T)$ is the _signature set
of $T$_ if $S(T)=\bigcap_{t\in T}N(t)$. We say that a non-empty set
$S\subseteq V(H)$ is a _signature set_ , if there exists $T$ such that
$S=S(T)$. We denote by $\mathcal{S}(H)$ the set of all signature sets of $H$,
and we note that $\\{V(H),\emptyset\\}\cap\mathcal{S}(H)=\emptyset$. If $T$ is
a proper non-empty subset of $V(H)$, and $a\in T$, $b\in S(T)$, then $ab\in
E(H)$. Moreover, for non-empty subsets $A,B\subseteq V(H)$, $S(A\cup
B)=S(A)\cap S(B)$.

We note that the operation of taking a signature set is reversible on
$\mathcal{S}(H)$:

For every $A\in\mathcal{S}(H)$, $S(S(A))=A$.

######  Proof 2.2.

By the definition of signature set, $A\times S(A)\subseteq E(H)$, so
$A\subseteq S(S(A))$. For the converse direction observe that as
$A\in\mathcal{S}(H)$, there exists a non-empty subset $T$ of $V(H)$ such that
$A=S(T)$. Pick any $x\in S(S(A))$, then $E(H)\supseteq\\{x\\}\times
S(A)=\\{x\\}\times S(S(T))\supseteq\\{x\\}\times T$. Hence by definition $x\in
S(T)=A$.

Let the _signature number_ of $H$, denoted $s(H)$, be defined as
$|\mathcal{S}(H)|$. As mentioned in the introduction, the signature number
will play a crucial role in our upper and lower bounds.

Observe that, if $H$ is a target and hence non-trivial, for every nonempty
$T\subseteq V(H)$ we have that $S(T)\cap T=\emptyset$. From that it is easy to
see that $V(H)$ never belongs to $\mathcal{S}(H)$. Since, by definition,
$\emptyset\notin\mathcal{S}(H)$, we get the following bounds for $s(H)$.

Let $H$ be a graph with no loops. Then $s(H)\leqslant 2^{|V(H)|}-2$. Notice
that since $2^{|V(H)|}-2$ is the number of all proper non-empty subsets of
$V(H)$, the equality in Section 2 holds if and only if $H$ is a clique.

If $S\in\mathcal{S}(H)$, we call $T$ such that $S(T)=S$ a _witness_ of $S$.
Clearly, we can have distinct $T_{1},T_{2}$ such that $S(T_{1})=S(T_{2})$,
however, notice that in such a case there exists $T=T_{1}\cup T_{2}$ such that
$S(T)=S(T_{1})=S(T_{2})$. Hence, there exists a unique maximal (with respect
to inclusion) witness of $S$, and we denote it by $M(S)$. In fact, it is not
difficult to see that $M(S)=\\{v\in V(H)\mid S\subseteq N_{H}(v)\\}$; for
$S(M(S))=S$ to hold, it is clearly necessary that $S\subseteq N_{H}(v)$ for
all $v\in M(S)$. On the other hand, as $M(S)$ is maximal all $v$ for which
this is true are contained in $M(S)$.

In this way signature sets and their witnesses are in one-to-one
correspondence. While not necessary to obtain our algorithmic and lower bounds
for Hom($H$) parameterized by clique-width, this offers an alternative
perspective on the role of signatures in our results.

In fact, the signature number could equivalently be defined as the ‘maximal
witness number’ and signature sets could be replaced by maximal witnesses in
all our proofs: Let $\mathcal{M}(H)=\\{M(S):S\in\mathcal{S}(H)\\}$, then
$\mathcal{S}(H)=\mathcal{M}(H)$.

######  Proof 2.3.

Let $T$ be a fixed non-empty subset of $V(H)$ such that $S(T)\neq\emptyset$.
Observe that the definition and the maximality of $M(S(T))$ implies that
$S(S(T))=\bigcap_{t\in S(T)}N(t)=M(S(T))$. Since $T$ and $S(T)$ are non-empty,
we get that $\mathcal{S}(H)\supseteq\mathcal{M}(H)$. For the other direction
observe that $M(M(S(T)))=S(T)$. Assume the contrary, then there exists a
vertex $v\notin S(T)$ such that $N(v)\supset M(S(T))$. However, $T\subseteq
M(S(T))\subseteq N(v)$ meaning that $v\in S(T)$, a contradiction. Thus,
$\mathcal{S}(H)=\mathcal{M}(H)$.

We note that if $H$ is a core graph, we can also bound the minimum cardinality
of $\mathcal{S}(H)$.

Let $H$ be a core graph, $H\neq K_{1}$. Then $s(H)\geqslant|V(H)|$.

######  Proof 2.4.

Observe that if $H$ is a core distinct from $K_{1}$, then it does not contain
isolated vertices. Therefore, for each $v\in V(H)$ we have
$N(v)\in\mathcal{S}(H)$. On the other hand, since $H$ is a core, it is
ramified. In particular, for every distinct $v,w\in V(H)$ we have $N(v)\neq
N(w)$. Hence different vertices give rise to different signature sets.

### Clique-Width and Clique-Width Expressions

For a positive integer $k$, we let a _$k$ -graph_ be a graph whose vertices
are labeled by $[k]$. For convenience, we consider a graph to be a $k$-graph
with all vertices labeled by $1$. We call the $k$-graph consisting of exactly
one vertex $v$ (say, labeled by $i$) an initial $k$-graph and denote it by
$i(v)$.

The _clique-width_ of a graph $G$ is the smallest integer $k$ such that $G$
can be constructed from initial $k$-graphs by means of iterative application
of the following three operations:

  1. 1.

Disjoint union (denoted by $\oplus$);

  2. 2.

Relabeling: changing all labels $i$ to $j$ (denoted by $\rho_{i\rightarrow
j}$);

  3. 3.

Edge insertion: adding an edge from each vertex labeled by $i$ to each vertex
labeled by $j$ ($i\neq j$; denoted by $\eta_{i,j}$).

A construction of a $k$-graph $G$ using the above operations can be
represented by an algebraic term composed of $\oplus$, $p_{i\rightarrow j}$
and $\eta_{i,j}$ (where $i\neq j$ and $i,j\in[k]$). Such a term is called a
$k$-expression defining $G$, and we often view it as a tree with each node
labeled with the appropriate operation. Conversely, we call the $k$-graph that
arises from a $k$-expression its _evaluation_. The _clique-width_ of $G$ is
the smallest integer $k$ such that $G$ can be defined by a $k$-expression
which we then also call a _clique-width expression_ of $G$.

Many graph classes are known to have constant clique-width; examples include
all graph classes of constant treewidth and co-graphs [5]. Moreover a fixed-
parameter algorithm is known to compute a $k$-expression of the input where
$k$ is bounded in $f({\operatorname{cw}})$ [26].

##  3 Algorithm

As our first contribution, we obtain an algorithm that will play a crucial
role for upper-bounding the fine-grained complexity of Hom($H$).

See 1.1

######  Proof 3.1.

Assume, w.l.o.g., that $G$ is connected and $|V(G)|>1$. We will describe a
dynamic program that proceeds in a leaf-to-root fashion along the provided
$k$-expression $\sigma$ of $G$. For a subexpression $\tau\subseteq\sigma$, we
denote the evaluation of $\tau$ by $G_{\tau}$, and by $V^{i}_{\tau}\subseteq
V(G_{\tau})$ the vertex set that has label $i$ in $G_{\tau}$. We say that $i$
is a _live label_ in $\tau$ if there is an edge of $G$ which is incident to
$V^{i}_{\tau}$ and does not appear in $G_{\tau}$. Denote the set of live
labels in $\tau$ by $L_{\tau}$. Since $G$ is connected,
$L_{\tau}\neq\emptyset$ for any proper subexpression $\tau$ of $\sigma$.

For each subexpression $\tau$ of $\sigma$, we will compute a set $P_{\tau}$
consisting of functions $p\colon L_{\tau}\to\mathcal{S}(H)$ where $p\in
P_{\tau}$ if and only if there exists a homomorphism $h_{p}$ from $G_{\tau}$
to $H$ such that $p(i)\subseteq S(h_{p}(V^{i}_{\tau}))$, $i\in L_{\tau}$. We
will say that $p\in P_{\tau}$ _describes_ the homomorphism $h_{p}$ in $\tau$
or, equivalently, that $h_{p}$ _witnesses_ $p$ in $\tau$. Intuitively, we will
use $p(i)$ to preemptively store the images of the neighbors of $V^{i}_{\tau}$
in the final graph $G$—that is why we store not only the exact signature, but
all signatures that occur as subsets. We remark that storing the “current”
images of the neighbors of $V^{i}_{\tau}$ in $G_{\tau}$ would be sufficient to
obtain a conceptually simpler fixed-parameter algorithm parameterized by
clique-width, but in that case it is not obvious how one can avoid a quadratic
dependency on clique-width in the exponent.

Observe that for any homomorhism $h\colon G_{\tau}\to H$, images of vertices
with live labels should be connected in $H$ with images of their future
neighbors. In particular, for any $i\in L_{\tau}$,
$S(h(V^{i}_{\tau}))\neq\emptyset$ and hence
$S(h(V^{i}_{\tau}))\in\mathcal{S}(H)$. Therefore $h$ is described in $\tau$ by
some $p\in P_{\tau}$. By definition, $L_{\sigma}=\emptyset$ and hence $G$ is
homomorphic to $H$ if and only if $P_{\sigma}$ contains the empty mapping,
i.e., if $P_{\sigma}=\\{\emptyset\\}$ (as opposed to $P_{\sigma}=\emptyset$).
It remains to show how to correctly compute each $P_{\tau}$. To do so, we
distinguish based on the outermost operation of $\tau$:

####  $\tau=i(v)$ for some $i\in[{\operatorname{cw}(G)}]$.

In this case $L_{\tau}=\\{i\\}$, and $P_{\tau}$ contains all functions
$p:\\{i\\}\mapsto\mathcal{S}(H)$ such that $p(i)\subseteq N_{H}(u)$ for some
$u\in V(H)$.

####  $\tau=\rho_{i\to j}(\tau^{\prime})$ and $P_{\tau^{\prime}}$ has already
been computed.

If $i\not\in L_{\tau^{\prime}}$, we can correctly set
$L_{\tau}=L_{\tau^{\prime}}$ and $P_{\tau}=P_{\tau^{\prime}}$. If $i\in
L_{\tau^{\prime}}$ and $j\not\in L_{\tau^{\prime}}$, then
$L_{\tau}=(L_{\tau^{\prime}}\setminus\\{i\\})\cup\\{j\\}$ and

$P_{\tau}=\left\\{p\colon L_{\tau}\to\mathcal{S}(H)\leavevmode\nobreak\
\mid\leavevmode\nobreak\ \exists p^{\prime}\in P_{\tau^{\prime}}:\quad
p(\ell)=\begin{cases}p^{\prime}(\ell)&\mbox{if }\ell\neq j\\\
p^{\prime}(i)&\mbox{if }\ell=j\end{cases}\right\\}.$

Finally, if $\\{i,j\\}\subseteq L_{\tau^{\prime}}$, then
$L_{\tau}=L_{\tau^{\prime}}\setminus\\{i\\}$ and
$P_{\tau}=\\{p^{\prime}|_{L_{\tau}}\leavevmode\nobreak\
\mid\leavevmode\nobreak\ p^{\prime}\in P_{\tau^{\prime}}\land
p^{\prime}(i)=p^{\prime}(j)\\}$.

For correctness in the last case, let $h$ be a homomorphism from $G_{\tau}$ to
$H$ and $S_{\ell}\in\mathcal{S}(H)$ be such that $S_{\ell}\subseteq
S(h(V^{\ell}_{\tau}))$, $\ell\in L_{\tau}$. Observe that
$V^{\ell}_{\tau}=V^{\ell}_{\tau^{\prime}}$ for $\ell\in
L_{\tau}\setminus\\{j\\}$ and $V^{j}_{\tau}=V^{j}_{\tau^{\prime}}\cup
V^{i}_{\tau^{\prime}}$. In particular, $S_{j}\subseteq
S(h(V^{i}_{\tau^{\prime}}))$ and $S_{j}\subseteq S(h(V^{j}_{\tau^{\prime}}))$.
By definition of $P_{\tau^{\prime}}$, there exists $p^{\prime}\in
P_{\tau^{\prime}}$ such that $p^{\prime}(\ell)=S_{\ell}$ for $\ell\in
L_{\tau}\setminus\\{j\\}$ and $p^{\prime}(i)=p^{\prime}(j)=S_{j}$. The
function $p\in P_{\tau}$, defined by $p=p^{\prime}|_{L_{\tau}}$, satisfies
$p(\ell)=S_{\ell}$ for each $\ell\in L_{\tau}$.

On the other hand, fix some $p\in P_{\tau}$. Let $p^{\prime}\in
P_{\tau^{\prime}}$ be a function such that $p$ arises from $p^{\prime}$ in the
construction of $P_{\tau}$. Consider a witness $h$ of $p^{\prime}$ in
$\tau^{\prime}$. For every $\ell\in L_{\tau}\setminus\\{j\\}$ we have
$V^{\ell}_{\tau}=V^{\ell}_{\tau^{\prime}}$ and so
$p(\ell)=p^{\prime}(\ell)\subseteq S(h(V^{\ell}_{\tau}))$. Moreover,
$p(j)=p^{\prime}(j)\subseteq S(h(V^{j}_{\tau^{\prime}}))$ and
$p(j)=p^{\prime}(i)\subseteq S(h(V^{i}_{\tau^{\prime}}))$. By Section 2, we
have $p(j)\subseteq S(h(V^{i}_{\tau^{\prime}}))\cap
S(h(V^{j}_{\tau^{\prime}}))=S(h(V^{i}_{\tau^{\prime}}\cup
V^{j}_{\tau^{\prime}}))=S(h(V^{j}_{\tau}))$. Hence $p$ witnesses $h$ in
$\tau$.

####  $\tau=\tau^{(1)}\oplus\tau^{(2)}$ where $P_{\tau^{(1)}}$ and
$P_{\tau^{(2)}}$ have already been computed.

In this case $L_{\tau}=L_{\tau^{(1)}}\cup L_{\tau^{(2)}}$ and

$P_{\tau}=\\{p=p_{1}\cup p_{2}\leavevmode\nobreak\ \mid\leavevmode\nobreak\
p_{1}\in P_{\tau^{(1)}}\wedge p_{2}\in P_{\tau^{(2)}}\wedge(\forall\ell\in
L_{\tau^{(1)}}\cap L_{\tau^{(2)}}\colon p_{1}(\ell)=p_{2}(\ell))\\}$

Intuitively, we construct a homomorphism on the disjoint union of two
subgraphs by “gluing together” the homomorphisms on the subgraphs. If the
subgraphs share any live labels, after this step they will all be treated
equally. For this reason we require the images of the neighbors of such labels
to be the same in both subgraphs. For correctness, let $h$ be a homomorphism
from $G_{\tau}$ to $H$ and $S_{\ell}\in\mathcal{S}(H)$ be such that
$S_{\ell}\subseteq S(h(V^{\ell}_{\tau}))$, $\ell\in L_{\tau}$. Observe that
for every $\ell\in L_{\tau^{(1)}}\cap L_{\tau^{(2)}}$,
$V^{\ell}_{\tau}\supseteq V^{\ell}_{\tau^{(i)}}$, so $S_{\ell}\subseteq
S(h(V^{\ell}_{\tau^{(i)}}))$, $i=1,2$. By definition, there exists $p_{i}\in
P_{\tau^{(i)}}$ such that $p_{i}(\ell)=S_{\ell}$ for $\ell\in L_{\tau^{(i)}}$,
$i=1,2$. Then for $p=p_{1}\cup p_{2}$ we have $p(\ell)=S_{\ell}$, $\ell\in
L_{\tau}$.

For the converse, fix some $p\in P_{\tau}$. Let $p_{1}\in P_{\tau^{(1)}}$,
$p_{2}\in P_{\tau^{(2)}}$ be functions such that $p=p_{1}\cup p_{2}$. Let
$h_{i}$ be a witness of $p_{i}$ in $\tau^{(i)}$, $i=1,2$. We define
$h=h_{1}\cup h_{2}$. Since $G_{\tau}$ doesn’t contain edges between
$V(G_{\tau^{(1)}})$ and $V(G_{\tau^{(2)}})$, $h$ is a homomorphism from
$G_{\tau}$ to $H$. For all $\ell\in L_{\tau^{(1)}}\setminus L_{\tau^{(2)}}$,
we have $p(\ell)=p_{1}(\ell)\subseteq
S(h_{1}(V^{\ell}_{\tau}))=S(h(V^{\ell}_{\tau}))$, similarly for $\ell\in
L_{\tau^{(2)}}\setminus L_{\tau^{(1)}}$. For $\ell\in L_{\tau^{(1)}}\cap
L_{\tau^{(2)}}$, we have $p(\ell)=p_{i}(\ell)\subseteq
S(h_{i}(V^{\ell}_{\tau^{(i)}}))$, $i=1,2$, so $p(\ell)\subseteq
S(h_{1}(V^{\ell}_{\tau^{(1)}}))\cap
S(h_{2}(V^{\ell}_{\tau^{(2)}}))=S(h(V^{\ell}_{\tau}))$. Hence $h$ is a witness
of $p$ in $\tau$.

####  $\tau=\eta_{i,j}(\tau^{\prime})$ and $P_{\tau^{\prime}}$ has already
been computed.

In this case $L_{\tau}=L_{\tau^{\prime}}\setminus I$ where
$I\subseteq\\{i,j\\}$ is the set of live labels in $\tau^{\prime}$ that are no
longer live labels in $\tau$. We set $P_{\tau}$ equal to

$\\{p:L_{\tau}\to\mathcal{S}(H)\leavevmode\nobreak\ |\leavevmode\nobreak\
\exists p^{\prime}\in P_{\tau^{\prime}}\colon p^{\prime}(i)\supseteq
S(p^{\prime}(j))\leavevmode\nobreak\ \wedge
p|_{{L_{\tau}}\setminus\\{i,j\\}}=p^{\prime}|_{{L_{\tau}}\setminus\\{i,j\\}}\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ p(i)\subseteq p^{\prime}(i)\leavevmode\nobreak\
\wedge\leavevmode\nobreak\ p(j)\subseteq p^{\prime}(j)\\}.$

Intuitively, we can add the edges between two live labels if and only if there
are edges between their images in $H$. Our restriction on $p^{\prime}$ is an
expression of this condition in terms of images of neighbors and their
signatures. Indeed, for correctness, let $h$ be a homomorphism from $G_{\tau}$
to $H$ and $S_{\ell}\in\mathcal{S}(H)$ be such that $S_{\ell}\subseteq
S(h(V^{\ell}_{\tau}))$, $\ell\in L_{\tau}$. There exists $p^{\prime}\in
P_{\tau^{\prime}}$ such that $p^{\prime}(\ell)=S_{\ell}$ for all $\ell\in
L_{\tau}\setminus\\{i,j\\}$, $p^{\prime}(i)=S(h(V^{i}_{\tau^{\prime}}))$ and
$p^{\prime}(j)=S(h(V^{j}_{\tau^{\prime}}))$. As $h$ is a homomorphism, we have
$h(V^{i}_{\tau^{\prime}})\times h(V^{j}_{\tau^{\prime}})\subseteq E(H)$, which
means that $S(h(V^{j}_{\tau^{\prime}}))\supseteq h(V^{i}_{\tau^{\prime}})$,
i.e. $p^{\prime}(j)\supseteq h(V^{i}_{\tau^{\prime}})$. Then
$S(p^{\prime}(j))\subseteq S(h(V^{i}_{\tau^{\prime}}))=p^{\prime}(i)$ and
hence $p^{\prime}$ gives rise to $p\in P_{\tau}$ such that $p(\ell)=S_{\ell}$,
$\ell\in L_{\tau}$.

On the other hand, let $p\in P_{\tau}$ arise from $p^{\prime}\in
P_{\tau^{\prime}}$. Consider a witness $h\colon G_{\tau^{\prime}}\to H$ of
$p^{\prime}$ in $\tau^{\prime}$. To see that $h$ preserves edges between
$V^{i}_{\tau^{\prime}}$ and $V^{j}_{\tau^{\prime}}$, recall that
$p^{\prime}(i)\supseteq S(p^{\prime}(j))$, so
$S(h(V^{i}_{\tau^{\prime}}))\supseteq p^{\prime}(i)\supseteq
S(p^{\prime}(j))\supseteq S(S(h(V^{j}_{\tau^{\prime}})))\supseteq
h(V^{j}_{\tau^{\prime}})$. Hence $h(V^{i}_{\tau^{\prime}})\times
h(V^{j}_{\tau^{\prime}})\subseteq E(H)$, so $h$ is a homomorphism. By
construction, for every $\ell\in L_{\tau}$ it holds that $p(\ell)\subseteq
p^{\prime}(\ell)\subseteq S(h(V^{\ell}_{\tau}))$. Therefore $h$ witnesses $p$
in $\tau$.

It is easy to verify that $|P_{\tau}|\leqslant s(H)^{{\operatorname{cw}(G)}}$
for each subexpression $\tau$ of $\sigma$. This means that in each step, the
computation requires time
$\mathcal{O}({\operatorname{cw}(G)}s(H)^{2}s(H)^{{\operatorname{cw}((G))}})$.
Overall this yields a complexity of
$\mathcal{O}(|V(G)|{\operatorname{cw}(G)}s(H)^{2}s(H)^{{\operatorname{cw}((G))}})\subseteq\mathcal{O}^{*}(s(H)^{{\operatorname{cw}(G)}})$.

##  4 On Products and Projectivity

While Theorem 1.1 will serve as the upper bound that will match our target
SETH-based lower bounds for Hom($H$) for the “most difficult” choices of $H$,
in many cases one can in fact supersede the algorithm’s runtime by exploiting
well-known properties of target graphs.

As a simple example showcasing this, consider the _wheel_ graph $W_{6}$ (see
Figure 1). Since $W_{6}$ is $3$-colorable, it holds that $W_{6}\to K_{3}$, and
since $K_{3}$ is a core and an induced subgraph of $W_{6}$, it is the core of
$W_{6}$. We recall that if $H$ is a core of $H^{\prime}$, then for every graph
$G$ it holds that $G\to H$ if and only if $G\to H^{\prime}$. Hence, having an
instance $G$ of Hom($W_{6}$), we can compute a core of $W_{6}$ (since we
assume that the target graph is fixed, this can be done in constant time), and
use Theorem 1.1 for $H=K_{3}$ to decide whether $G\to W_{6}$ in total running
time $\mathcal{O}^{*}(s(K_{3})^{{\operatorname{cw}(G)}})$. As
$s(K_{3})<s(W_{6})$ (as showcased in Figure 1), this yields a better running
time bound than the direct use of Theorem 1.1. While this example shows that
the signature number can decrease by taking an induced subgraph, we remark
that it can never increase.

1234560 | $\to$ |
---|---|---
Figure 1: The graphs $W_{6}$ (left) and $K_{3}$ (right). Colors on the
vertices of $W_{6}$ indicate the homomorphism $h:W_{6}\to K_{3}$. We note that
$\\{\\{0\\}\\}\cup\\{\\{0,i\\}\leavevmode\nobreak\ |\leavevmode\nobreak\
i\in[6]\\}\subseteq\mathcal{S}(W_{6})$. Since $K_{3}$ is a clique, we have
$s(K_{3})=6<7\leqslant s(W_{6})$.

Let $H$ and $H^{\prime}$ be graphs such that $H$ is an induced subgraph of
$H^{\prime}$. Then $s(H)\leqslant s(H^{\prime})$.

######  Proof 4.1.

Given a connected graph $Q$ without loops, one may consider an equivalence
relation $\sim_{Q}$ on the set of nonempty subsets of $V(Q)$ defined as
follows: $V_{1}\sim_{Q}V_{2}$ if and only if $V_{1}$ and $V_{2}$ have the same
signature sets in $Q$. Observe that $s(Q)$ is equal to the number of
equivalence classes of $\sim_{Q}$ minus one (as there are subsets $V$ such
that $S(V)=\emptyset$). Hence to prove the claim, it suffices to show that
whenever two subsets of $V(H)$ belong to different equivalence classes of
$\sim_{H}$, they also belong to different equivalence classes of
$\sim_{H^{\prime}}$. For this, consider any two non-empty subsets $V_{1}$ and
$V_{2}$ of $V(H)$ such that $V_{1}\nsim_{H}V_{2}$. Without loss of generality,
we assume that there exists $v\in(\bigcap_{t\in
V_{1}}N_{H}(t))\setminus(\bigcap_{t\in V_{2}}N_{H}(t))$. Then $vt\in
E(H)\subseteq E(H^{\prime})$ for every $t\in V_{1}$, i.e., $v$ belongs to the
signature set of $V_{1}$ in $H^{\prime}$. On the other hand, $vt_{0}\notin
E(H)$ for some $t_{0}\in V_{2}$. As $H$ is induced subgraph of $H^{\prime}$,
it means that $vt_{0}\notin E(H^{\prime})$, so $v$ doesn’t belong to the
signature set of $V_{2}$ in $H^{\prime}$ and hence
$V_{1}\nsim_{H^{\prime}}V_{2}$.

At this point, we may ask whether the procedure of simply computing the unique
core $H$ of the fixed target $H^{\prime}$ and then applying Theorem 1.1 for
$H$ could yield a tight upper bound for Hom($H^{\prime}$). Unfortunately, the
situation is more complicated than that, and we need to introduce a few
important notions in order to capture the problem’s fine-grained complexity.

Let the _direct product_ $H_{1}\times H_{2}$ of graphs $H_{1},H_{2}$ be the
graph defined as follows:

$\displaystyle V(H_{1}\times H_{2})$ $\displaystyle=V(H_{1})\times V(H_{2}),$
$\displaystyle E(H_{1}\times H_{2})$
$\displaystyle=\\{(x_{1},x_{2})(y_{1},y_{2}):x_{i}y_{i}\in E(H_{i})\textrm{
for every }i\in\\{1,2\\}\\}.$

We call $H_{1}$ and $H_{2}$ the _factors_ of $H_{1}\times H_{2}$. Clearly, the
operation $\times$ is commutative, and since it is also associative, we can
naturally extend the definition of direct product to more than two factors,
i.e., $H_{1}\times H_{2}\times\ldots\times
H_{m}=H_{1}\times(H_{2}\times\ldots\times H_{m})$. Note that for every graph
$H$ it holds that $H\times K^{*}_{1}=H$..

In the remaining part of the paper we will often consider vertices that are
tuples. If such a vertex is an argument of some function and in cases where
this does not lead to confusion, we omit one pair of brackets; similarly, we
omit internal brackets in nested tuples where this does not lead to confusion.
Moreover, for any graph $H$ and for an integer $\ell$, we denote by $H^{\ell}$
the graph $\overbrace{H\times\ldots\times H}^{\ell}$. As an example, instead
of writing $((x_{1},x_{2}),y_{1})\in((H_{1}\times H_{1})\times H_{2})$, we
write $(x_{1},x_{2},y_{1})\in(H_{1}^{2}\times H_{2})$.

If $H=H_{1}\times\ldots\times H_{m}$ for some graphs $H_{1},\ldots,H_{m}$, we
say that $H_{1}\times\ldots\times H_{m}$ is a _factorization_ of $H$. A graph
$H$ on at least two vertices is _prime_ if the fact that $H=H_{1}\times H_{2}$
for some graphs $H_{1},H_{2}$ implies that $H_{1}=K^{*}_{1}$ or
$H_{2}=K^{*}_{1}$. If $H$ has a factorization $H_{1}\times\ldots\times H_{m}$
such that for every $i\in[m]$ the graph $H_{i}$ is prime, we call
$H_{1}\times\ldots\times H_{m}$ a _prime factorization_ of $H$.

######  Theorem 4.2 ([8, 14]).

Any connected non-bipartite graph with more than one vertex has a unique prime
factorization (into factors with possible loops).

Consider a graph $H_{1}\times\ldots\times H_{m}$, and let $i\in[m]$. A mapping
$\pi_{i}:V(H_{1}\times\ldots\times H_{m})\to V(H_{i})$ such that
$\pi_{i}(x_{1},\ldots,x_{\ell})=x_{i}$ is called the ($i$-th) _projection_ of
$H_{1}\times\ldots\times H_{m}$. Clearly, such a mapping is always a
homomorphism.

Let $G,H_{1},\ldots,H_{m}$ be graphs. Then $G\to H_{1}\times\ldots\times
H_{m}$ if and only if for every $i\in[m]$ we have $G\to H_{i}$.

######  Proof 4.3.

Let $f:G\to H_{1}\times\ldots\times H_{m}$. Then for every $i\in[m]$ we have a
homomorphism $\pi_{i}:G\to H_{i}$. Conversely, if for every $i\in[m]$ we have
$g_{i}:G\to H_{i}$, then we can define $g:G\to H_{1}\times\ldots\times H_{m}$
as $g(x)=(g_{1}(x),\ldots,g_{m}(x))$.

Crucially, since there exist cores that are not prime [25], in some cases
Observation 4 allows us to improve the bounds given by Theorem 1.1 even if $H$
is a core, simply by considering all possible factorizations of $H$.

######  Corollary 4.4.

Let $H$ be a graph with factorization $H_{1}\times\ldots\times H_{m}$, and let
$G$ be an instance graph of Hom($H$). Assuming that the clique-width
expression $\sigma$ of $G$ of width ${\operatorname{cw}(G)}$ is given, the
Hom($H$) problem can be solved in time
$\max_{i\in[m]}\mathcal{O}^{*}\big{(}s(H_{i})^{\operatorname{cw}(G)}\big{)}$.

######  Proof 4.5.

Observe that if $G$ is an instance of Hom($H$), by Theorem 1.1 for every
$i\in[m]$ we can decide whether $G\to H_{i}$ in time
$\mathcal{O}^{*}\big{(}s(H_{i})^{\operatorname{cw}(G)}\big{)}$. Then, if $G$
is a yes-instance of Hom($H_{i}$) for every $i\in[m]$, we return that $G$ is a
yes-instance of Hom($H$). Otherwise, we return that $G$ is a no-instance of
Hom($H$). The correctness of this procedure follows from Section 4.

On the other hand, the notion of signature sets we introduced in the previous
section behaves multiplicatively with respect to taking direct product of
graphs.

Let $H=H_{1}\times H_{2}$. Then
$\mathcal{S}(H)=\mathcal{S}(H_{1})\times\mathcal{S}(H_{2})$.

######  Proof 4.6.

We prove that $\mathcal{S}(H)$ is of form $\\{S(T_{1})\times
S(T_{2}):T_{i}\subseteq V(H_{i}),S(T_{i})\neq\emptyset\textrm{ for }i=1,2\\}$.

Let $T_{1}$ and $T_{2}$ be some subsets of, respectively, $V(H_{1})$ and
$V(H_{2})$. Clearly,

$\displaystyle S(T_{1})\times S(T_{2})=[\bigcap_{t\in
T_{1}}N(t)]\times[\bigcap_{t^{\prime}\in
T_{2}}N(t^{\prime})]=\bigcap_{(t,t^{\prime})\in T_{1}\times
T_{2}}N(t,t^{\prime})=S(T_{1}\times T_{2}).$ (1)

Therefore, if $S(T_{1})$ and $S(T_{2})$ are non-empty, we get that
$S(T_{1})\times S(T_{2})\in\mathcal{S}(H).$

To see that
$\mathcal{S}(H)\subseteq\mathcal{S}(H_{1})\times\mathcal{S}(H_{2})$, we show
that for every $T\subseteq V(H)$ set $S(T)$ is of the form $S(T_{1})\times
S(T_{2})$ for some $T_{1},T_{2}$. Define $T_{1}$ and $T_{2}$ to be minimal
sets such that $T\subseteq T_{1}\times T_{2}$. Hence, by (1), $S(T_{1})\times
S(T_{2})=S(T_{1}\times T_{2})\subseteq S(T)$. On the other hand, for every
$(s,s^{\prime})\in S(T)$ we have $s\in\bigcap_{t\in T_{1}}N(t)$ and
$s^{\prime}\in\bigcap_{t^{\prime}\in T_{2}}N(t^{\prime})$, so the equality
follows.

In particular, it follows from Section 4 that if $H$ is a graph with
factorization $H_{1}\times\ldots\times H_{m}$, then
$s(H)=s(H_{1})\cdot\ldots\cdot s(H_{m})$. Therefore if there exist at least
two factors $H_{i},H_{j}$ such that $s(H_{i})>1$, $s(H_{j})>1$, Corollary 4.4
yields a better running time than Theorem 1.1.

In order to analyze the possible matching lower bounds for our algorithms, in
the remaining part of the section, we focus only on connected non-trivial
cores $H$ that are provided with their unique prime factorization
$H_{1}\times\ldots\times H_{m}$; if $H$ is prime, we technically consider this
factorization to be $H\times K_{1}^{*}$ (noting that this is not a prime
factorization, and that $K_{1}^{*}$ is the only non-simple graph in this
article). We note that the factors of a core must satisfy some necessary
conditions.

[[25]] Let $H$ be a connected, non-trivial core with factorization
$H=H_{1}\times\ldots\times H_{m}$ such that $H_{i}\neq K^{*}_{1}$ for all
$i\in[m]$. Then for every $i\in[m]$ the graph $H_{i}$ is a connected non-
trivial core, incomparable with $H_{j}$ for $j\in[m]-\\{i\\}$.

4.6 in particular implies that if $H$ is a connected non-trivial graph with
factorization $H_{1}\times\ldots\times H_{m}$, then at least one of the
factors $H_{i}$ must be non-trivial, and that $K_{1}$ and $K_{2}$ never appear
as factors of a connected non-trivial graph.

In the remaining part of this section we introduce a few more important
definitions, in particular, the well-established notion of _projectivity_ for
non-trivial graphs $H$.

We say that a homomorphism $f:H^{\ell}\to H$, for some $\ell\geqslant 2$, is
_idempotent_ if for each $x\in V(H)$ it holds that $f(x,\ldots,x)=x$. Graph
$H$ is _projective_ if for every $\ell\geqslant 2$, every idempotent
homomorphism $f:H^{\ell}\to H$ is a projection. We note that every projective
graph on at least three vertices must be connected, ramified, non-bipartite
and prime [22].

Here, we introduce a generalization of the projectivity property for non-
trivial cores, which turns out to be the central component required to
establish the lower bound for our problem. As a first step towards this, we
lift the notion of idempotency as follows. Let $H$ be a connected, non-trivial
prime core, and let $W$ be either a connected core on at least three vertices
incomparable with $H$, or the graph $K^{*}_{1}$. Let $f:A\rightarrow H$ be a
homomorphism where $A=H^{\ell}\times W$; observe that $\ell$ is uniquely
determined by either $W$ being incomparable with the prime core $H$, or $W$
being $K^{*}_{1}$. We say that $f$ is _$H$ -idempotent_ if for each $x\in
V(H),y\in V(W)$ it holds that $f(x,\ldots,x,y)=x$.

Now, let us consider a non-trivial core $H$ which admits a prime factorization
$H_{1}\times\ldots\times H_{m}$ and let $i\in[m]$. We say that $H$ is _$H_{i}$
-projective_ if $H_{i}$ is non-trivial and every $H_{i}$-idempotent
homomorphism $f:H_{1}\times\ldots\times H_{i-1}\times H_{i}^{\ell}\times
H_{i+1}\times\ldots\times H_{m}\to H_{i}$ is a projection. In other words, for
every homomorphism $f:H_{1}\times\ldots H_{i-1}\times H_{i}^{\ell}\times
H_{i+1}\times\ldots\times H_{m}\to H_{i}$ such that for every $x\in
V(H_{i}),y_{j}\in V(H_{j})$ for $j\in[m]-\\{i\\}$ it holds that
$f(y_{1},\ldots,y_{i-1},x,\ldots,x,y_{i+1},\ldots,y_{m})=x$, we must have that
there exists $q\in\\{i,\ldots,i+\ell-1\\}$ such that $f\equiv\pi_{q}$. Recall
that if $H$ is a non-trivial projective core, then it must be prime, so
$H\times K_{1}^{*}$ is its only possible factorization. It is straightforward
to verify that in a such case $H$ is $H$-projective.

Since the direct product of graphs is commutative, if
$H=H_{1}\times\ldots\times H_{m}$ is $H_{i}$-projective for some $i\in[m]$, to
simplify the notation we will often assume w.l.o.g. that $i=1$.

##  5 Hardness

In this section, we focus on establishing the desired lower bounds, stated
below.

See 1.2

We divide our proof into two main steps. First, we show that in our setting,
instead of considering the Hom($H$) problem, we may focus on the Homomorphism
Extension problem, denoted HomExt($H$). For a fixed $H$, HomExt($H$) takes as
an instance a pair $(G^{\prime},h^{\prime})$, where $G^{\prime}$ is a graph
and $h^{\prime}:V^{\prime}\to V(H)$ is a mapping from some
$V^{\prime}\subseteq V(G^{\prime})$. We ask whether there exists _an
extension_ of $h^{\prime}$ to $G^{\prime}$, i.e., a homomorphism
$h:G^{\prime}\to H$ such that $h|_{V^{\prime}}\equiv h^{\prime}$.

The HomExt($H$) is clearly a generalization of the Hom($H$) problem. However,
as the first step of our proof, we show that if $H$ is a fixed non-trivial
core, each instance $(G^{\prime},h^{\prime})$ of HomExt($H$) can be
transformed in polynomial time into an instance $G$ of Hom($H$), such that
${\operatorname{cw}(G^{\prime})}$ and ${\operatorname{cw}(G)}$ differ only by
a constant.

######  Theorem 5.1.

Let $H$ be a fixed non-trivial core. Given an instance
$(G^{\prime},h^{\prime})$ of HomExt($H$), we can construct an equivalent
instance $G$ of Hom($H$) such that
${\operatorname{cw}(G)}\leqslant{\operatorname{cw}(G^{\prime})}+|V(H)|$.

######  Proof 5.2.

Let $V^{\prime}\subseteq V(G^{\prime})$ be the domain of $h^{\prime}$. We
construct $G$ by taking a copy $\hat{G^{\prime}}$ of $G^{\prime}$ and a copy
$\hat{H}$ of $H$. Then, for every $v\in V^{\prime}$ we add all the edges with
one endpoint in $v$ and another one in $N_{\hat{H}}(h^{\prime}(v))$.

Observe that if there exists an extension $h:G^{\prime}\to H$ of $h^{\prime}$,
then $h$ can be also extended to $G$, by setting $h(v)=v$ for every $v\in
V(\hat{H})$. Indeed, let $uv\in E(G)$. If $u,v\in V(\hat{G^{\prime}})$, then
$h(u)h(v)\in E(H)$, by definition of the extension of $h^{\prime}$ to
$G^{\prime}$. If $u,v\in V(\hat{H})$, then $h(u)h(v)=uv\in E(H)$. Finally,
assume that $u\in V(\hat{G^{\prime}}),v\in V(\hat{H})$. Note that, by
definition of $G$, this can happen only if $u\in V^{\prime}$ and $v$ is
adjacent to $h^{\prime}(u)$. Hence, $h(u)h(v)=h^{\prime}(u)v\in E(H)$.

For the reverse direction, assume that there exists a homomorphism $f:G\to H$.
We show that there exists an extension $h:G^{\prime}\to H$ of $h^{\prime}$.
Let $\sigma:\hat{H}\to H$ be a restriction of $f$ to $\hat{H}$. Since $H$ is a
core, $\sigma$ is an automorphism of $H$. We claim that $g=\sigma^{-1}\circ
f:G\to H$, restricted to $G^{\prime}$, is an extension of $h^{\prime}$.
Clearly, $g$ is a composition of homomorphisms, so also a homomorphism.
Therefore, it remains to show that for every $v\in V^{\prime}$ we have
$h^{\prime}(v)=g(v)$. Since $H$ is a core, and
$N_{\hat{H}}(h^{\prime}(v))\subseteq N_{G}(v)$, we have that
$f(v)=f(h^{\prime}(v))$. It follows that $g(v)=\sigma^{-1}\circ
f(v)=\sigma^{-1}\circ f(h^{\prime}(v))=g(h^{\prime}(v))$. However, recall that
for every $u\in V(H)$ we have that $g(u)=u$, so in particular,
$g(h^{\prime}(v))=h^{\prime}(v)$.

To see that
${\operatorname{cw}(G)}\leqslant{\operatorname{cw}(G^{\prime})}+|V(H)|$,
observe that we added exactly $|V(H)|$ vertices to $G^{\prime}$. This means we
can modify a clique-width expression $\sigma$ for $G^{\prime}$ to obtain a
clique-width expression of $G$ as follows. Each added vertex is introduced
with a designated label that is distinct from all labels used in $\sigma$.
Then each subexpression of $\sigma$ that introduces a vertex of $G^{\prime}$
can be replaced by an expression that introduces the vertex and inserts all
required edges to the added vertices. Finally, one can insert the missing
edges between added vertices.

As the second step, we prove the following theorem.

######  Theorem 5.3.

Let $H$ be a fixed non-trivial core with prime factorization
$H_{1}\times\ldots\times H_{m}$. Assume that $H$ is $H_{i}$-projective for
some $i\in[m]$. Then there is no algorithm solving HomExt($H$) in time
$\mathcal{O}^{*}((s(H_{i})-\varepsilon)^{{\operatorname{cw}(G^{\prime})}})$
for any $\varepsilon>0$, unless the SETH fails.

Before we proceed to the proof of Theorem 5.3, we show that it implies Theorem
1.2.
Theorem 5.3 $\to$ Theorem 1.2: Let $H$ be a non-trivial core with a prime
factorization $H_{1}\times\ldots\times H_{m}$. W.l.o.g. assume that $H$ is
$H_{1}$-projective. Suppose that Theorem 1.2 does not hold, i.e., there exists
an algorithm $A$ that solves every instance $G$ of Hom($H$) in time
$\mathcal{O}^{*}((s(H_{1})-\varepsilon)^{{\operatorname{cw}(G)}})$.

Let $(G^{\prime},h^{\prime})$ be an instance of HomExt($H$). We use Theorem
5.1 to transform $(G^{\prime},h^{\prime})$ into an equivalent instance $G$ of
Hom($H$), such that
${\operatorname{cw}(G)}\leqslant{\operatorname{cw}(G^{\prime})}+|V(H)|$. Then,
we use $A$ to decide whether $G\to H$ in time

$\mathcal{O}^{*}\left((s(H_{1})-\varepsilon)^{{\operatorname{cw}(G)}}\right)=\mathcal{O}^{*}\left((s(H_{1})-\varepsilon)^{{\operatorname{cw}(G^{\prime})}}\cdot(s(H_{1})-\varepsilon)^{|V(H)|}\right).$

Since $H$ is a fixed graph, $(s(H_{1})-\varepsilon)^{|V(H)|}$ is a constant,
and therefore
$\mathcal{O}^{*}\left((s(H_{1})-\varepsilon)^{{\operatorname{cw}(G)}}\right)=\mathcal{O}^{*}\left((s(H_{1})-\varepsilon)^{{\operatorname{cw}(G^{\prime})}}\right)$.
Since $G\to H$ if and only if $(G^{\prime},h^{\prime})$ is a yes-instance of
HomExt($H$), we get a contradiction with Theorem 5.3. We will prove Theorem
5.3 for $i=1$, which covers other cases by commutativity of direct products.
We begin by constructing certain gadgets that will be used later. Let $H$ be a
fixed core with factorization $H_{1}\times\ldots\times H_{m}$. We define
$W=H_{2}\times\ldots\times H_{m}$ if $m\geqslant 2$, and $W=K^{*}_{1}$
otherwise. Clearly, $H_{1}\times W$ is a (not necessarily prime) factorization
of $H$. Moreover, if for some graph $G$ we have a homomorphism $f:G\to
H_{1}\times\ldots\times H_{m}$, for $i\in[m]$ we denote by $f_{i}$ the
homomorphism $\pi_{i}\circ f:G\to H_{i}$. Let $S$ be a set of pairs of
vertices of $H_{1}$, and let $w,w^{\prime}\in V(W)$. We say that a tuple
$(F,h^{\prime},p,q)$, such that $F$ is a graph, $h^{\prime}:V^{\prime}\to H$
is a mapping with domain $V^{\prime}\subseteq V(F)$, and $p,q\in V(F)$, is an
_$(S,w,w^{\prime})$ -gadget_ if

  1. (S1)

for every extension $h:F\to H$ of $h^{\prime}$, it holds that
$(h_{1}(p),h_{1}(q))\in S$,

  2. (S2)

for every pair $(s_{1},s_{2})\in S$ there exists an extension $h:F\to H$ of
$h^{\prime}$ such that $h(p)=(s_{1},w)$ and $h(q)=(s_{2},w^{\prime})$.

######  Lemma 5.4.

Let $H$ be a non-trivial connected core with factorization $H_{1}\times W$,
let $S\subseteq V(H_{1})^{2}$, and let $w,w^{\prime}\in V(W)$. Assume that $H$
is $H_{1}$-projective. Then there exists an $(S,w,w^{\prime})$-gadget.

######  Proof 5.5.

Let $S=\\{(s^{1}_{1},s^{1}_{2}),\ldots,(s^{\ell}_{1},s^{\ell}_{2})\\}$. Define

$\displaystyle F=H_{1}^{\ell}\times W,\ \textrm{ and }\
p=(s^{1}_{1},\ldots,s^{\ell}_{1},w),\ \textrm{ and
}q=(s^{1}_{2},\ldots,s^{\ell}_{2},w^{\prime}).$

Let $V^{\prime}=\\{(x,x,\ldots,x,y)\leavevmode\nobreak\ |\leavevmode\nobreak\
x\in V(H_{1}),y\in V(W)\\}$, and let $h^{\prime}(x,\ldots,x,y)=(x,y)$. We
claim that $(F,h^{\prime},p,q)$ is an $(S,w,w^{\prime})$-gadget.

The condition 1 follows from the fact that $H$ is $H_{1}$-projective. Indeed,
if $h:F\to H_{1}\times W$ is an extension of $h^{\prime}$, observe that
$h_{1}$ must be $H_{1}$-idempotent, and hence a projection on one of the
$\ell$ first coordinates. Therefore, we must have $(h_{1}(p),h_{1}(q))\in S$.

For (S2), take any $(s^{i}_{1},s^{i}_{2})\in S$ and let $h:F\to H_{1}\times
W$, $h(x)=(\pi_{i}(x),\pi_{\ell+1}(x)).$ Clearly, $h$ is an extension of
$h^{\prime}$, and it is easy to verify that $h(p)=(s^{i}_{1},w)$ and
$h(q)=(s^{i}_{2},w^{\prime})$.

We say that $S\subseteq V(H_{1})^{2}$ is _proper_ , if for every coordinate
there exist two elements in $S$ that differ on that coordinate, i.e., $S$ is
not of the form $\\{s\\}\times U$ nor $U\times\\{s\\}$ for some $s\in
V(H_{1})$ and $U\subseteq V(H_{1})$. Note that if $S$ is proper and
$(F,h^{\prime},p,q)$ is an $(S,w,w^{\prime})$-gadget constructed as in Lemma
5.4, then neither $p$ nor $q$ belong to the domain of $h^{\prime}$. For fixed
vertices $a,b\in V(H_{1})$, let
$S_{a,b}=\\{(a^{\prime},b^{\prime}):a^{\prime}\neq a,b^{\prime}\in
V(H_{1})\\}\cup\\{(a,b)\\}$. We call the $(S_{a,b},w,w^{\prime})$-gadget
$(F,h^{\prime},p,q)$ an _$((a,b),w,w^{\prime})$ -implication-gadget_.
Intuitively, an $((a,b),w,w^{\prime})$-implication-gadget works as the
implication $a\Rightarrow b$, since in every homomorphism $h:F\to H$ that
extends $h^{\prime}$, if $h_{1}(p)=a$, then $h_{1}(q)=b$. Let $a,b,c\in
V(H_{1})$, $w\in V(W)$, and let $t$ be an integer. A triple $(F,h^{\prime},R)$
such that $F$ is a graph, $h^{\prime}:V^{\prime}\to H_{1}\times W$ is a
partial mapping from some $V^{\prime}\subseteq V(F)$, and $R$ is a subset of
$V(F)$ of cardinality $t$ is an _$t$ -or-gadget with domain $((a,b,c),w)$_ if

  1. (O1)

for every homomorphism $h:F\to H$ that is an extension of $h^{\prime}$, and
for every $u\in R$ we have that $h_{1}(u)\in\\{a,b,c\\}$ and there exists
$v\in R$ such that $h_{1}(v)=a$,

  2. (O2)

for every $v\in R$ there exists a homomorphism $h:F\to H$ that is an extension
of $h^{\prime}$, such that $h(v)=(a,w)$ and for every $u\in R-\\{v\\}$ it
holds that $h(u)\in\\{(b,w),(c,w)\\}$.

######  Lemma 5.6.

Let $H$ be a non-trivial core with factorization $H_{1}\times W$. Assume that
$H$ is $H_{1}$-projective. Then for every distinct $a,b,c\in V(H_{1})$, every
$w\in V(W)$ and every $t$, there exists a $t$-or-gadget $(F,h^{\prime},R)$
with domain $((a,b,c),w)$.

######  Proof 5.7.

We consider separately the cases $t=1$ and $t=2$. Observe that in case $t=1$
our gadget needs to be a graph that has a vertex $r\in R$ that is always
mapped to $(a,w)$. Hence, we set $F=K_{1}$, $R=V(F)$, and
$h^{\prime}(v)=(a,w)$ for $v\in V(F)$.

If $t=2$, let $S=\\{(a,b),(b,a),(a,a)\\}$, we introduce an independent set
$R=\\{r_{1},r_{2}\\}$ and $(S,w,w)$-gadget $(F,h^{\prime},r_{1},r_{2})$. To
see that $(F,h^{\prime},R)$ satisfies 1, consider any extension $f:F\to H$ of
$h^{\prime}$. As $(F,h^{\prime},r_{1},r_{2})$ is $(S,w,w)$-gadget, we have
$(f_{1}(r_{1}),f_{1}(r_{2}))\in\\{(a,b),(a,a),(b,a)\\}$. For 2, recall that by
the property 2 of $S$-gadget there exist extensions $f^{(1)}$ and $f^{(2)}$ of
$h^{\prime}$ such that $(f^{(1)}_{1}(r_{1}),f^{(1)}_{1}(r_{2}))=(a,b)$ and
$(f^{(2)}_{1}(r_{1}),f^{(2)}_{1}(r_{2}))=(b,a)$.

Assume then that $t>2$, and let

$\displaystyle S$ $\displaystyle={\\{a,b,c\\}}^{2}-\\{(b,c),(c,b)\\},$
$\displaystyle S_{\text{left}}$
$\displaystyle=\\{(a,a),(a,b),(a,c),(c,a),(c,c)\\},$ $\displaystyle
S_{\text{right}}$ $\displaystyle=\\{(a,a),(a,b),(b,a),(b,b),(c,a)\\}$

be subsets of $V(H_{1})^{2}$. We introduce an independent set
$R=\\{r_{1},\ldots,r_{t}\\}$ of $t$ vertices and one copy of
$(S_{\text{left}},w,w)$-gadget $(F_{1},h^{\prime}_{1},r_{1},r_{2})$. Then, for
$j\in\\{2,\ldots,t-2\\}$, we introduce an $(S,w,w)$-gadget
$(F_{j},h^{\prime}_{j},r_{j},r_{j+1})$ (we note that if $t=3$, we do not
introduce these). Last, we introduce one copy of
$(S_{\text{right}},w,w)$-gadget $(F_{t-1},h^{\prime}_{t-1},r_{t-1},r_{t})$. We
note that sets $S,S_{\text{left}}$, and $S_{\text{right}}$ are proper, so the
domains of the partial mappings $h^{\prime}_{j}$, $j\in\\{1,\ldots,t-1\\}$,
are pairwise disjoint. In particular, the union
$h^{\prime}=\bigcup_{j=1}^{t}h^{\prime}_{j}$ is a well-defined mapping. We
define $F$ to be the union of all the graphs from the introduced gadgets and
claim that $(F,h^{\prime},R)$ is a $t$-or-gadget.

We first show that 1 holds. Assume that there exists an extension $f:F\to H$
of $h^{\prime}$, and $j^{\prime}\in[t]$ such that
$f_{1}(r_{j^{\prime}})\notin\\{a,b,c\\}$. This implies that there exists
$j\in\\{j^{\prime}-1,j^{\prime}\\}$ such that
$(f_{1}(r_{j}),f_{1}(r_{j+1}))\notin S^{\prime}$ for any
$S^{\prime}\in\\{S_{\text{left}},S,S_{\text{right}}\\}$. This is a
contradiction with $(F_{,}h^{\prime}_{j},p_{j},q_{j})$ being an
$(S^{\prime},w,w)$-gadget, as it violates 1.

Now assume that there exists an extension $f:F\to H$ of $h^{\prime}$ such that
for every $j\in[t]$ we have that $f_{1}(r_{j})\in\\{b,c\\}$. The definition of
$S_{\text{left}}$ and $S_{\text{right}}$, respectively, implies that
$f_{1}(r_{1})=c$ and $f_{1}(r_{t})=b$. Hence, there exists $j\in[t-1]$ such
that $f_{1}(r_{j})=c$ and $f_{1}(r_{j+1})=b$. However, observe that the pair
$(c,b)$ does not belong to set $S^{\prime}$, for
$S^{\prime}\in\\{S_{\text{left}},S,S_{\text{right}}\\}$, and since we
introduced an $S^{\prime}$-gadget from $r_{j}$ to $r_{j+1}$, this leads to a
contradiction.

To see that 2 holds as well, fix some $r_{j}\in R$ and define

$\displaystyle f^{\prime}(r_{\ell})=\begin{cases}(a,w),&\textnormal{ if
}\ell=j,\\\ (c,w),&\textnormal{ if }\ell<j,\\\ (b,w),&\textnormal{ if
}\ell>j,\end{cases}$

If $j=1$, then since $(a,b)\in S_{\text{left}}$, $(b,b)\in S$ and $(b,b)\in
S_{\text{right}}$, the property 2 asserts that we can construct a homomorphism
$f:F\to H$ that extends $h^{\prime}$ and $f^{\prime}$. The same holds also if
$j=t$, (since $(c,c)\in S_{\text{left}}$, $(c,c)\in S$ and $(c,a)\in
S_{\text{right}}$), and if $1<j<t$ (since $(c,c)\in S_{\text{left}}$,
$(c,c),(c,a),(a,b),(b,b)\in S$ and $(b,b)\in S_{\text{right}}$).

Finally, all that remains is to prove Theorem 5.3. Our reduction generalizes
the construction used by Lampis [20] to reduce an SETH lower-bounded
constraint satisfaction problem to $k$-Coloring. Intuitively speaking, in that
construction possible variable assignments are encoded by mapping specified
vertices to arbitrary non-trivial subsets of the colors. The straightforward
generalization of this approach to our setting would be to map to non-trivial
subsets of $V(H)$. However, the structure of $H$ allows only certain
configurations of subsets as images for the specified vertices in a solution
for Hom($H$)—which is precisely where the signature sets come into play.

Let $q,B\geqslant 2$ be integers. We will reduce from the $q$-CSP-$B$ problem
that is defined as follows. An instance of $q$-CSP-$B$ consists of a set $X$
of variables and a set $C$ of $q$-constraints. A $q$-constraint $c\in C$ is a
$q$-tuple of elements from $X$ and a set $P(c)$ of $q$-tuples of elements from
$[B]$ (i.e., $P(c)\subseteq[B]^{q})$. The $q$-CSP-$B$ problem asks whether
there exists an assignment $\gamma:X\to[B]$, such that each constraint is
satisfied, i.e., if $c=((x_{1},\ldots,x_{q}),P(c))\in C$, then
$(\gamma(x_{1}),\ldots,\gamma(x_{q}))\in P(c)$. Note that we can assume that
$q$-constraints in our $q$-CSP-$B$ instance may have less than $q$ vertices,
as it is always possible to add at most $q-1$ dummy variables to $X$ and add
them to constraints that are of smaller size.

We will use the following theorem.

######  Theorem 5.8 ([20]).

For any $B\geqslant 2,\varepsilon>0$ we have the following: assuming the SETH,
there exists $q$ such that $n$-variable $q$-CSP-$B$ cannot be solved in time
$\mathcal{O}^{*}((B-\varepsilon)^{n})$.

We have all the tools to perform the final reduction.

######  Proof 5.9 (Proof of Theorem 5.3).

Recall that it is sufficient to prove the theorem when $H=H_{1}\times W$ is
non-trivial $H_{1}$-projective core ($W=K^{*}_{1}$ if $H=H_{1}$). Fix
$\varepsilon>0$ and set $B=s(H_{1})$. As $H$ is $H_{1}$-projective, $H_{1}$ is
non-trivial and hence contains at least three distinct vertices $a$, $b$ and
$c$. In particular, $B\geqslant 3$ by Observation 2. Since $H=H_{1}\times W$
is a non-trivial core, $W$ must have at least one edge $ww^{\prime}$ (it may
happen that $w=w^{\prime}$). From now on $a,b,c,w$ and $w^{\prime}$ are fixed.
Let $q$ be the smallest number such that $q$-CSP-$B$ on $n$ variables cannot
be solved in time $\mathcal{O}^{*}((B-\varepsilon)^{n})$ assuming the SETH,
given by Theorem 5.8.

Let $\varphi$ be an instance of $q$-CSP-$B$, where
$X=\\{x_{1},\ldots,x_{n}\\}$ is the set of variables and
$C=\\{c_{0},\ldots,c_{m-1}\\}$ is the set of constraints. For every
$j\in\\{0,\ldots,m-1\\}$ denote by $X_{j}$ the set of variables that appear in
the constraint $c_{j}$. Let $P(c_{j})=\\{f^{j}_{1},\ldots,f^{j}_{p_{j}}\\}$ be
the set of assignments from $X_{j}$ to $[B]$ that satisfy the constraint
$c_{j}$. Let $L=m(n|H_{1}|+1)$, and let $\lambda:[B]\to\mathcal{S}(H_{1})$ be
some fixed bijection.

We construct the instance $G_{\varphi}$ of HomExt($H$). For each
$j\in\\{0,\ldots L-1\\}$, let $j^{\prime}=j\mod m$. Let
$R_{j}=\\{r^{j}_{1},\ldots,r^{j}_{p_{j^{\prime}}}\\}$, where each vertex
$r^{j}_{k}$ corresponds to the assignment $f^{j^{\prime}}_{k}$. We introduce
the $p_{j^{\prime}}$-or-gadget $(F_{j},h^{\prime}_{j},R_{j})$ with domain
$((a,b,c),w)$.

For each $x_{i}\in X_{j^{\prime}}$, and for each $f^{j^{\prime}}_{k}\in
P(c_{j^{\prime}})$ we do the following:

  1. 1.

Let $y=f^{j^{\prime}}_{k}(x_{i})\in[B]$. Construct an independent set
$V^{j,k}_{i}$ of $|\lambda(y)|$ vertices and an independent set $U^{j,k}_{i}$
of $|S(\lambda(y))|$ vertices.

  2. 2.

For each $d\in\lambda(y)$ select a distinct vertex $z\in V^{j,k}_{i}$ and add
an $((a,d),w,w^{\prime})$-implication-gadget from $r^{j}_{k}$ to $z$. For each
$d\in S(\lambda(y))$ select a distinct vertex $z\in U^{j,k}_{i}$ and add an
$((a,d),w,w^{\prime})$-implication-gadget from $r^{j}_{k}$ to $z$.

  3. 3.

Connect all vertices of $U^{j,k}_{i}$ with all vertices of previously
constructed sets $V^{\ell,k^{\prime}}_{i}$ for $\ell<j$ and
$k^{\prime}\in[p_{\ell}]$ (see Figure 2).

Figure 2: Construction of the instance of HomExt($K_{3}$) for $B=6$, variable
set $X=\\{x_{1},x_{2},x_{3}\\}$ and constraint set $C=\\{c_{0},c_{1}\\}$. The
sattisfying assignments $f^{j}_{k}$ and the bijection $\lambda$ are as
depicted. The vertices of $K_{3}$ are
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}b},{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}c}$.
Top: fragment of $G_{\varphi}$ restricted to $j=0,1$. Bottom: homomorphism
from $G_{\varphi}$ to $H$ corresponding to the sattisfying assignment
$\gamma$.

The partial mapping $h^{\prime}$ is the union of all the partial mappings that
are introduced by all the gadgets. This finishes the construction of the
instance $(G_{\varphi},h^{\prime})$ of HomExt($H$).

######  Claim 1.

If $\varphi$ is a yes-instance of $q$-CSP-$B$, then there exists a
homomorphism $h:G_{\varphi}\to H$ that extends $h^{\prime}$.

######  Proof 5.10 (Proof of Claim).

If $\varphi$ is a yes-instance of $q$-CSP-$B$, then there exists an assignment
$\gamma:X\to[B]$ satisfying each constraint. We define $h:G_{\varphi}\to H$ as
follows.

Fix $j\in\\{0,\ldots,L-1\\}$, and consider the or-gadget
$(F_{j},h^{\prime}_{j},R_{j})$. Recall that the set $P(c_{j^{\prime}})$
consists of all assignments of variables in $X_{j^{\prime}}$ that satisfy the
constraint $c_{j^{\prime}}$. Therefore, there exists an assignment
$f^{j^{\prime}}_{k}\in P(c_{j^{\prime}})$ such that
$\gamma|_{X_{j^{\prime}}}\equiv f^{j^{\prime}}_{k}$. Consider the vertex
$r^{j}_{k}$ that corresponds to that assignment. By the property 2 of the or-
gadget, we know that there exists a $H$-coloring of $F_{j}$ that extends
$h^{\prime}$, such that (i) $h_{1}(r^{j}_{k})=a$ and (ii) for every
$r^{j}_{k^{\prime}}\in R_{j},k^{\prime}\neq k$ we have that
$h_{1}(r^{j}_{k^{\prime}})\in\\{b,c\\}$.

Let $x_{i}\in X_{j^{\prime}}$ and let $y=f^{j^{\prime}}_{k}(x_{i})\in[B]$.
Since for each $d\in\lambda(y)$ there exists a vertex $z\in V^{j,k}_{i}$ such
that there is an $((a,d),w,w^{\prime})$-implication-gadget from $r^{j}_{k}$ to
$z$, the condition (i) implies that $h_{1}(V^{j,k}_{i})=\lambda(y)$. We color
the vertices of $V^{j,k}_{i}$ in a way that
$h(V^{j,k}_{i})=\lambda(y)\times\\{w\\}$.

Also, since for each $d\in S(\lambda(y))$ there exists a vertex $z\in
U^{j,k}_{i}$ such that there is an $(a,d)$-implication-gadget from $r^{j}_{k}$
to $z$, the condition (i) implies that $h_{1}(U^{j,k}_{i})=S(\lambda(y))$. We
color the vertices of $U^{j,k}_{i}$ in a way that
$h(U^{j,k}_{i})=S(\lambda(y))\times\\{w^{\prime}\\}$.

Because of (ii), the implication gadgets from $r_{k^{\prime}}$ to the vertices
of $V^{j,k^{\prime}}_{i}\cup U^{j,k^{\prime}}_{i}$ do not put any constraints
on the coloring of the sets $V^{j,k^{\prime}}_{i}$ and $U^{j,k^{\prime}}_{i}$.
Therefore, for each $v\in V^{j,k^{\prime}}_{i}$ we set $h(v)$ to be any vertex
from $\lambda(y)$. Similarly, for each $u\in U^{j,k^{\prime}}_{i}$ we set
$h(u)$ to be any vertex from $S(\lambda(y))$. Since $(b,z),(c,z)\in S_{a,d}$
for any $z\in V(H_{1})$ and $d\in\lambda(y)\cup S(\lambda(y))$, property 2
applied to the implication gadgets asserts that since
$h_{1}(r^{j}_{k^{\prime}})\in\\{b,c\\}$, we can always extend this mapping to
a homomorphism of the whole gadget to $H$.

It remains to argue that the edges between the sets $V^{j_{1},k_{1}}_{i}$ and
$U^{j_{2},k_{2}}_{i}$ are mapped to edges of $H$, for any $j_{1}<j_{2}$ and
$k_{1},k_{2}$. However, observe that since $\gamma$ is an extension of some
$f^{j^{\prime}_{1}}_{k_{1}}\in S_{j^{\prime}_{1}}$ and
$f^{j^{\prime}_{2}}_{k_{2}}\in S_{j^{\prime}_{2}}$, we must have
$f^{j^{\prime}_{1}}_{k_{1}}(x_{i})=f^{j^{\prime}_{2}}_{k_{2}}(x_{i})=y$.
Hence, $h$ maps every $v\in V^{j_{1},k_{1}}_{i}$ to some element of
$\lambda(y)\times\\{w\\}$, and every $u\in U^{j_{2},k_{2}}_{i}$ to some
element of $S(\lambda(y))\times\\{w^{\prime}\\}$. By Observation 2, and since
$ww^{\prime}\in E(W)$, we get that $h(v)h(u)\in E(H)$. That concludes the
proof of the claim.

######  Claim 2.

If there exists a homomorphism $h:G_{\varphi}\to H$ that extends $h^{\prime}$,
then $\varphi$ is a yes-instance of $q$-CSP-$B$.

######  Proof 5.11 (Proof of Claim).

We will define the assignment $\gamma:X\to[B]$ that makes every constraint
from $C$ satisfied.

Fix $j\in\\{0,\ldots,L-1\\}$, and consider the $p_{j^{\prime}}$-or-gadget
$(F_{j},h^{\prime}_{j},R_{j})$. By the property 1 of the or-gadget, there
exists $k_{j}\in[p_{j^{\prime}}]$ such that $h_{1}(r^{j}_{k_{j}})=a$.
Implication gadgets whose $p$-vertices were identified with $r^{j}_{k_{j}}$
assert that $h_{1}(V^{j,k_{j}}_{i})\in\mathcal{S}(H)$ and
$h_{1}(U^{j,k_{j}}_{i})$ is the signature of $h_{1}(V^{j,k_{j}}_{i})$. Then,
by Section 2, $h_{1}(V^{j,k_{j}}_{i})$ is a signature of
$h_{1}(U^{j,k_{j}}_{i})$. Denote $h_{1}(U^{j,k_{j}}_{i})$ by $T^{j}_{i}$, then
$h_{1}(V^{j,k_{j}}_{i})=S(T^{j}_{i})$ and $S(S(T^{j}_{i}))=T^{j}_{i}$. Let
$y^{j}_{i}=f^{j^{\prime}}_{k_{j}}(x_{i})$ be the _candidate assignment_ for
$x_{i}\in X_{j^{\prime}}$ at index $j$, recall that
$y^{j}_{i}=\lambda^{-1}(S(T^{j}_{i}))$. Let $i\in[n]$ be fixed and let
$j_{1},j_{2}\in[L],j_{1}<j_{2}$ be such that $x_{i}\in X_{j^{\prime}_{1}}\cap
X_{j^{\prime}_{2}}$. Observe that in such case $T^{j_{1}}_{i}\supseteq
T^{j_{2}}_{i}$. Indeed, denote $k_{1}=k_{j_{1}}$, $k_{2}=k_{j_{2}}$, then we
have (1) $h_{1}(V^{j_{1},k_{1}}_{i})=S(T^{j_{1}}_{i})\ \textrm{ and }\
h_{1}(U^{j_{1},k_{1}}_{i})=T^{j_{1}}_{i}$, and (2)
$h_{1}(V^{j_{2},k_{2}}_{i})=S(T^{j_{2}}_{i})\ \textrm{ and }\
h_{1}(U^{j_{2},k_{2}}_{i})=T^{j_{2}}_{i}$. Recall that each vertex from
$U^{j_{2},k_{2}}_{i}$ is adjacent to each vertex from $V^{j_{1},k_{1}}_{i}$.
Since $h_{1}$ is a homomorphism, the same holds for their images: each vertex
from $T^{j_{2}}_{i}$ is adjacent to each vertex from $S(T^{j_{1}}_{i})$. Then
$S(T^{j_{2}}_{i})\supseteq S(T^{j_{1}}_{i})$, so
$T^{j_{1}}_{i}=S(S(T^{j_{1}}_{i}))\supseteq S(S(T^{j_{2}}_{i}))\supseteq
T^{j_{2}}_{i}$. We say that the index $j_{1}\in\\{0,\ldots,L-1\\}$ is
_problematic_ for $i$ if there is $j_{2}>j_{1}$ such that $x_{i}\in
X_{j_{1}^{\prime}}\cap X_{j_{2}^{\prime}}$ and $T^{j_{1}}_{i}\neq
T^{j_{2}}_{i}$. Since for each variable we have at most $|H_{1}|$ problematic
indices, there are at most $|H_{1}|\cdot n$ problematic indices for all
variables. Since $L=m(|H_{i}|\cdot n+1)$, by pigeonhole principle we get that
there exists a set $J\subseteq\\{0,\ldots,L-1\\}$ of $m$ consecutive indices
such that none of them is problematic for any $i$. For every $i\in[n]$, we fix
some $j\in J$ such that $x_{i}\in X_{j^{\prime}}$ and set
$\gamma(x_{i})=y^{j}_{i}$ (observe that the choice of $j$ does not matter). We
claim that $\gamma$ is an assignment that satisfies every constraint from
$\varphi$. Indeed, for any $j^{\prime}\in[m]$ there exists $j\in J$ such that
$j^{\prime}=j\mod m$. For every $i\in X_{j^{\prime}}$, we have
$\gamma(x_{i})=y^{j}_{i}=f_{k_{j}}^{j^{\prime}}(x_{i})$, so $\gamma$ satisfies
the constraint $c_{j^{\prime}}$.

Finally, it remains to adapt the arguments of Lampis [20] to establish the
desired linear clique-width bound.

######  Claim 3.

$G_{\varphi}$ can be constructed in time polynomial in $|\varphi|$, and we
have ${\operatorname{cw}(G_{\varphi})}\leqslant n+f(\varepsilon,\nu)$ for some
function $f$, where $\nu=|V(H)|$.

######  Proof 5.12 (Proof of Claim).

Observe that any $(S,w,w^{\prime})$-gadget constructed as in Lemma 5.4 for
$i=1$ has at most $|V(H_{i})|^{|S|-1}\cdot|V(H)|\leqslant\nu^{|S|}$ vertices.
In particular, we can ensure that every implication gadget in $G_{\varphi}$
has at most $\nu^{\mathcal{O}(\nu^{2})}$ vertices. Moreover, we will assume
that all the or-gadgets of $G_{\varphi}$ are constructed as in Lemma 5.6 and
the subgadgets for $S$, $S_{\text{left}}$ and $S_{\text{right}}$ contain at
most $\nu^{7}$ vertices. Then for every $j\in\\{0,\ldots,L-1\\}$,
$p_{j^{\prime}}$-or-gadget $(F_{j},h^{\prime}_{j},R_{j})$ has at most
$(p_{j^{\prime}}-1)\cdot\nu^{7}$ vertices. For fixed $H$ and $\varepsilon>0$
we have that $B=s(H_{i})\leqslant 2^{|V(H_{i})|}-2$ and $q$ is a constant that
only depends on $B$, $\varepsilon$ (that is, on $|V(H_{i})|$, $\varepsilon$).
Each constraint of the $q$-CSP-$B$ instance has at most $B^{q}$ satisfying
assignments. In particular, the number of vertices in each or-gadget is upper-
bounded by $B^{q}\cdot\nu^{7}$. Therefore, it is not hard to see that the
whole construction can be performed in polynomial time, if $H$ is fixed and
$\varepsilon$ is a constant. For clique-width we use the following labels:

  1. 1.

$n$ _main_ labels, representing the variables of $\varphi$.

  2. 2.

A single _done_ label. Its informal meaning is that a vertex that receives
this label will not be connected to anything else not yet introduced in the
graph.

  3. 3.

$B^{q}\cdot\nu^{7}$ _constraint work_ labels.

  4. 4.

$qB^{q}\cdot\nu^{\mathcal{O}(\nu^{2})}$ _variable-constraint incidence work_
labels.

To give a clique-width expression we will describe how to build the graph,
following essentially the steps given in the description of the construction
by maintaining the following invariant: before starting iteration $j$, all
vertices of the set
$W^{j}_{i}=\bigcup_{j^{\prime}<j}\bigcup_{k\in[p_{j^{\prime}}]}V^{j^{\prime},k}_{i}$
have label $i$, and all other vertices have the _done_ label. This invariant
is vacuously satisfied before the first iteration, since the graph is empty.
Suppose that for some $j\in\\{0,\ldots,L-1\\}$ the invariant is true. We use
the $B^{q}\cdot\nu^{7}$ constraint work labels to introduce the vertices of
the $p_{j^{\prime}}$-or-gadget $(F_{j},h^{\prime}_{j},R_{j})$, giving each
vertex a distinct label. We use join operations to construct the internal
edges of the or-gadget. Then, for each variable $x_{i}$ that appears in the
current constraint we do the following: we use
$B^{q}\cdot\nu^{\mathcal{O}(\nu^{2})}$ of the variable-constraint incidence
work labels to introduce for all $k\in[p_{j^{\prime}}]$ the vertices of
$V_{i}^{j,k}$ and $U_{i}^{j,k}$ as well as the implication gadgets connecting
these to $r^{j}_{k}$ . Again we use a distinct label for each vertex, but the
number of vertices (including internal vertices of the implication gadgets) is
$B^{q}\cdot\nu^{\mathcal{O}(\nu^{2})}$, so we have sufficiently many labels to
use distinct labels for each of the $q$ variables of the constraint. We use
join operations to add the edges inside all implication gadgets. Then we use
join operations to connect $U_{i}^{j,k}$ to all vertices $W^{j}_{i}$. This is
possible, since the invariant states that all the vertices of $W^{j}_{i}$ have
the same label $i$. We then rename all the vertices of $U_{i}^{j,k}$ for all
$k$ to the done label, and do the same also for internal vertices of all
implication gadgets. We proceed to the next variable of the same constraint
and handle it using its own $B^{q}\cdot\nu^{\mathcal{O}(\nu^{2})}$ labels.
Once we have handled all variables of the current constraint, we rename all
vertices of each $V_{i}^{j,k}$ to label $i$ for all $k$. We then rename all
vertices of the $p_{j^{\prime}}$-or-gadget $(F_{j},h^{\prime}_{j},R_{j})$
gadget to the done label and increase $j$ by 1. It is not hard to see that we
have maintained the invariant and constructed all edges induced by the
vertices introduced in steps up to $j$, so repeating this process constructs
the graph.

Together the claims imply Theorem 5.3 in the following way: For an arbitrary
instance of $q$-CSP-$B$, our construction produces an instance of HomExt($H$),
and the instances are equivalent by 1 and 2. If one could solve HomExt($H$) in
$\mathcal{O^{*}}((s(H_{i})-\varepsilon)^{{\operatorname{cw}(G)}})$ for some
$\varepsilon>0$, one could use our construction to solve $q$-CSP-$B$, and by
our choice of $B$ and 3 this procedure would have complexity
$\mathcal{O^{*}}((B-\varepsilon)^{n+c})$ for some constant $c$. By our choice
of $q$ according to Theorem 5.8, this contradicts the SETH.

##  6 Summary and Concluding Remarks

Extensions and Corollaries. We observe that Corollary 4.4 can be combined with
Theorem 1.2 to obtain the following statement, which summarizes our results.

######  Theorem 6.1.

Let $H^{\prime}$ be a fixed graph with the non-trivial connected core $H$. Let
$H_{1}\times\ldots\times H_{m}$ be the factorization of $H$. Let $i\in[m]$ be
such that $s(H_{i})=\max_{j\in[m]}s(H_{j})$. Let $G$ be an instance of
Hom($H^{\prime}$).

  1. 1.

Assuming a clique-width expression $\sigma$ of $G$ of width
${\operatorname{cw}(G)}$ is given, the Hom($H^{\prime}$) problem can be solved
in time $\max_{i\in[m]}\mathcal{O}^{*}(s(H_{i})^{{\operatorname{cw}(G)}})$.

  2. 2.

Assuming SETH, if $H$ is $H_{i}$-projective, then there is no algorithm to
solve Hom($H^{\prime}$) in time
$\max_{i\in[m]}\mathcal{O}^{*}((s(H_{i})-\varepsilon)^{{\operatorname{cw}(G)}})$
for any $\varepsilon>0$.

We note that the restriction to connected targets can be avoided by known
properties of homomorphisms to disconnected graphs [25]; on the algorithmic
side, one branches over all connected components of $H$, while for the lower
bound one considers the component with maximum signature number.

It is clear that obtaining a full complexity classification with respect to
clique-width may require weakening the assumption in the second statement of
Theorem 6.1. We recall that an analogous situation occurs in the work of
Okrasa and Rzążewski [25]; as mentioned in the introduction, the authors
obtain the SETH-conditioned tight complexity bound for the Hom($H$) problem
parameterized by treewidth for all targets $H$, assuming two conjectures of
Larose and Tardif [22, 21]. The notion of $H_{i}$-projectivity allows us to
restate these conjectures as one, which is not only sufficient in our setting
but is also weaker in the sense of it being implied by the former two
conjectures, but not necessarily equivalent to them.

######  Conjecture 1.

Let $H$ be a non-trivial core with prime factorization
$H_{1}\times\ldots\times H_{m}$ and let $i\in[m]$. Then $H$ is
$H_{i}$-projective.

Using 1, we can restate our main result as follows.

######  Theorem 6.2.

Let $H^{\prime}$ be a fixed graph with the non-trivial connected core $H$. Let
$H_{1}\times\ldots\times H_{m}$ be the prime factorization of $H$. Let $G$ be
an instance of Hom($H^{\prime}$).

  1. 1.

Assuming the clique-width expression $\sigma$ of $G$ of width
${\operatorname{cw}(G)}$ is given, the Hom($H^{\prime}$) problem can be solved
in time $\max_{i\in[m]}\mathcal{O}^{*}(s(H_{i})^{{\operatorname{cw}(G)}})$.

  2. 2.

Assuming that 1 and SETH hold, there is no algorithm to solve
Hom($H^{\prime}$) in time
$\max_{i\in[m]}\mathcal{O}^{*}((s(H_{i})-\varepsilon)^{{\operatorname{cw}(G)}})$
for any $\varepsilon>0$.

We also observe that since each non-trivial projective core $H$ is
$H$-projective, in this case we already obtain a tight complexity bound.

######  Corollary 6.3.

Let $H^{\prime}$ be a fixed graph with the non-trivial connected projective
core $H$. Let $G$ be an instance of Hom($H^{\prime}$).

  1. 1.

Assuming the clique-width expression $\sigma$ of $G$ of width
${\operatorname{cw}(G)}$ is given, the Hom($H^{\prime}$) problem can be solved
in time $\mathcal{O}^{*}(s(H)^{{\operatorname{cw}(G)}})$.

  2. 2.

There is no algorithm to solve Hom($H^{\prime}$) in time
$\mathcal{O}^{*}((s(H)-\varepsilon)^{{\operatorname{cw}(G)}})$ for any
$\varepsilon>0$, unless the SETH fails.

Generalizations and Other Research Directions. We remark that our hardness
reduction is via HomExt($H$), and in fact our algorithm can also easily be
adapted to this setting (by removing all records that do not adhere to the
partial mapping from the input graph to $H$) without an increase in
complexity. However, since the dichotomy between P and NP-complete cases of
HomExt($H$) is more complicated (see [11], studied as the graph-retract
problem) there exist target graphs $H$ that are not covered by Theorem 6.2. On
a similar note, let us also point out that setting up the SETH-conditioned
tight complexity bounds for clique-width for a more general list problem
LHom($H$) [10, 27] is widely open.

Another direction that is very closely related to our results is to determine
similarly tight complexity bounds for the _rank-width_ ($\operatorname{rw}$)
of the input graph: rank-width [17, 26] is a graph parameter that is known to
be asymptotically equivalent to clique-width and is in fact used as an
approximation of clique-width that can be computed in fixed-parameter
tractable time. Our results together with the known relationship between
clique-width and rank-width imply an upper bound of
$\mathcal{O}^{*}(s(H)^{2^{\operatorname{rw}+1}})$ and a SETH lower bound of
$(s(H)-\varepsilon)^{\operatorname{rw}}$ on the complexity of Hom($H$) for
projective $H$ parameterized by the rank-width of the input.

## References

  * [1] Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi.  Grundy distinguishes treewidth from pathwidth.  In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 14:1–14:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [2] Jan Böker.  Graph similarity and homomorphism densities.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 32:1–32:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [3] Andrei A. Bulatov and Amineh Dadsetan.  Counting homomorphisms in plain exponential time.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 21:1–21:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [4] Bruno Courcelle, Johann A. Makowsky, and Udi Rotics.  Linear time solvable optimization problems on graphs of bounded clique-width.  Theory Comput. Syst., 33(2):125–150, 2000.
  * [5] Bruno Courcelle and Stephan Olariu.  Upper bounds to the clique width of graphs.  Discrete Applied Mathematics, 101(1-3):77–114, 2000.
  * [6] Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socała.  Tight lower bounds on graph embedding problems.  J. ACM, 64(3):18:1–18:22, 2017.  doi:10.1145/3051094.
  * [7] Reinhard Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * [8] Willibald Dörfler.  Primfaktorzerlegung und Automorphismen des Kardinalproduktes von Graphen.  Glasnik Matematički, 9:15–27, 1974.
  * [9] László Egri, Dániel Marx, and Paweł Rzążewski.  Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization.  In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pages 27:1–27:15, 2018\.
  * [10] Tomás Feder, Pavol Hell, and Jing Huang.  Bi-arc graphs and the complexity of list homomorphisms.  J. Graph Theory, 42(1):61–80, 2003.  doi:10.1002/jgt.10073.
  * [11] Tomás Feder and Moshe Y. Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory.  SIAM J. Comput., 28(1):57–104, 1998.  doi:10.1137/S0097539794266766.
  * [12] Fedor V. Fomin, Pinar Heggernes, and Dieter Kratsch.  Exact algorithms for graph homomorphisms.  Theory Comput. Syst., 41(2):381–393, 2007.  doi:10.1007/s00224-007-2007-x.
  * [13] Martin Grohe.  The complexity of homomorphism and constraint satisfaction problems seen from the other side.  J. ACM, 54(1):1:1–1:24, 2007.
  * [14] Richard H. Hammack, Wilfried Imrich, and Sandi Klavžar.  Handbook of product graphs.  CRC press, 2011.
  * [15] Pavol Hell and Jaroslav Nešetřil.  On the complexity of $H$-coloring.  J. Comb. Theory, Ser. B, 48(1):92–110, 1990.  doi:10.1016/0095-8956(90)90132-J.
  * [16] Pavol Hell and Jaroslav Nešetřil.  The core of a graph.  Discret. Math., 109(1-3):117–126, 1992.
  * [17] Sang il Oum and Paul Seymour.  Approximating clique-width and branch-width.  Journal of Combinatorial Theory, Series B, 96(4):514–528, 2006\.  URL: https://www.sciencedirect.com/science/article/pii/S0095895605001528, doi:https://doi.org/10.1016/j.jctb.2005.10.006.
  * [18] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-sat.  J. Comput. Syst. Sci., 62(2):367–375, 2001.
  * [19] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  J. Comput. Syst. Sci., 63(4):512–530, 2001.  URL: http://dx.doi.org/10.1006/jcss.2001.1774, doi:10.1006/jcss.2001.1774.
  * [20] Michael Lampis.  Finer tight bounds for coloring on clique-width.  SIAM J. Discret. Math., 34(3):1538–1558, 2020.  doi:10.1137/19M1280326.
  * [21] Benoît Larose.  Families of strongly projective graphs.  Discuss. Math. Graph Theory, 22(2):271–292, 2002.  doi:10.7151/dmgt.1175.
  * [22] Benoît Larose and Claude Tardif.  Strongly rigid graphs and projectivity.  Multiple-Valued Logic, 7:339–361, 2001.
  * [23] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.  Lower bounds based on the exponential time hypothesis.  Bull. EATCS, 105:41–72, 2011.
  * [24] Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski.  Full complexity classification of the list homomorphism problem for bounded-treewidth graphs.  In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 74:1–74:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.ESA.2020.74.
  * [25] Karolina Okrasa and Paweł Rzążewski.  Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs.  SIAM J. Comput., 50(2):487–508, 2021.
  * [26] Sang-il Oum.  Approximating rank-width and clique-width quickly.  In Dieter Kratsch, editor, Graph-Theoretic Concepts in Computer Science, pages 49–58, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [27] Marta Piecyk and Paweł Rzążewski.  Fine-grained complexity of the list homomorphism problem: Feedback vertex set and cutwidth.  In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 56:1–56:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [28] Neil Robertson and Paul D. Seymour.  Graph minors. II. algorithmic aspects of tree-width.  J. Algorithms, 7(3):309–322, 1986.
  * [29] Paweł Rzążewski.  Exact algorithm for graph homomorphism and locally injective graph homomorphism.  Inf. Process. Lett., 114(7):387–391, 2014.
  * [30] Magnus Wahlström.  New plain-exponential time classes for graph homomorphism.  Theory Comput. Syst., 49(2):273–282, 2011.  doi:10.1007/s00224-010-9261-z.
  * [31] Tomasz Łuczak and Jaroslav Nešetřil.  Note on projective graphs.  J. Graph Theory, 47(2):81–86, 2004.