# Generalisations of Matrix Partitions : Complexity and Obstructions

Alexey Barsukov  Université Clermont Auvergne, LIMOS, CNRS, Aubière, France
<EMAIL_ADDRESS>and  Mamadou Moustapha Kanté  Université Clermont
Auvergne, LIMOS, CNRS, Aubière, France<EMAIL_ADDRESS>
###### Abstract.

A _trigraph_ is a graph where each pair of vertices is labelled either $0$ (a
non-edge), $1$ (an edge) or $\star$ (both an edge and a non-edge). In a series
of papers, Hell and co-authors (see for instance [Pavol Hell: Graph partitions
with prescribed patterns. Eur. J. Comb. 35: 335-353 (2014)]) proposed to study
the complexity of homomorphisms from graphs to trigraphs, called _Matrix
Partition Problems_ , where edges and non-edges can be both mapped to
$\star$-edges, while a non-edge cannot be mapped to an edge, and vice-versa.
Even though, Matrix Partition Problems are generalisations of _Constraint
Satisfaction Problems ( CSPs)_, they share with them the property of being
”intrinsically” combinatorial. So, the question of a possible dichotomy, i.e.
P-time vs NP-complete, is a very natural one and raised in Hell et al.’s
papers. We propose in this paper to study Matrix Partition Problems on
relational structures, wrt a dichotomy question, and, in particular,
homomorphisms between trigraphs. We first show that trigraph homomorphisms and
Matrix Partition Problems are P-time equivalent, and then prove that one can
also restrict (wrt dichotomy) to relational structures with one relation.
Failing in proving that Matrix Partition Problems on directed graphs are not
P-time equivalent to Matrix Partitions on relational structures, we give some
evidence that it is unlikely by showing that reductions used in the case of
CSPs cannot work. We turn then our attention to Matrix Partitions with finite
sets of obstructions. We show that, for a fixed trigraph $\mathbf{H}$, the set
of inclusion-wise minimal obstructions, which prevent to have a homomorphism
to $\mathbf{H}$, is finite for directed graphs if and only if it is finite for
trigraphs. We also prove similar results for relational structures. We
conclude by showing that on trees (seen as trigraphs) it is NP-complete to
decide whether a given tree has a trigraph homomorphism to another input
trigraph. The latter shows a notable difference on tractability between CSP
and Matrix Partition as it is well-known that CSP is tractable on the class of
trees.

###### Key words and phrases:

Matrix Partition, csp, dichotomy theorem, complexity

###### 1991 Mathematics Subject Classification:

68Q15, 68Q17,05B20

##  1\. Introduction

Ladner showed in [27] that, under the assumption $\textrm{P}\not=\textrm{NP}$,
there exist problems that are neither in P nor NP-complete. This raises the
question of knowing which subclasses of NP admit a dichotomy between P and NP-
complete, that is subclasses where every problem is either in P or is NP-
complete. For instance, Schaefer proved in his seminal paper [30] that any SAT
problem is either in P or is NP-complete, and Hell and Nešetřil [22] showed a
similar dichotomy for homomorphism problems on undirected graphs. The
_Constraint Satisfaction Problems_ (CSPs for short) form a large and well-
known class of problems that are usually described (see [23]) as decision
problems that check the existence of a homomorphism between two given
relational structures. Since, general CSPs are generalisations of both SAT
problems and homomorphism problems on undirected graphs, people wonder whether
a dichotomy can hold for general CSPs. Indeed, Feder and Vardi explicitly
asked for such a result in [18], known as the _CSP conjecture_, and showed in
the same paper many P-time equivalences111We refer to Section 2 for
definitions, but roughly two problems are _P -time equivalent_ if one can
reduce in P-time one to the other, and vice-versa. Notice that if two families
of problems are P-time equivalent, then one admits a dichotomy if and only if
the other does., in particular, a P-time equivalence of CSP with the directed
graph homomorphism and with the logical language $\mathsf{MMSNP}$. For around
two decades, the CSP conjecture has been verified for many special cases, see
for instance [7, 18, 20], but, more importantly, its study brings many
mathematical tools in studying algorithmic and complexity questions, in
particular, the algebraic tools [9]. Recently, Bulatov [8] and Zhuk [33]
independently answered in the affirmative the CSP conjecture.

Motivated by the CSP conjecture, many homomorphism type problems have been
introduced and studied under the realm of a dichotomy, e.g., _full
homomorphism_ [3], _locally injective/surjective homomorphism_ [28, 5], _list
homomorphism_ [25], _quantified CSP_ [34], _infinite CSP_ [6], _VCSP_ [26],
etc. In this paper, we are interested in the _Matrix Partition_ Problem
introduced in [15] which finds its origin in combinatorics as other variants
of the CSP conjecture, e.g., list or surjective homomorphism. A _trigraph_ is
a pair $\mathbf{G}=(G,E^{\mathbf{G}})$ where $E^{\mathbf{G}}\colon
G^{2}\to\\{0,1,\star\\}$. A _homomorphism_ between two trigraphs $\mathbf{G}$
and $\mathbf{H}$ is a mapping $h\colon G\to H$ such that for all $(x,y)\in
G^{2}$, $E^{\mathbf{H}}(h(x),h(y))\in\\{E^{\mathbf{G}}(x,y),\star\\}$. As any
graph is a trigraph, Hell et al. ([15, 17, 21]) proposed a way to consider
combinatorial problems on graphs as trigraph homomorphism problems, and called
them _Matrix Partition Problems_ 222The term _Matrix Partition Problem_ is a
natural one because any trigraph can be represented by a matrix where each
entry is in $\\{0,1,\star\\}$, and a trigraph homomorphism is a partition
problem where the edges between two parts $V_{i}$ and $V_{j}$ are controlled
by the entry of the matrix on $(i,j)$.. Particularly, any CSP problem on
(directed) graphs can be represented as a Matrix Partition Problem, thus the
latter is a generalisation of the class CSP. Motivated by the CSP conjecture,
and the similarity of Matrix Partition Problem with CSP, Hell et al. [17, 21]
asks whether Matrix Partition Problems may satisfy the same dichotomy as CSP.

Motivated by the P-time equivalence between general CSP and CSP on directed
graphs [18], we investigate a similar question for Matrix Partition Problems.
But, contrary to CSP, there are several ways to generalise Matrix Partition
Problems on relational structures. We first propose to generalise the
definition of trigraphs to relational structures, where a tuple can be now
labelled $\star$, and as in the trigraph homomorphism, a tuple labeled $0$ can
be only mapped to tuples labelled $0$ or $\star$, similarly for $1$-labelled
tuples that can be mapped to $1$ or $\star$-labelled tuples, and a tuple
labelled $\star$ can be only mapped to tuples labelled $\star$. Another
generalisation of Matrix Partition Problem concerns the inputs. While in Hell
et al.’s definition of the problem the inputs are graphs, we propose to
consider instead trigraphs as inputs, for their definition see [24]. We denote
such new problems by $\textrm{MP}_{\star}(\mathbf{H})$, and the original ones
by $\textrm{MP}(\mathbf{H})$ where $\mathbf{H}$ is the target structure of the
problem. As in the CSP case, we wonder whether this generalisation is P-time
equivalent to trigraph homomorphism. We prove that $\textrm{MP}_{\star}$ and
MP are P-time equivalent. Hell and Nešetřil in [24] provided a probabilistic
proof of this equivalence. In this paper we make it determenistic. In doing
so, we replace any $\star$-labelled tuple by a large enough _Hadamard matrix_
[19]. Hadamard matrices are matrices over $\\{1,-1\\}$ with the property that
any large submatrix is not monochromatic. This property of Hadamard matrices
and the pigeonhole principle allow us to show the P-time equivalence (see
Section 3).

Feder and Vardi in [18] showed that a CSP over a finite signature is P-time
equivalent to a CSP on directed graphs. Bulin et al. in [10] gave a more
detailed proof of this fact and showed that all the reductions are log-space.
In Section 5, we raise similar questions about Matrix Partition Problems.
Using the result achieved in Section 4, we show that any problem in MP over
any finite signature is P-time equivalent to a problem in MP on relational
structures with one single relation.

We then turn our attention to the P-time equivalence between MP on relational
structures with a single relation to MP on directed graphs. While we think
that, contrary to the CSP case, MP on relational structures is richer than MP
on directed graphs, we fail to prove it. Instead, we analyse the type of
reductions used in the CSP case and show that it is unlikely that such
reductions work for MP, unless MP is P-time equivalent to CSP. In order to
show this, we introduce another generalisation of Matrix Partition Problems,
denoted by $\textrm{MP}_{\varnothing}$. We first encode any problem in MP by a
CSP problem by identifying for each tuple whether it is labelled $1$ or $0$
(we introduce for each relation $R$ two relations $R_{0}$, for $0$-labelled
tuples, and $R_{1}$ for $1$-labelled tuples). Therefore, any MP problem is a
CSP problem, but restricted to ”complete structures”, i.e. any tuple should be
in either $R_{0}$ or in $R_{1}$. When we relax this completeness property, we
obtain the class of problems $\textrm{MP}_{\varnothing}$, where we introduce a
new value for tuples, namely $\varnothing$, which can be mapped to any value
among $\\{0,1,\star\\}$. Firstly, we show in Section 3 that
$\textrm{MP}_{\varnothing}$ is P-time equivalent to CSP, and that the
correspondence is a bijection between the classes of problems. We later use
this correspondence to show in Section 5 that any reduction similar to the one
of Bulin et al. cannot prove the P-time equivalence between MP over any finite
signature and MP on directed graphs, unless MP is P-time equivalent to CSP.

A natural way to prove that a problem is in P is to show that it is described
by a finite set of obstructions. In the case of CSP, $\mathcal{F}$ is called a
_duality set_ for an instance $\textrm{CSP}(\mathbf{H})$ if for any structure
$\mathbf{G}$, $\mathbf{G}$ does not homomorphically map to $\mathbf{H}$ if and
only if there is $\mathbf{F}\in\mathcal{F}$ such that $\mathbf{F}$
homomorphically maps to $\mathbf{G}$. It is known that
$\textrm{CSP}(\mathbf{H})$ has a finite set of obstructions if and only if it
is definable by a _first-order formula_ [2]. Feder, Hell and Xie proposed in
[17] to study Matrix Partition Problems with finite sets of (inclusion-wise
minimal) obstructions, that is a graph admits a partition if and only if it
does not have an induced subgraph that belongs to a finite family
$\mathcal{F}$ of forbidden graphs. They proposed a necessary (but not
sufficient) condition for a matrix $\mathsf{M}$ to have finitely many
obstructions, and Feder, Hell and Shklarsky later showed in [16] that any
Matrix Partition Problem has finitely many obstructions if the input consists
only of split graphs. In Section 6, we show that a Matrix Partition Problem
has finitely many inclusion-wise minimal obstructions if and only if there are
finitely many of them for the $\textrm{MP}_{\star}$ case. We also consider
duality sets for Matrix Partition Problems. We show that the following are
equivalent for a trigraph $\mathbf{H}$ (it holds also for relational
structures):

  1. (1)

$\textrm{MP}(\mathbf{H})$ has a finite duality set.

  2. (2)

$\textrm{MP}(\mathbf{H})$ has a finite set of inclusion-wise minimal
obstructions.

  3. (3)

$\textrm{MP}_{\star}(\mathbf{H})$ has a finite duality set.

  4. (4)

$\textrm{MP}_{\star}(\mathbf{H})$ has a finite set of inclusion-wise minimal
obstructions.

Apart from it, we study how the finiteness of obstruction sets for the CSPs is
related to the finiteness for trigraphs. We demonstrate that if
$\textrm{MP}_{\varnothing}(\mathbf{H})$ (that corresponds to a CSP, see
Section 3) has a finite set of obstructions, then $\textrm{MP}(\mathbf{H})$
has also a finite set of obstructions. We show that the other direction is
false by giving an example of a $\star$-graph $\mathbf{H}$ such that
$\textrm{MP}_{\star}(\mathbf{H})$ has finitely many obstructions and
$\textrm{MP}_{\varnothing}(\mathbf{H})$ has an infinite set of obstructions.

We finally consider tractability questions. It is proven in [20] for the case
of CSP that, once the input is restricted onto the family $\mathcal{C}$ of
relational structures that are cores, any CSP with input from $\mathcal{C}$ is
solvable in P-time if and only if all the structures from $\mathcal{C}$ have
bounded tree-width. We show that the similar problem is NP-complete for the
case of Matrix Partitions, even when $\mathcal{C}$ consists only of trees, by
reducing $3$-SAT to it.

Outline. After giving all the necessary definitions in Section 2, we show in
Section 3 that $\textrm{MP}_{\varnothing}$ and CSP are P-time equivalent.
P-time equivalence of MP and $\textrm{MP}_{\star}$ is shown in Section 4. In
Section 5 we explain how a dichotomy for MP over one-relational signatures
implies a dichotomy for MP over any signatures, and we also argue about a
possible equivalence between MP on directed graphs and MP over any signatures.
Section 6 covers the finiteness for the obstruction sets. We discuss with some
remarks in Section 7, the potential utility of tree-width for the MP problems.

##  2\. Preliminaries

We denote by $\mathbb{N}$ the set of positive integers (including $0$), and
for $n\in\mathbb{N}$, we let $[n]$ be $\\{1,\ldots,n\\}$. The power set of a
set $V$ is denoted by $2^{V}$, and its size by $|V|$. For a finite set $V$ and
a positive integer $k$, tuples in $V^{k}$ are often represented by boldface
lower case letters (e.g., $\mathbf{t}$), and the $i$-th coordinate of a tuple
$\mathbf{t}$ is denoted by $t_{i}$; if $f:V\to A$ is a mapping from $V$ to a
set $A$, we denote by $f(\mathbf{t})$ the tuple $(f(t_{1}),\ldots,f(t_{k}))$,
and by $f(X)$, for $X\subseteq A$, the set $\\{f(x)\mid x\in X\\}$.

Our graph terminology is standard, see for instance [12]. In this paper, we
deal mostly with labelled complete relational structures, i.e. each relation
of arity $k$ is $V^{k}$, and tuples are labelled by the elements of a
partially ordered set, defined for example in [31].

######  Definition 2.1 ($({*},\sigma)$-structures).

A _signature_ $\sigma$ is a set $\\{R_{1},\ldots,R_{n}\\}$, each $R_{i}$ has
arity $k_{i}\in\mathbb{N},\ i\in[n]$.

Let $(P_{*},\preceq_{*})$ be a partially ordered set (poset). A
_$({*},\sigma)$ -structure_ is a tuple
$\mathbf{G}:=(G;R_{1}^{\mathbf{G}},\ldots,R_{n}^{\mathbf{G}})$ with $G$ a
finite set, and for each $i\in[n]$, $R_{i}^{\mathbf{G}}\colon G^{k_{i}}\to
P_{*}$ is interpreted as a mapping to the elements of the poset.

We will always denote a $({*},\sigma)$-structure by a boldface capital letter,
e.g. $\mathbf{A}$, and its domain by the same letter in plain font, e.g. $A$.
It is worth mentioning that the notion of $({*},\sigma)$-structure is
different from the one in _universal algebra_ , where in the latter case the
functional symbol $R_{i}$ is interpreted in $\mathbf{G}$ as a function from
$G^{k_{i}}\to G$.

For a $({*},\sigma)$-structure $\mathbf{G}$ and $X\subseteq G$, the
substructure of $\mathbf{G}$ induced by $X$ is the $({*},\sigma)$-structure
$\mathbf{G^{\prime}}$ with domain $G^{\prime}=X$ and, for $R\in\sigma$ of
arity $k$ and $\mathbf{t}\in X^{k}$,
$R^{\mathbf{G^{\prime}}}(\mathbf{t})=R^{\mathbf{G}}(\mathbf{t})$; and we
denote by $\mathbf{G}\setminus X$ the substructure of $\mathbf{G}$ induced by
$G\setminus X$.

We now extend the notion of homomorphism between relational structures to
$({*},\sigma)$-structures, the difference being the ability to map a tuple to
a ”greater” one.

######  Definition 2.2 (homomorphism for $({*},\sigma)$-structures).

For two $({*},\sigma)$-structures $\mathbf{G}$ and $\mathbf{H}$, a mapping
$h\colon G\to H$ is called a _homomorphism from $\mathbf{G}$ to $\mathbf{H}$_
if, for each $R\in\sigma$ of arity $k$, and $\mathbf{t}\in G^{k}$,
$R^{\mathbf{G}}(\mathbf{t})\preceq_{*}R^{\mathbf{H}}(h(\mathbf{t}))$.

As usual, we will write $h\colon\mathbf{G}\to\mathbf{H}$ to mean that $h\colon
G\to H$ is a homomorphism from $\mathbf{G}$ to $\mathbf{H}$. We say that
$h:\mathbf{G}\to\mathbf{H}$ is _surjective_ (resp. _injective_) if $h:G\to H$
is surjective (resp. injective).

We can now explain how the notion of homomorphism between
$({*},\sigma)$-structures subsumes the usual ones. Before, let us recall the
partial orders we consider in this paper.

  * •

$(P_{01},\preceq_{01})$, where $P_{01}=\\{0,1\\}$ and $\preceq_{01}$ is the
empty order with $0$ and $1$ incomparable.

  * •

$(P_{\textrm{CSP}},\preceq_{\textrm{CSP}})$, where
$P_{\textrm{CSP}}=\\{0,1\\}$ and $\preceq_{\textrm{CSP}}$ is a total order
with $0\preceq_{\textrm{CSP}}1$.

  * •

$(P_{\star},\preceq_{\star})$, where $P_{\star}=\\{0,1,\star\\}$ and
$\preceq_{\star}$ is the poset with $0\preceq_{\star}\star$ and
$1\preceq_{\star}\star$, and $0$ incomparable with $1$.

  * •

$(P_{\varnothing},\preceq_{\varnothing})$ where
$P_{\varnothing}=\\{\varnothing,0,1,\star\\}$ and $\preceq_{\varnothing}$ is
the poset with $\varnothing\preceq_{\varnothing}0\preceq_{\varnothing}\star$
and $\varnothing\preceq_{\varnothing}1\preceq_{\varnothing}\star$, and $0$
incomparable with $1$.

######  Remark 2.3.

If the signature $\sigma$ is clear from the context, then we will just write
_$*$ -structure_ instead of $({*},\sigma)$-structure, for
$*\in\\{01,\star,\varnothing\\}$. Also, if $\sigma=\\{E(\cdot,\cdot)\\}$, then
we will write _$*$ -graph_ instead. Finally, we will talk about _relational
$\sigma$-structures_ and _directed graphs_ , instead of
$({\textrm{CSP}},\sigma)$-structures and CSP-graphs. Furthermore, for any
tuple (edge) $\mathbf{t}\in A^{k}$ of a $*$-structure ($*$-graph) $\mathbf{A}$
corresponding to a symbol $R\in\sigma$ that is clear from the context, we will
call $\mathbf{t}$ a _$p$ -tuple ($p$-edge)_ if $R^{\mathbf{A}}(\mathbf{t})=p$
for some element $p$ of the poset $(P_{*},\preceq_{*})$.

It is not hard to check that $({\textrm{CSP}},\sigma)$-structures correspond
exactly to the usual notion of relational $\sigma$-structures, and
homomorphisms between $({\textrm{CSP}},\sigma)$-structures to usual
homomorphisms. Notice that homomorphisms between $({01},\sigma)$-structures
are exactly full homomorphisms on relational structures.

######  Proposition 2.4.

Let $(P_{*},\preceq_{*})$ and $(P_{*^{\prime}},\preceq_{*^{\prime}})$ be two
posets, with $(P_{*},\preceq_{*})$ a sub-poset of
$(P_{*^{\prime}},\preceq_{*^{\prime}})$. Then every $({*},\sigma)$-structure
is also a $({*^{\prime}},\sigma)$-structure, for any $\sigma$.

Particularly, for any $\sigma$, every $({{01}},\sigma)$-structure is a
$({\star},\sigma)$-structure, and every $({\star},\sigma)$-structure is a
$({\varnothing},\sigma)$-structure. For $*\in\\{01,\star,\varnothing\\}$, we
denote by $\textrm{Cat}_{*}$ the set of all $({*},\sigma)$-structures333We use
the notation $\textrm{Cat}_{*}$ because one can use $({*},\sigma)$-structures
as objects and homomorphisms as arrows to make a category.. From the
proposition above, and the definitions of
$(P_{01},\preceq_{01}),(P_{\star},\preceq_{\star})$ and
$(P_{\varnothing},\preceq_{\varnothing})$, we have the following inclusion:

$\displaystyle\textrm{Cat}_{01}^{\sigma}\subset\textrm{Cat}_{\star}^{\sigma}\subset\textrm{Cat}_{\varnothing}^{\sigma}.$

We can now define the homomorphism problems, that we restrict for conciseness
to the four posets:
$(P_{01},\preceq_{01}),(P_{\star},\preceq_{\star}),(P_{\varnothing},\preceq_{\varnothing}),(P_{\textrm{CSP}},\preceq_{\textrm{CSP}})$.

######  Definition 2.5.

Let $\sigma$ be a finite signature and $*\in\\{01,\star\\}$. For a
$\star$-structure $\mathbf{H}$, the problem
$\textrm{MP}^{\sigma}_{*}(\mathbf{H})$ denotes the set of all $*$-structures
$\mathbf{G}$ such that there exists a homomorphism
$h\colon\mathbf{G}\to\mathbf{H}$. If $\mathbf{H}$ is a CSP-structure, then we
write $\textrm{CSP}^{\sigma}(\mathbf{H})$ as the set of all CSP-structures
$\mathbf{G}$ such that there exists a homomorphism
$h\colon\mathbf{G}\to\mathbf{H}$. We always omit subscript $01$ in
$\textrm{MP}_{01}^{\sigma}(\mathbf{H})$.

The set of all $\varnothing$-structures $\mathbf{G}$ such that there is a
homomorphism $h\colon\mathbf{G}\to\mathbf{H}$, with $\mathbf{H}$ a
$\varnothing$-structure, is denoted by
$\textrm{MP}_{\varnothing}^{\sigma}(\mathbf{H})$.

By $\textrm{MP}^{\sigma}$, $\textrm{MP}_{\star}^{\sigma}$,
$\textrm{MP}_{\varnothing}^{\sigma}$ and $\textrm{CSP}^{\sigma}$ we denote,
respectively, the families of problems $\textrm{MP}^{\sigma}(\mathbf{H})$,
$\textrm{MP}_{\star}^{\sigma}(\mathbf{H})$,
$\textrm{MP}_{\varnothing}^{\sigma}(\mathbf{H})$ and
$\textrm{CSP}^{\sigma}(\mathbf{H})$, for all $\star$-structures444For
$\textrm{CSP}^{\sigma}(\mathbf{H})$ we of course demand that $\mathbf{H}$ is a
$({\textrm{CSP}},\sigma)$-structure, and for
$\textrm{MP}_{\varnothing}^{\sigma}(\mathbf{H})$, we consider $\mathbf{H}$ to
be a $(\varnothing,\sigma)$-structure. $\mathbf{H}$. If
$\sigma=\\{E(\cdot,\cdot)\\}$ – the directed graph signature, then we will
omit the $\sigma$-superscript and will just write MP, $\textrm{MP}_{\star}$,
$\textrm{MP}_{\varnothing}$ and CSP.

Notice that as every $01$-structure is also a $\star$-structure, and every
$\star$-structure is also a $\varnothing$-structure, our problems are
correctly defined.

######  Observation 2.6 (Matrix Partitions [17]).

Let $\mathsf{M}$ be a an $n\times n$-matrix with entries on $\\{0,1,\star\\}$.
A graph $\mathbf{G}$ admits an _$\mathsf{M}$ -partition_ if there is a
function $m:G\to[n]$ such that for all distinct $x,y\in G$,
$E^{\mathbf{G}}(x,y)\preceq_{\star}M[m(x),m(y)]$.

######  Remark 2.7.

There are some differences between the definition of $\mathsf{M}$-partition in
[17] and the definition of $\textrm{MP}(\mathbf{H})$. Unlike Feder and Hell,
we consider all possible graphs in the input, not only the loopless ones. This
implies that we do not need to require that $x,y\in G$ must be distinct to
satisfy the condition of Matrix Partition. We decided to use our definition
because it can be generalised better.

It is already observed in [17, 21] that MP is a generalisation of CSP problems
in directed graphs, and hence the homomorphism problems
$\textrm{MP}^{\sigma}_{\star}$ are generalisations of $\textrm{CSP}^{\sigma}$
problems.

Let us end these preliminaries with the notion of P-time equivalence between
two families of problems, which allows to transfer dichotomy results. Two
decision problems $P_{1}$ and $P_{2}$ are _P -time equivalent_ if there is a
P-time reduction from $P_{1}$ to $P_{2}$, and a P-time reduction from $P_{2}$
to $P_{1}$.

For two subsets $\mathscr{C}$ and $\mathscr{C^{\prime}}$ of decision problems,
we say that they are _P -time equivalent_ if for any $P\in\mathscr{C}$, one
can find in P-time $P^{\prime}\in\mathscr{C^{\prime}}$ and both are P-time
equivalent, and similarly, for any $P^{\prime}\in\mathscr{C^{\prime}}$, one
can find in P-time $P\in\mathscr{C}$ and both are P-time equivalent.

######  Observation 2.8.

All along the paper, whenever we consider a problem
$\textrm{MP}_{*}^{\sigma}(\mathbf{H})$, for $*\in\\{01,\star,\varnothing\\}$,
we consider that there is no $x\in H$ such that for all $R\in\sigma$,
$R(x,\ldots,x)=\star$. Otherwise, the problem is trivial as then
$\textrm{MP}_{*}^{\sigma}(\mathbf{H})$ equals $\textrm{Cat}_{*}^{\sigma}$.

##  3\. Equivalence between $\textrm{MP}_{\varnothing}^{\sigma}$ and
$\textrm{CSP}^{\sigma_{\textrm{CSP}}}$

Let $\sigma=\\{R_{1},\ldots,R_{n}\\}$ be a signature, the arity of each
$R_{i}$ denoted by $k_{i}$. We prove in this section that there is a signature
$\sigma_{\textrm{CSP}}$ such that any problem in
$\textrm{MP}_{\varnothing}^{\sigma}$ is P-time equivalent to a problem in
$\textrm{CSP}^{\sigma_{\textrm{CSP}}}$ and vice versa.

The signature $\sigma_{\textrm{CSP}}$ is defined by repeating each symbol of
$\sigma$ two times, one for $0$-tuples and one for $1$-tuples, $\star$-tuples
will be considered as $0$\- and $1$-tuples at the same time:
$\sigma_{\textrm{CSP}}=\\{R_{1,0},R_{1,1},\ldots,R_{n,0},R_{n,1}\\}$, for
$i\in[n],R_{i,0},R_{i,1}$ both have arity $k_{i}$.

For every $\varnothing$-structure $\mathbf{A}_{\varnothing}$, we correspond a
relational $\sigma_{\textrm{CSP}}$-structure $\mathbf{A}_{\textrm{CSP}}$ with
the same domain $A$ and the symbols $R_{i,0},R_{i,1}$ of
$\sigma_{\textrm{CSP}}$ are interpreted as follows:

(1) $\forall R_{i}\in\sigma,\mathbf{t}\in A^{k_{i}},j\in\\{0,1\\}\colon
R_{i,j}^{\mathbf{A}_{\textrm{CSP}}}(\mathbf{t})=1\Leftrightarrow
j\preceq_{\varnothing}R_{i}^{\mathbf{A}_{\varnothing}}(\mathbf{t}).$

######  Observation 3.1.

$\mathbf{A}_{\textrm{CSP}}$ is constructible in P-time in the size of
$\mathbf{A}_{\varnothing}$.

######  Observation 3.2.

For any $({\varnothing},\sigma)$-structure $\mathbf{A}_{\varnothing}$, there
exists a unique relational $\sigma_{\textrm{CSP}}$-structure
$\mathbf{A}_{\textrm{CSP}}$, and for any relational
$\sigma_{\textrm{CSP}}$-structure, there exists a unique
$({\varnothing},\sigma)$-structure $\mathbf{A}_{\varnothing}$ such that eq. 1
is satisfied. That is there is a bijective correspondence between
$({\varnothing},\sigma)$-structures and relational
$\sigma_{\textrm{CSP}}$-structures.

######  Theorem 3.3.

$\textrm{MP}_{\varnothing}^{\sigma}$ and
$\textrm{CSP}^{\sigma_{\textrm{CSP}}}$ are P-time equivalent.

###### Proof.

Let $\mathbf{A}_{\varnothing}$ be a $\varnothing$-structure. We first prove
that
$\mathbf{B}_{\varnothing}\in\textrm{MP}_{\varnothing}^{\sigma}(\mathbf{A}_{\varnothing})$
if and only if
$\mathbf{B}_{\textrm{CSP}}\in\textrm{CSP}^{\sigma_{\textrm{CSP}}}(\mathbf{A}_{\textrm{CSP}})$.

Assume that
$\mathbf{B}_{\varnothing}\in\textrm{MP}_{\varnothing}^{\sigma}(\mathbf{A}_{\varnothing})$
and let $h:B\to A$ be a homomorphism from $\mathbf{B}_{\varnothing}$ to
$\mathbf{A}_{\varnothing}$. We will show that the same map $h$ is a
homomorphism from $\mathbf{B}_{\textrm{CSP}}$ to $\mathbf{A}_{\textrm{CSP}}$.
For any tuple $\mathbf{t}$ and its image $h(\mathbf{t})$, we know that for any
$R_{i,j}\in\sigma_{\textrm{CSP}}$:

$R_{i,j}^{\mathbf{B}_{\textrm{CSP}}}(\mathbf{t})=1\Leftrightarrow
j\preceq_{\varnothing}R_{i}^{\mathbf{B}_{\varnothing}}(\mathbf{t})\Rightarrow
j\preceq_{\varnothing}R_{i}^{\mathbf{A}_{\varnothing}}(h(\mathbf{t}))\Leftrightarrow
R_{i,j}^{\mathbf{A}_{\textrm{CSP}}}(h(\mathbf{t}))=1.$

Now, backwards, assume that
$\mathbf{B}_{\textrm{CSP}}\in\textrm{CSP}^{\sigma_{\textrm{CSP}}}(\mathbf{A}_{\textrm{CSP}})$,
and let $h:B\to A$ a homomorphism from $\mathbf{B}_{\textrm{CSP}}$ to
$\mathbf{A}_{\textrm{CSP}}$. Similarly as in the first part, for a tuple
$\mathbf{t}$, we know that for all $R_{i}\in\sigma,j\in\\{0,1\\}$:

$j\preceq_{\varnothing}R_{i}^{\mathbf{B}_{\varnothing}}(\mathbf{t})\Leftrightarrow
R_{i,j}^{\mathbf{B}_{\textrm{CSP}}}(\mathbf{t})=1\Rightarrow
R_{i,j}^{\mathbf{A}_{\textrm{CSP}}}(h(\mathbf{t}))=1\Leftrightarrow
j\preceq_{\varnothing}R_{i}^{\mathbf{A}_{\varnothing}}(h(\mathbf{t})).$

This implies that $h$ is a homomorphism from $\mathbf{B}_{\varnothing}$ to
$\mathbf{A}_{\varnothing}$. ∎

For $*\in\\{01,\star,\varnothing\\}$, the notion of homomorphism between
$({*},\sigma)$-structures admits a _core_ notion. It generalises the notion of
a core for trigraphs ($\star$-graphs) given in [24]. For
$*\in\\{01,\star,\varnothing\\}$, a $({*},\sigma)$-structure $\mathbf{C}$ is
called a _core_ if any homomorphism $h\colon\mathbf{C}\to\mathbf{C}$ is an
isomorphism, where isomorphism between $({*},\sigma)$-structures is the same
as usual.

######  Proposition 3.4.

Let $*\in\\{01,\star,\varnothing\\}$. Then for any $({*},\sigma)$-structure
$\mathbf{A}_{*}$, there exists a unique, up to isomorphism,
$({*},\sigma)$-structure $\mathbf{C}_{*}$ such that it is a core and
$\mathbf{A}_{*}\leftrightarrows\mathbf{C}_{*}$, and $\mathbf{C}_{*}$ embeds
into $\mathbf{A}_{*}$.

###### Proof.

We know that $\mathbf{A}_{*}$ is also a $\varnothing$-structure by Proposition
2.4. Then, consider the relational $\sigma_{\textrm{CSP}}$-structure
$\mathbf{A}_{\textrm{CSP}}$ provided by Theorem 3.3. It has the core
$\mathbf{C}_{\textrm{CSP}}$ embedded into $\mathbf{A}_{\textrm{CSP}}$. Let
$\mathbf{C}_{*}$ be the corresponding $\varnothing$-structure by Theorem 3.3,
it must also be homomorphically equivalent to $\mathbf{A}_{*}$ and be embedded
into it. As $\mathbf{C}_{*}$ embeds into $\mathbf{A}_{*}$, it is also a
$*$-structure. Let $e:C\to C$ be a non-injective endomorphism. Then the same
map $e$ will be a non-injective endomorphism of the core
$\mathbf{C}_{\textrm{CSP}}$ which is impossible. Let $\mathbf{C}_{*}^{\prime}$
be another core of $\mathbf{A}_{*}$, that is not isomorphic to
$\mathbf{C}_{*}$. But then $\mathbf{C}_{\textrm{CSP}}^{\prime}$ must be the
core of $\mathbf{A}_{\textrm{CSP}}$ and
$\mathbf{C}_{\textrm{CSP}}\not\cong\mathbf{C}_{\textrm{CSP}}^{\prime}$ which
is impossible as $\mathbf{C}_{\textrm{CSP}}$ is a core. ∎

##  4\. Equivalence between $\textrm{MP}^{\sigma}_{\star}$ and
$\textrm{MP}^{\sigma}$

In this section we will prove the following theorem.

######  Theorem 4.1.

For any finite signature $\sigma$, $\textrm{MP}^{\sigma}$ and
$\textrm{MP}_{\star}^{\sigma}$ are P-time equivalent.

In order to prove the P-time equivalence, we will show that for any
$\star$-structure $\mathbf{H}$, the two corresponding problems:
$\textrm{MP}^{\sigma}(\mathbf{H})$ and
$\textrm{MP}_{\star}^{\sigma}(\mathbf{H})$ are P-time equivalent. We first do
the proof for $\star$-graphs, and then explain how to modify the construction
for any $\sigma$. Hell and Nešetřil proved in [24] that for any $\star$-graph
$\mathbf{G}$ there is a $01$-graph $\mathbf{G}_{01}$ such that
$\mathbf{G}\in\textrm{MP}_{\star}(\mathbf{H})\Leftrightarrow\mathbf{G}_{01}\in\textrm{MP}(\mathbf{H})$
using probabilistic arguments. We prove the P-time equivalence by giving a
determenistic algorithm running in P-time.

In order to prove that for any $\star$-graph $\mathbf{G}$, there is a
$01$-graph $\mathbf{G}_{01}$ such that
$\mathbf{G}\in\textrm{MP}_{\star}(\mathbf{H})$ if and only if
$\mathbf{G}_{01}\in\textrm{MP}(\mathbf{H})$, we will use the notion of
_Hadamard matrices_.

######  Definition 4.2 (Hadamard Matrices).

An $n\times n$-matrix $\mathsf{H}_{n}$, which entries are in $\\{1,-1\\}$, is
called a _Hadamard matrix_ if

$\mathsf{H}_{n}\cdot\mathsf{H}_{n}^{T}=n\cdot\mathsf{I}_{n},$

where $\mathsf{I}_{n}$ is the identity matrix of size $n$, and
$\mathsf{H}^{T}$ is the transpose of $\mathsf{H}$.

Hadamard matrices exist for any power of $2$.

######  Lemma 4.3 ([32]).

For every positive integer $n>1$, one can construct in time $2^{poly(n)}$ a
$2^{n}\times 2^{n}$-Hadamard matrix.

If $\mathsf{H}_{n}$ is an $n\times n$-Hadamard matrix, that we assume its rows
and columns indexed by $[n]$, then for any two sets $A,B\subseteq[n]$, we
denote by $\mathsf{H}_{n}[A,B]$ the submatrix of $\mathsf{H}_{n}$, whose rows
are indexed by $A$ and columns are indexed by $B$. If all the entries of
$\mathsf{H}_{n}[A,B]$ are equal, then we call $\mathsf{H}_{n}[A,B]$ a
_monochromatic submatrix_. We will need the following to prove that if
$\mathbf{G}_{01}\in\textrm{MP}(\mathbf{H})$, then
$\mathbf{G}\in\textrm{MP}_{\star}(\mathbf{H})$.

######  Lemma 4.4 ([1, 29]).

Let $\mathsf{H}_{n}$ be an $n\times n$-Hadamard matrix, whose rows and columns
are indexed by $[n]$. Then, for any two disjoint sets $A,B\subseteq[n]$, with
$|A|=|B|>\sqrt{n}$, the submatrix $\mathsf{H}_{n}[A,B]$ of $\mathsf{H}_{n}$ is
not monochromatic.

###### Proof of Theorem 4.1.

Let us first explain the case of $\star$-graphs. Let $\mathbf{H}$ be a
$\star$-graph with $m=|H|$. We will show the P-time equivalence between the
problems $\textrm{MP}(\mathbf{H})$ and $\textrm{MP}_{\star}(\mathbf{H})$.

Every $01$-graph is also a $\star$-graph, so $\textrm{MP}_{01}(\mathbf{H})$
trivially reduces to $\textrm{MP}_{\star}(\mathbf{H})$. For the opposite
direction, let us construct for every $\star$-graph $\mathbf{G}$, a $01$-graph
$\mathbf{G}_{01}$ such that $\mathbf{G}\in\textrm{MP}_{\star}(\mathbf{H})$ if
and only $\mathbf{G}_{01}\in\textrm{MP}_{01}(\mathbf{H})$.

Let $k$ be the smallest positive integer such that $2^{k}>4m^{2}+1$, and let
$\mathsf{H}_{2^{k}}$ be the Hadamard matrix ensured by Lemma 4.3. Let the
domain of $\mathbf{G}_{01}$ be the disjoint union $\bigsqcup_{g\in G}V_{g}$,
where for all $g\in G$, $|V_{g}|=2^{k}$. Let us enumerate the set $V_{g}$ as
$\\{v_{g,1},\ldots,v_{g,2^{k}}\\}$, for each $g\in G$. Now, for each
$v_{g_{1},i}\in V_{g_{1}}$ and $v_{g_{2},j}\in V_{g_{2}}$, $1\leq i,j\leq
2^{k}$,

$\displaystyle E^{\mathbf{G}_{01}}(v_{g_{1},i},v_{g_{2},j})$
$\displaystyle=\begin{cases}E^{\mathbf{G}}(g_{1},g_{2})&\textrm{if
$E^{\mathbf{G}}(g_{1},g_{2})\neq\star$},\\\
(\mathsf{H}_{2^{k}}[i,j]+1)/2&\textrm{otherwise}.\end{cases}$

Observe that in the case $E^{\mathbf{G}}(g_{1},g_{2})=\star$, if
$\mathsf{H}_{2^{k}}[i,j]=1$, then
$E^{\mathbf{G}_{01}}(v_{g_{1},i},v_{g_{2},j})=1$, otherwise it is equal to
$0$.

By construction, there exists a surjective homomorphism
$\pi\colon\mathbf{G}_{01}\to\mathbf{G}$ such that for all $g\in G$,
$\pi(V_{g})=g$. If there exists a homomorphism
$h\colon\mathbf{G}\to\mathbf{H}$, then, by transitivity, $h\circ\pi:G_{01}\to
H$ will be a homomorphism. Suppose that there exists a homomorphism
$h_{01}\colon\mathbf{G}_{01}\to\mathbf{H}$. By pigeonhole principle, for every
$V_{g}$, there is a set of size at least $\frac{|V_{g}|}{m}$ elements of
$V_{g}$ that are mapped by $h_{01}$ to the same element of $\mathbf{H}$, and
let us call it $A_{g}\subseteq V_{g}$, for each $g\in G$. Let us define a map
$h\colon G\to H$ with $h(g)=h_{01}(A_{g})$. Now, for every two elements
$g_{1},g_{2}\in G$, if $E^{\mathbf{G}}(g_{1},g_{2})\in\\{0,1\\}$, then for all
$a_{1}\in A_{g_{1}},a_{2}\in A_{g_{2}}$,
$E^{\mathbf{G}_{01}}(a_{1},a_{2})=E^{\mathbf{G}}(g_{1},g_{2})$, so
$E^{\mathbf{G}}(g_{1},g_{2})\preceq_{\star}E^{\mathbf{H}}(h(g_{1}),h(g_{2}))$.
If $E^{\mathbf{G}}(g_{1},g_{2})=\star$, then
$\mathsf{H}_{2^{k}}[A_{g_{1}},A_{g_{2}}]$ is of size at least
$\frac{4m^{2}+1}{m}\times\frac{4m^{2}+1}{m}$, where $A_{g}$ is identified with
the set $\\{i\in[2^{k}]\mid v_{g,i}\in A_{g}\\}$. One checks easily that there
are subsets $B_{1}$ of $A_{g_{1}}$, and $B_{2}$ of $A_{g_{2}}$, that do not
intersect and both of size at least $\frac{|V_{g}|}{2m}$. Observe that

$\frac{|V_{g}|}{2m}\geq\frac{4m^{2}+1}{2m}\geq\sqrt{4m^{2}+1}.$

By Lemma 4.4, the submatrix $\mathsf{H}_{2^{k}}[B_{1},B_{2}]$ is not
monochromatic. Thus, $E^{\mathbf{H}}(h(g_{1}),h(g_{2}))=\star$ and $h$ is a
homomorphism from $\mathbf{G}$ to $\mathbf{H}$, and we are done.

Let us now prove the general case. Let $\sigma=\\{R_{1},\ldots,R_{p}\\}$ a
signature, with $k_{i}$ the arity of $R_{i}$, for $i\in[p]$. We recall that
$\textrm{MP}^{\sigma}(\mathbf{H})$ trivially reduces to
$\textrm{MP}_{\star}^{\sigma}(\mathbf{H})$ as it is the same problem, but with
restricted inputs.

For the other direction, we use the same technique as in the proof for the
binary case, we construct a $01$-structure $\mathbf{G}_{01}$. For a given
input $\mathbf{G}$, and for any element $g\in G$, we introduce a set
$V_{g}=\\{v_{g,1},\ldots,v_{g,2^{k}}\\}$ of size $2^{k}$ such that $2^{k}\geq
4|H|^{2}+1$ and $k$ is the smallest such positive integer. Let also
$\mathsf{H}_{2^{k}}$ be the Hadamard matrix guaranteed by Lemma 4.3. Now, the
domain $G_{01}$ of $\mathbf{G}_{01}$ is the disjoint union $\bigsqcup_{g\in
G}V_{g}$. For each $R_{i}\in\sigma$ and for each tuple
$(v_{g_{1},i_{1}},v_{g_{2},i_{2}},\ldots,v_{g_{k_{i}},i_{k_{i}}})$,

$\displaystyle
R_{i}^{\mathbf{G}_{01}}(v_{g_{1},i_{1}},\ldots,v_{g_{k_{i}},i_{k_{i}}})$
$\displaystyle=\begin{cases}R_{i}^{\mathbf{G}}(g_{1},\ldots,g_{k_{i}})&\textrm{if
$R_{i}^{\mathbf{G}}(g_{1},\ldots,g_{k_{i}})\neq\star$},\\\
(\mathsf{H}_{2^{k}}[i_{1},i_{2}]+1)/2&\textrm{otherwise}.\end{cases}$

Suppose now that there exists $h_{01}\colon\mathbf{G}_{01}\to\mathbf{H}$.
Then, by pigeonhole principle, in each set $V_{g}$, there is a set of size at
least $\frac{|V_{g}|}{|H|}$ elements that are mapped to the same element of
$H$, denoted by $A_{g}$. Then, the sets $A_{g_{1}}$ and $A_{g_{2}}$ define a
submatrix of $\mathsf{H}_{2^{k}}$ of size at least $2\sqrt{2^{k}}$ and thus it
is not monochromatic by the same argument as in the proof for the binary case.
We can conclude then the statement. ∎

##  5\. Arity Reduction

Recall that a _primitive-positive formula_ $\varphi(x_{1},\ldots,x_{n})$ is a
first-order formula ($\mathsf{FO}^{\sigma}$) of the form

$\exists x_{n+1},\ldots,x_{m}.(\psi_{1}\wedge\dots\wedge\psi_{l})$

where each $\psi_{i}$ is either $x_{s}=x_{j}$, $\mathsf{true}$, or
$R(x_{i_{1}},\ldots,x_{i_{k}})=1$.

Let $\sigma=\\{R_{1},\ldots,R_{n}\\},\sigma^{\prime}=\\{S_{1},\ldots,S_{m}\\}$
be two signatures, and $\mathbf{A},\mathbf{A}^{\prime}$ be relational
$\sigma$\- and $\sigma^{\prime}$-structures over the same domain $A$. We say
that $\mathbf{A}$ _pp-defines_ $\mathbf{A}^{\prime}$ if for every $k$-ary
relation $S_{j}^{\mathbf{A^{\prime}}}$ of $\mathbf{A}^{\prime}$ there exists a
primitive-positive formula $\varphi_{j}\in\mathsf{FO}^{\sigma}$ with $k$ free
variables such that for all $(a_{1},\ldots,a_{k})\in A^{k}$,
$S_{j}^{\mathbf{A^{\prime}}}(a_{1},\ldots,a_{n})=1\Leftrightarrow\mathbf{A}^{\prime}\models\varphi_{j}(a_{1}/x_{1},\ldots,a_{n}/x_{n})$.

######  Theorem 5.1.

[4] Suppose that a relational $\sigma$-structure $\mathbf{A}$ pp-defines a
relational $\sigma^{\prime}$-structure $\mathbf{A}^{\prime}$. Then the problem
$\textrm{CSP}^{\sigma^{\prime}}(\mathbf{A}^{\prime})$ reduces in P-time to
$\textrm{CSP}^{\sigma}(\mathbf{A})$.

###  5.1. From directed graphs to many relations

Let $\sigma=\\{R_{1},\ldots,R_{n}\\}$ be a finite signature with arities
$k_{1},\ldots,k_{n}$, and such that $k_{1}\geq 2$. We show that the existence
of a dichotomy for the class of problems $\textrm{MP}_{\star}^{\sigma}$
implies the existence of a dichotomy for the class of $\star$-graphs
$\textrm{MP}_{\star}$. Let $\gamma=\\{E(\cdot,\cdot)\\}$ be the directed graph
signature and let
$\gamma_{\textrm{CSP}}=\\{E_{0}(\cdot,\cdot),E_{1}(\cdot,\cdot)\\}$ be
obtained from $\gamma$ by the construction from Section 3.

######  Theorem 5.2.

For every $\star$-graph $\mathbf{H}_{\star}$, there exists a
$({\star},\sigma)$-structure $\mathbf{A}_{\star}$ such that the problems
$\textrm{MP}_{\star}(\mathbf{H}_{\star})$ and
$\textrm{MP}_{\star}^{\sigma}(\mathbf{A}_{\star})$ are P-time equivalent.

###### Proof.

Let us recall from the Section 3 that there is a bijective correspondence
between a $({\varnothing},\sigma)$-structure $\mathbf{A}_{\varnothing}$ and a
relational $\sigma_{\textrm{CSP}}$-structure $\mathbf{A}_{\textrm{CSP}}$ such
that for any two $({\varnothing},\sigma)$-structures
$\mathbf{A}_{\varnothing},\mathbf{B}_{\varnothing}$:

$\mathbf{B}_{\varnothing}\to\mathbf{A}_{\varnothing}\Leftrightarrow\mathbf{B}_{\textrm{CSP}}\to\mathbf{A}_{\textrm{CSP}}.$

Now, let us consider a $\star$-graph $\mathbf{H}_{\star}$ with its
corresponding relational $\gamma_{\textrm{CSP}}$-structure
$\mathbf{H}_{\textrm{CSP}}$. We construct the
$\sigma_{\textrm{CSP}}$-structure $\mathbf{A}_{\textrm{CSP}}$ by the following
pp-definition:

(2) $\forall j\in\\{0,1\\}\colon
R_{1,j}^{\mathbf{A}_{\textrm{CSP}}}(x_{1},\ldots,x_{k_{1}})=1\Leftrightarrow
E_{j}^{\mathbf{H}_{\textrm{CSP}}}(x_{1},x_{2})=1;$ (3) $\forall
i>1,j\in\\{0,1\\}\colon
R_{i,j}^{\mathbf{A}_{\textrm{CSP}}}(x_{1},\ldots,x_{k_{i}})=1\Leftrightarrow\mathsf{true}.$

Observe that the relational $\gamma_{\textrm{CSP}}$-structure
$\mathbf{H}_{\textrm{CSP}}$ is also pp-definable from the relational
$\sigma_{\textrm{CSP}}$-structure $\mathbf{A}_{\textrm{CSP}}$:

(4) $E^{\mathbf{H}_{\textrm{CSP}}}(x_{1},x_{2})=1\Leftrightarrow\exists
x_{3},\ldots,x_{k_{1}}.R_{1}^{\mathbf{A}_{\textrm{CSP}}}(x_{1},\ldots,x_{k_{1}}).$

Now consider any $\star$-graph $\mathbf{G}_{\star}$. Every $\star$-graph is
also a $\varnothing$-graph, so there is a relational
$\gamma_{\textrm{CSP}}$-structure $\mathbf{G}_{\textrm{CSP}}$ such that
$\mathbf{G}_{\star}\to\mathbf{H}_{\star}$ if and only if
$\mathbf{G}_{\textrm{CSP}}\to\mathbf{H}_{\textrm{CSP}}$. By the pp-
definability in eq. 4 and Theorem 5.1, we construct a relational
$\sigma_{\textrm{CSP}}$-structure $\mathbf{B}_{\textrm{CSP}}$ such that
$\mathbf{G}_{\textrm{CSP}}\to\mathbf{H}_{\textrm{CSP}}$ if and only if
$\mathbf{B}_{\textrm{CSP}}\to\mathbf{A}_{\textrm{CSP}}$. From
$\mathbf{B}_{\textrm{CSP}}$ we obtain a $({\star},\sigma)$-structure
$\mathbf{B}_{\star}$ such that
$\mathbf{B}_{\textrm{CSP}}\to\mathbf{A}_{\textrm{CSP}}$ if and only if
$\mathbf{B}_{\star}\to\mathbf{A}_{\star}$. Observe that, because
$\mathbf{G}_{\star}$ is a $\star$-graph, in $\mathbf{G}_{\textrm{CSP}}$ for
any $(x,y)\in G^{2}$, we have either
$E_{0}^{\mathbf{G}_{\textrm{CSP}}}(x,y)=1$ or
$E_{1}^{\mathbf{G}_{\textrm{CSP}}}(x,y)=1$; thus in
$\mathbf{B}_{\textrm{CSP}}$ any relation other than $R_{1}$ is interpreted
trivially and for each tuple $\mathbf{x}\in B^{k_{1}}$ either
$R_{1,0}^{\mathbf{B}_{\textrm{CSP}}}(\mathbf{x})=1$ or
$R_{1,1}^{\mathbf{B}_{\textrm{CSP}}}(\mathbf{x})=1$. So, $\mathbf{B}_{\star}$
is indeed a $({\star},\sigma)$-structure, that finishes the reduction from
$\textrm{MP}_{\star}(\mathbf{H}_{\star})$ to
$\textrm{MP}_{\star}^{\sigma}(\mathbf{A}_{\star})$.

For the other direction, consider any $({\star},\sigma)$-structure
$\mathbf{B}_{\star}$. Similarly, we construct a relational
$\sigma_{\textrm{CSP}}$-structure $\mathbf{B}_{\textrm{CSP}}$, and by the pp-
definition in eqs. 2 and 3, we can compute a relational
$\gamma_{\textrm{CSP}}$-structure $\mathbf{G}_{\textrm{CSP}}$ such that
$\mathbf{G}_{\textrm{CSP}}\to\mathbf{H}_{\textrm{CSP}}$ if and only if
$\mathbf{B}_{\star}\to\mathbf{A}_{\star}$, and then a $\star$-graph
$\mathbf{G}_{\star}$ such that $\mathbf{B}_{\star}\to\mathbf{A}_{\star}$ if
and only if $\mathbf{G}_{\star}\to\mathbf{H}_{\star}$. With similar arguments
as in the other direction, we can prove that $\mathbf{G}_{\star}$ is indeed a
$\star$-graph. We have then shown that
$\textrm{MP}_{\star}(\mathbf{G}_{\star})$ and
$\textrm{MP}_{\star}^{\sigma}(\mathbf{A}_{\star})$ are P-time equivalent. ∎

One notices that the proof of Theorem 5.2 is still correct if we replace
$\gamma$ by any relation $R$ of arity $\ell\geq 2$, we require in this case
that $R_{1}$ has arity at least $\ell$.

###  5.2. From many relations to one

Suppose that $\sigma=\\{R_{1},\ldots,R_{p}\\}$, $R_{i}$ has arity $k_{i}$, let
$k=\max_{i}k_{i}$. In this section we show that for any such $\sigma$ there
exists $\tilde{\sigma}=\\{R\\}$ with $R$ of arity $k+p-1$ such that for any
$({\star},\sigma)$-structure $\mathbf{A}$ there exists a
$({\star},\tilde{\sigma})$-structure $\tilde{\mathbf{A}}$ such that
$\textrm{MP}_{\star}^{\sigma}(\mathbf{A})$ and
$\textrm{MP}_{\star}^{\tilde{\sigma}}(\tilde{\mathbf{A}})$ are P-time
equivalent.

Now we will describe how the $\tilde{\sigma}$-structure $\tilde{\mathbf{A}}$
is constructed. If $A$ is the domain of $\mathbf{A}$, then the domain
$\tilde{A}$ of $\tilde{\mathbf{A}}$ is $\tilde{A}=A\sqcup\\{c_{A}\\}$, with
$c_{A}$ a new element. The relation $R^{\tilde{\mathbf{A}}}$ is defined as
follows:

  * •

Let
$\mathcal{A}_{1}=\\{\tilde{\mathbf{t}}=(\underbrace{c_{A},\ldots,c_{A}}_{i-1},\mathbf{t},\underbrace{c_{A},\ldots,c_{A}}_{k+p-k_{i}-i})\mid
R_{i}\in\sigma,\mathbf{t}\in A^{k_{i}}\\}$, and

(5) $\textrm{for all},\ \tilde{\mathbf{t}}\in\mathcal{A}_{1},\
R^{\tilde{\mathbf{A}}}(\tilde{\mathbf{t}})=R^{\mathbf{A}}_{i}(\mathbf{t});$

  * •

Let $\mathcal{A}_{2}=\\{(c_{A},\ldots,c_{A})\\}$, then for all
$\tilde{\mathbf{t}}\in\mathcal{A}_{2}\colon
R^{\tilde{\mathbf{A}}}(\tilde{\mathbf{t}})=1$;

  * •

Let
$\mathcal{A}_{3}=\tilde{A}^{k+p-1}\setminus(\mathcal{A}_{1}\sqcup\mathcal{A}_{2})$,
then for all $\tilde{\mathbf{t}}\in\mathcal{A}_{3}\colon
R^{\tilde{\mathbf{A}}}(\tilde{\mathbf{t}})=0$.

Now we will prove one direction of the P-time equivalence. The size of
$\tilde{\mathbf{A}}$ is polynomial in $|A|$, so the construction takes P-time,
and below we show that
$\mathbf{B}\to\mathbf{A}\Leftrightarrow\tilde{\mathbf{B}}\to\tilde{\mathbf{A}}.$

######  Lemma 5.3.

$\textrm{MP}_{\star}^{\sigma}(\mathbf{A})$ reduces in polynomial time to
$\textrm{MP}_{\star}^{\tilde{\sigma}}(\tilde{\mathbf{A}})$.

###### Proof.

Let $\mathbf{B}$ be an input instance of the problem
$\textrm{MP}_{\star}^{\sigma}(\mathbf{A})$. Assume that there is
$h\colon\mathbf{B}\to\mathbf{A}$ – a homomorphism. We will show that
$\tilde{h}\colon\tilde{B}\to\tilde{A}$ such that $\tilde{h}(c_{B})=c_{A}$ and
for all $x\in B\setminus\\{c_{B}\\}\colon\tilde{h}(x)=h(x)$, is a
homomorphism.

Recall that
$\tilde{B}^{k+p-1}=\mathcal{B}_{1}\sqcup\mathcal{B}_{2}\sqcup\mathcal{B}_{3}$.
Consider
$\tilde{\mathbf{t}}=(c_{B},\ldots,c_{B},\mathbf{t},c_{B},\ldots,c_{B})\in\mathcal{B}_{1}$,
where $\mathbf{t}=(b_{1},\ldots,b_{k_{i}})\in B^{k_{i}}$ for $R_{i}\in\sigma$.
Then
$\tilde{h}(\tilde{\mathbf{t}})=(c_{A},\ldots,c_{A},h(\mathbf{t}),c_{A},\ldots,c_{A})\in\mathcal{A}_{1}$.
As $h$ is a homomorphism, we have that by eq. 5:

$R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})=R_{i}^{\mathbf{B}}(\mathbf{t})\preceq_{\star}R_{i}^{\mathbf{A}}(h(\mathbf{t}))=R^{\tilde{\mathbf{A}}}(\tilde{h}(\tilde{\mathbf{t}})).$

For $\tilde{\mathbf{t}}\in\mathcal{B}_{2}$, we have that
$\tilde{h}(\tilde{\mathbf{t}})=(c_{A},\ldots,c_{A})$, so
$R^{\tilde{\mathbf{A}}}(\tilde{h}(\tilde{\mathbf{t}}))=R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})=1.$
Let us consider a tuple
$\tilde{\mathbf{t}}=(x_{1},\ldots,x_{k+p-1})\in\mathcal{B}_{3}$. We know that
$\tilde{h}(x)=c_{A}$ if and only if $x=c_{B}$, thus
$\tilde{h}(\tilde{\mathbf{t}})\in\mathcal{A}_{3}$. Then
$R^{\tilde{\mathbf{A}}}(\tilde{h}(\tilde{\mathbf{t}}))=R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})=0.$
We have shown that $\tilde{h}$ is a homomorphism.

Assume that there is $\tilde{h}\colon\tilde{\mathbf{B}}\to\tilde{\mathbf{A}}$
– a homomorphism. We know that $x=c_{B}$ if and only if
$R^{\tilde{\mathbf{B}}}(x,\ldots,x)=1$, and otherwise
$R^{\tilde{\mathbf{B}}}(x,\ldots,x)=0$. We also know the same thing for
$\tilde{\mathbf{A}}$. Thus, $x=c_{B}$ if and only if $\tilde{h}(x)=c_{A}$.
This allows us to correctly construct $h\colon\mathbf{B}\to\mathbf{A}$, where
for all $x\in B$, $h(x)=\tilde{h}(x)$.

For any $R_{i}\in\sigma$ and $\mathbf{t}\in B^{k_{i}}$, $\mathbf{t}$
corresponds to
$\tilde{\mathbf{t}}=(c_{B},\ldots,c_{B},\mathbf{t},c_{B}\ldots,c_{B})\in\mathcal{B}_{1}$
and its image $h(\mathbf{t})\in A^{k_{i}}$ corresponds to
$\tilde{h}(\tilde{\mathbf{t}})=(c_{A},\ldots,c_{A},h(\mathbf{t}),c_{A},\ldots,c_{A})\in\mathcal{A}_{1}$.
We know that by the construction of $\tilde{\mathbf{A}}$ and
$\tilde{\mathbf{B}}$, and by eq. 5:

$R_{i}^{\mathbf{B}}(\mathbf{t})=R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})\preceq_{\star}R^{\tilde{\mathbf{A}}}(\tilde{h}(\tilde{\mathbf{t}}))=R_{i}^{\mathbf{A}}(h(\mathbf{t})).$

So, $h$ is a homomorphism and $\textrm{MP}_{\star}^{\sigma}(\mathbf{A})$
reduces to $\textrm{MP}_{\star}^{\tilde{\sigma}}(\tilde{\mathbf{A}})$. ∎

Now we have to find in polynomial time for any input
$({\star},\tilde{\sigma})$-structure $\tilde{\mathbf{G}}$ of
$\textrm{MP}_{\star}^{\tilde{\sigma}}(\mathbf{A})$ a
$({\star},\sigma)$-structure $\mathbf{B}$ such that

$\tilde{\mathbf{G}}\to\tilde{\mathbf{A}}\Leftrightarrow\mathbf{B}\to\mathbf{A}.$

######  Lemma 5.4.

$\textrm{MP}_{\star}^{\tilde{\sigma}}(\tilde{\mathbf{A}})$ reduces in
polynomial time to $\textrm{MP}_{\star}^{\sigma}(\mathbf{A})$.

###### Proof.

Let $\tilde{\mathbf{G}}$ be an input instance of
$\textrm{MP}_{\star}^{\tilde{\sigma}}(\tilde{\mathbf{A}})$. Firstly, for any
element $x\in\tilde{G}$, we check whether
$R^{\tilde{\mathbf{G}}}(x,\ldots,x)=\star$. If such an $x$ exists, then we
cannot map $\tilde{\mathbf{G}}$ to $\tilde{\mathbf{A}}$ as for all
$y\in\tilde{A}$ we have that $R^{\tilde{\mathbf{A}}}(y,\ldots,y)\in\\{0,1\\}$.
This can be checked in time linear in $|\tilde{G}|$. In this case, we output
some fixed NO input instance of $\textrm{MP}_{\star}^{\sigma}(\mathbf{A})$,
e.g., some $\mathbf{B}$ where there is $b\in B$ and
$R_{i}^{\mathbf{B}}(b,\ldots,b)=\star$ for all $R_{i}\in\sigma$.

Now we can assume that, for all $x\in\tilde{G}$,
$R^{\tilde{\mathbf{G}}}(x,\ldots,x)\in\\{0,1\\}$. We divide the elements of
$\tilde{G}$ into two classes: $\tilde{G}=C_{1}\sqcup C_{0}$ by the following
rule:

(6) $\textrm{for all}\ x\in\tilde{G},\ x\in C_{i}\Leftrightarrow
R^{\tilde{\mathbf{G}}}(x,\ldots,x)=i.$

Observe that if there exists a homomorphism
$h\colon\tilde{\mathbf{G}}\to\tilde{\mathbf{A}}$, then for all
$x\in\tilde{G}\colon h(x)=c_{A}\Leftrightarrow x\in C_{1}$. We are going to
construct a $\tilde{\sigma}$-structure $\tilde{\mathbf{B}}$ with the following
properties:

  1. (1)

$\tilde{\mathbf{G}}\to\tilde{\mathbf{B}}$;

  2. (2)

$\tilde{\mathbf{G}}\to\tilde{\mathbf{A}}\Leftrightarrow\tilde{\mathbf{B}}\to\tilde{\mathbf{A}}$;

  3. (3)

Either we can check in P-time that
$\tilde{\mathbf{B}}\not\to\tilde{\mathbf{A}}$ or there exists a
$\sigma$-structure $\mathbf{B}$ such that $\tilde{\mathbf{B}}$ can be obtained
from $\mathbf{B}$ by the construction described above in this section.

The domain $\tilde{B}:=C_{0}\sqcup\\{c_{B}\\}$. The element $c_{B}$ should be
considered as the result of identifying all in $C_{1}$ into a single element,
namely $c_{B}$.

Let us consider a tuple
$\tilde{\mathbf{t}}=(b_{1},\ldots,b_{k+p-1})\in\tilde{B}^{k+p-1}$. Denote by
$\mathcal{I}_{\tilde{\mathbf{t}}}\subseteq[k+p-1]$ the set of indices such
that $b_{i}=c_{B}$ in $\tilde{\mathbf{t}}$. Denote by
$\mathcal{C}_{\tilde{\mathbf{t}}}\subseteq G^{k+p-1}$ the class of all tuples
$(x_{1},\ldots,x_{k+p-1})\in\tilde{G}^{k+p-1}$ such that

$\forall
i\in[k+p-1]\colon\left(i\in\mathcal{I}_{\tilde{\mathbf{t}}}\Rightarrow
x_{i}\in C_{1}\right)\
\wedge\left(i\notin\mathcal{I}_{\tilde{\mathbf{t}}}\Rightarrow
b_{i}=x_{i}\right).$

The interpretation $R^{\tilde{\mathbf{B}}}$ is defined as follows, here
$\bigvee$ denotes the join operation w.r.t. $\preceq_{\star}$:

(7)
$R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})=\bigvee_{(x_{1},\ldots,x_{k+p-1})\in\mathcal{C}_{\tilde{\mathbf{t}}}}R^{\tilde{\mathbf{G}}}(x_{1},\ldots,x_{k+p-1}).$

Observe that we can construct $\tilde{\mathbf{B}}$ in time polynomial in the
size of the input $\tilde{\mathbf{G}}$.

Let us check the property 1, that $\tilde{\mathbf{G}}\to\tilde{\mathbf{B}}$.
Let us consider a map $\pi\colon\tilde{G}\to\tilde{B}$ s.t.

  * •

if $x\in C_{1}$, then $\pi(x)=c_{B}$;

  * •

if $x\in C_{0}$, then $\pi(x)=x$.

Consider a tuple
$\tilde{\mathbf{x}}=(x_{1},\ldots,x_{k+p-1})\in\tilde{G}^{k+p-1}$ and
$\pi(\tilde{\mathbf{x}})=(b_{1},\ldots,b_{k+p-1})\in\tilde{B}^{k+p-1}$ where

  * •

$b_{i}=c_{B}$, if $x_{i}\in C_{1}$;

  * •

$b_{i}=x_{i}$, otherwise.

As $\tilde{\mathbf{x}}\in\mathcal{C}_{\pi(\tilde{\mathbf{x}})}$, by eq. 7 we
have
$R^{\tilde{\mathbf{G}}}(\tilde{\mathbf{x}})\preceq_{\star}R^{\tilde{\mathbf{B}}}(\pi(\tilde{\mathbf{x}}))$.
This proves that $\pi$ is a homomorphism.

Let us check the property 2, that
$\tilde{\mathbf{G}}\to\tilde{\mathbf{A}}\Leftrightarrow\tilde{\mathbf{B}}\to\tilde{\mathbf{A}}$.
As $\tilde{\mathbf{G}}\to\tilde{\mathbf{B}}$, we need to show only one
direction, i.e. $\Rightarrow$. Assume that there is
$h_{G}\colon\tilde{\mathbf{G}}\to\tilde{\mathbf{A}}$ – a homomorphism. Observe
that, for all $x$, $x\in C_{1}\Leftrightarrow h_{G}(x)=c_{A}$. We define a map
$h_{B}$ as follows:

  * •

if $x=c_{B}$, then $h_{B}(x)=c_{A}$;

  * •

if $x\not=c_{B}$, then $h_{B}(x)=h_{G}(x)$.

Consider a tuple
$\tilde{\mathbf{t}}=(b_{1},\ldots,b_{k+p-1})\in\tilde{B}^{k+p-1}$. Observe
that $h_{B}(\tilde{\mathbf{t}})=h_{G}(\mathcal{C}_{\tilde{\mathbf{t}}})$ that
is any tuple from $\mathcal{C}_{\tilde{\mathbf{t}}}$ is mapped to
$h_{B}(\tilde{\mathbf{t}})$ by $h_{G}$. We know that

$R^{\tilde{\mathbf{A}}}(h_{B}(\tilde{\mathbf{t}}))\succeq_{\star}R^{\tilde{\mathbf{G}}}(x_{1},\ldots,x_{k+p-1})$

for all $(x_{1},\ldots,x_{k+p-1})\in\mathcal{C}_{\tilde{\mathbf{t}}}$. Thus,

$R^{\tilde{\mathbf{A}}}(h_{B}(\tilde{\mathbf{t}}))\succeq_{\star}\bigvee_{(x_{1},\ldots,x_{k+p-1})\in\mathcal{C}_{\tilde{\mathbf{t}}}}R^{\tilde{\mathbf{G}}}(x_{1},\ldots,x_{k+p-1})=R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}}).$

This shows that $h_{B}$ is a homomorphism.

Finally, we need to check the property 3 to finish the proof. Recall that we
split all the tuples $(b_{1},\ldots,b_{k+p-1})\in\tilde{B}^{k+p-1}$ into three
classes: $\mathcal{B}_{1},\mathcal{B}_{2},\mathcal{B}_{3}$. Observe that for
any homomorphism $h:\tilde{\mathbf{B}}\to\tilde{\mathbf{A}}$, we have that for
any $x\in\tilde{B}$, $(x=c_{B}\Leftrightarrow h(x)=c_{A})$; then, for any
$j\in[3]$, $h(\mathcal{B}_{j})\subseteq\mathcal{A}_{j}$. At first, we look at
the tuple $\tilde{\mathbf{t}}=(c_{B},\ldots,c_{B})\in\mathcal{B}_{2}$. By eqs.
6 and 7, we know that
$R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})\succeq_{\star}1$. If
$R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})=\star$, then we output some fixed
NO input instance of $\textrm{MP}_{\star}^{\sigma}(\mathbf{A})$ for
$\tilde{\mathbf{G}}$. If $R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})=1$, then
we continue.

Now, we look at every tuple $\tilde{\mathbf{t}}\in\mathcal{B}_{3}$ and check
whether $R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})=0$. If there exists
$\tilde{\mathbf{t}}\in\mathcal{B}_{3}$ such that
$R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})\not=0$, then we output some fixed
NO input instance of $\textrm{MP}_{\star}^{\sigma}(\mathbf{A})$ for
$\tilde{\mathbf{G}}$. If, for all tuples of $\mathcal{B}_{3}$, we have that
$R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}})=0$, then we continue. We can do
all these checks in time polynomial in $|\tilde{G}|$.

Now we can assume that $R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}}_{2})=1$ and
$R^{\tilde{\mathbf{B}}}(\tilde{\mathbf{t}}_{3})=0$, for all
$\tilde{\mathbf{t}}_{2}\in\mathcal{B}_{2},\tilde{\mathbf{t}}_{3}\in\mathcal{B}_{3}$.
We are ready to construct the $({\star},\sigma)$-structure $\mathbf{B}$:

  * •

the domain $B$ of $\mathbf{B}$ is $\tilde{B}\setminus\\{c_{B}\\}$;

  * •

for any relation $R_{i}\in\sigma$ and any tuple
$\mathbf{t}=(b_{1},\ldots,b_{k_{i}})\in B^{k_{i}}$ it is interpreted as
follows:

(8)
$R^{\mathbf{B}}_{i}(\mathbf{t})=R^{\tilde{\mathbf{B}}}(\underbrace{c_{B},\ldots,c_{B}}_{i-1},\mathbf{t},\underbrace{c_{B},\ldots,c_{B}}_{k+p-k_{i}-i}).$

If we apply the $\tilde{(\cdot)}$-transformation to this
$({\star},\sigma)$-structure $\mathbf{B}$, then we will get
$\tilde{\mathbf{B}}$, because for all tuples of
$\mathcal{B}_{2},\mathcal{B}_{3}$: $R^{\tilde{\mathbf{B}}}$ always has values
1 and 0 correspondingly, and for all tuples of $\mathcal{B}_{1}$ there is a
bijective correspondence with the tuples of all $R_{i}\in\sigma$, the
equivalence of their values is provided by eqs. 5 and 8. By Lemma 5.3,
$\mathbf{B}\to\mathbf{A}$ if and only if
$\tilde{\mathbf{B}}\to\tilde{\mathbf{A}}$. We have shown that, for any
$({\star},\tilde{\sigma})$-structure $\tilde{\mathbf{G}}$, we can find in time
polynomial in $|\tilde{G}|$ a $({\star},\sigma)$-structure $\mathbf{B}$ such
that
$\tilde{\mathbf{G}}\to\tilde{\mathbf{A}}\Leftrightarrow\tilde{\mathbf{B}}\to\tilde{\mathbf{A}}$.
Thus $\textrm{MP}_{\star}^{\tilde{\sigma}}(\tilde{\mathbf{A}})$ reduces in
polynomial time to $\textrm{MP}_{\star}^{\sigma}(\mathbf{A})$. ∎

Lemma 5.3 and Lemma 5.4 provide the following statement about the P-NP-
complete dichotomy property.

######  Theorem 5.5.

If the class of problems $\textrm{MP}_{\star}^{\tilde{\sigma}}$ has a
dichotomy, then the class $\textrm{MP}_{\star}^{\sigma}$ has a dichotomy.

Observe that in order to prove the other direction, for every
$({\star},\tilde{\sigma})$-structure $\mathbf{A}$, we have to find a
$({\star},\sigma)$-structure $\hat{\mathbf{A}}$ such that
$\textrm{MP}_{\star}^{\sigma}(\hat{\mathbf{A}})$ and
$\textrm{MP}_{\star}^{\tilde{\sigma}}(\mathbf{A})$ are P-time equivalent. We
show in the next section the difficulties to obtain such a reduction.

The dichotomy implications between the considered classes are displayed on the
Figure 1. One can see now that the existence of a dichotomy for
$\textrm{MP}^{\tilde{\sigma}}$ implies such existence for all other classes
considered on the figure.

Figure 1. Each arrow shows an implication of the existence of a dichotomy,
i.e. if the class at the tail has a dichotomy, then the class at the head has
it. The vertical ones are shown in Section 4, and the horizontal ones are
shown in Section 5.

###  5.3. From one relation to directed graphs

In this section we do not prove that for any
$({\star},\tilde{\sigma})$-structure $\mathbf{H}$, with $\tilde{\sigma}$
consisting of one single symbol, there exists a $\star$-graph $\mathbf{H}_{2}$
such that the two problems $\textrm{MP}_{\star}^{\tilde{\sigma}}(\mathbf{H})$
and $\textrm{MP}_{\star}(\mathbf{H}_{2})$ are P-time equivalent. However, we
will discuss some necessary conditions for the existence of such a reduction.
And also we will discuss why approaches that are similar to the one used in
[10, 18] cannot be applied to the homomorphism problems considered in this
paper, in particular, Matrix Partition Problems.

For the simplicity of the notations, we will consider the reduction from
$\tilde{\sigma}=\\{R(\cdot,\cdot,\cdot)\\}$ to $\star$-graphs. In the very
beginning, we are going to show that if there exists such a correspondence
between $({\star},\tilde{\sigma})$-structures and $\star$-graphs, then the
size of the domain of the constructed $\star$-graph must be significantly
greater than the one of the corresponding ternary $\star$-structure.

Let $\mathcal{G}_{2}^{n}$ be the class of all $\star$-graphs on $n$ elements
that are cores and pairwise not homomorphically equivalent. Recall that a core
$\mathbf{G}\in\mathcal{G}_{2}^{n}$ cannot have an element $x$ with
$E^{\mathbf{G}}(x,x)=\star$. Let $\mathcal{G}_{3}^{n}$ be the class of
$({\star},\tilde{\sigma})$-structures with the same property.

######  Lemma 5.6.

For every positive integer $n$,
$|\mathcal{G}_{3}^{n}|\geq|\mathcal{G}_{2}^{n}|\cdot 3^{n(n-1)^{2}-1}$.

###### Proof.

We suppose that all $\mathbf{G}\in\mathcal{G}_{2}^{n}$ have the same domain
$\\{a,x_{1},\ldots,x_{n-1}\\}$, we fix one element $a$, and linearly order the
elements from $\\{x_{1},\ldots,x_{n-1}\\}$ with $x_{i}<x_{j}$ if $i<j$. Let
$\mathbf{G}\in\mathcal{G}_{2}^{n}$. We will construct a family of
$({\star},\tilde{\sigma})$-structures $\mathcal{G}_{\mathbf{G}}$ of size
$3^{n(n-1)^{2}-1}$ such that every two $({\star},\tilde{\sigma})$-structures
from there will not be homomorphically equivalent. We will construct such a
class for every $\star$-graph in $\mathcal{G}_{2}^{n}$, and then show that any
two structures from different classes will not be homomorphically equivalent
as well.

Any $\mathbf{G}_{3}\in\mathcal{G}_{\mathbf{G}}$ must satisfy the following
properties:

  * •

the domain is the same as the one of $\mathbf{G}$:
$G_{3}=G=\\{a,x_{1},\ldots,x_{n-1}\\}$;

  * •

for all $x,y\in G_{3}\colon R^{\mathbf{G}_{3}}(a,x,y)=E^{\mathbf{G}}(x,y)$ –
we define all the relations of $\mathbf{G}$ using only the triples that have
$a$ on the first coordinate;

  * •

for all $x\in G_{3}\setminus\\{a\\}\colon
R^{\mathbf{G}_{3}}(x,x,x)=1-E^{\mathbf{G}}(a,a)$ – all the elements other than
$a$ have the value on the loop, that is different from the loop
$R^{\mathbf{G}_{3}}(a,a,a)=E^{\mathbf{G}}(a,a)$; the _loop property_

  * •

for all $i,j\in[n]$, $R^{\mathbf{G}_{3}}(x_{i},x_{j},a)=\star$ if $i<j$ and
$R^{\mathbf{G}_{3}}(x_{i},x_{j},a)=0$ if $i\geq j$; the _linear ordering
property_

  * •

fix one $(x_{i_{1}},x_{i_{2}},x_{i_{3}})\in(G_{3}\setminus\\{a\\})^{3}$, such
that the number $i_{1},i_{2},i_{3}$ are not all equal, and set
$R^{\mathbf{G}_{3}}(x_{i_{1}},x_{i_{2}},x_{i_{3}})=\star$.

The values are restricted for the $n^{2}$ tuples that correspond to the edges
of $\mathbf{G}$, for the $(n-1)^{2}$ tuples of the linear ordering, and for
the $(n-1)$ loops, and for the triple $(x_{i_{1}},x_{i_{2}},x_{i_{3}})$. For
any other triple $(x,y,z)\in G^{3}$, there is no restriction on the value of
$R^{\mathbf{G}_{3}}$ among $\\{0,1,\star\\}$. Thus,

$|\mathcal{G}_{\mathbf{G}}|=3^{n^{3}-n^{2}-(n-1)^{2}-(n-1)-1}=3^{n(n-1)^{2}-1}.$

Let us consider $\mathbf{A},\mathbf{B}\in\mathcal{G}_{\mathbf{G}}$, suppose
that there is a homomorphism $h\colon\mathbf{A}\to\mathbf{B}$, then $h(a)=a$
and for all $x\not=a$, $h(x)\not=a$ by the loop property of $\mathbf{G}_{3}$.
Also, by the linear ordering property, we have that for all $x\in A$,
$h(x)=x$. But these two structures differ on at least one tuple, this is a
contradiction.

Let us consider
$\mathbf{A}_{1}\in\mathcal{G}_{\mathbf{G}_{1}},\mathbf{A}_{2}\in\mathcal{G}_{\mathbf{G}_{2}}$
– structures from different classes of two $\star$-graphs
$\mathbf{G}_{1},\mathbf{G}_{2}$ that are not hom-equivalent. Suppose that
there is no homomorphism from $\mathbf{G}_{1}$ to $\mathbf{G}_{2}$ and there
is a homomorphism $h\colon\mathbf{A}_{1}\to\mathbf{A}_{2}$. If
$E^{\mathbf{G}_{1}}(a,a)\not=E^{\mathbf{G}_{2}}(a,a)$, then by the loop
property, for all $x\in A_{1}\setminus\\{a\\}$, $h(x)=a$, this is a
contradiction as $E^{\mathbf{G}_{2}}(a,a)\not=\star$ on one hand and
$\star=R^{\mathbf{A}_{1}}(x_{i_{1}},x_{i_{2}},x_{i_{3}})\preceq_{\star}R^{\mathbf{A}_{2}}(a,a,a)=E^{\mathbf{G}_{2}}(a,a)$
on the other hand. Thus, we assume that
$E^{\mathbf{G}_{1}}(a,a)=E^{\mathbf{G}_{2}}(a,a)$ and that $h(a)=a$ and, for
all $x\not=a$, $h(x)\not=a$ (again by the loop property), but, by the linear
ordering property, we must have that $h(x)=x$. The homomorphism $h$ implies
that the identity mapping on the set $G=\\{a,x_{1},\ldots,x_{n-1}\\}$ is a
homomorphism from $\mathbf{G}_{1}$ to $\mathbf{G}_{2}$ that is a contradiction
as $\mathbf{G}_{1}$ and $\mathbf{G}_{2}$ are pairwise not homomorphically
equivalent.

This proves that we are able to construct at least $|\mathcal{G}_{2}^{n}|\cdot
3^{n(n-1)^{2}-1}$ $({\star},\tilde{\sigma})$-structures such that any two of
them are not homomorphically equivalent. ∎

This lemma ensures that when we make a correspondence between ternary and
binary structures, in the general case we need to add a lot of elements to the
binary one.

######  Corollary 5.7.

Let $n,m\in\mathbb{N}$. If $|\mathcal{G}_{3}^{n}|<|\mathcal{G}_{2}^{m}|$, then
$m>\sqrt{n(n-1)^{2}-1}$.

###### Proof.

The number of all possible ways to assign one of three values to each of the
$m^{2}$ pairs equals $3^{m^{2}}$. Then, by Lemma 5.6:

$3^{m^{2}}\geq|\mathcal{G}_{2}^{m}|>|\mathcal{G}_{3}^{n}|\geq
3^{n(n-1)^{2}-1}|\mathcal{G}_{2}^{n}|\geq 3^{n(n-1)^{2}-1}\Rightarrow
m^{2}>n(n-1)^{2}-1.$

∎

We will argue that all the approaches similar to the one used in [10] do not
work for the case of $\textrm{MP}_{\star}$ (equivalently MP, see Section 4).
Such an approach can be described by these steps: for any
$({\star},\tilde{\sigma})$-structure $\mathbf{H}_{3}$ the corresponding
$\star$-graph $\mathbf{H}_{2}$ is constructed as follows:

  1. (1)

take the same domain $H_{2}=H_{3}$ and

  2. (2)

substitute every tuple $R^{\mathbf{H}_{3}}(x_{1},x_{2},x_{3})$ by a
$\star$-graph $\mathbf{T}^{v}_{x_{1}x_{2}x_{3}}$ for $v\in\\{0,1,\star\\}$
that contains only these 3 elements $x_{1},x_{2},x_{3}$ among those of
$H_{3}$. Letter $\mathbf{T}$ stands for “tuple” and the superscript $v$ is for
“value”. It is required that for two different tuples $\mathbf{t_{1}}$ and
$\mathbf{t_{2}}$, the domains of $\mathbf{T}^{v_{1}}_{\mathbf{t_{1}}}$ and of
$\mathbf{T}^{v_{1}}_{\mathbf{t_{2}}}$ intersect only on $H_{3}$.

So, the domain of $\mathbf{H}_{2}$ is the union of the domain $H_{3}$ of the
$({\star},\tilde{\sigma})$-structure $\mathbf{H}_{3}$ and the domains of all
the $\star$-graphs $\mathbf{T}^{v}$ that represent the tuples of
$\mathbf{H}_{3}$:

$H_{2}=H_{3}\cup\bigcup_{(x_{1},x_{2},x_{3})\in H_{3}^{3},\
R^{\mathbf{H_{3}}}(x_{1},x_{2},x_{3})=v}T^{v}_{x_{1}x_{2}x_{3}}.$

This union is not disjoint because each $\mathbf{T}^{v}$ contains elements of
$H_{3}$.

In [10] every such $\mathbf{T}^{v}$ was a balanced directed graph obtained
from the star with three leaves by subdividing each edge $p$ times, for some
$p$, the leaves being the elements of $H_{3}$. So, during the reduction from
CSP on directed graphs to $\textrm{CSP}^{\tilde{\sigma}}$, it was clear which
elements of the input directed graph correspond to the elements of the domain
of the $\tilde{\sigma}$-structure from which this directed graph is reduced.
We generalise this constructive approach by the conditions applied to
$\mathbf{H}_{2}$:

  1. (1)

For each $\star$-graph $\mathbf{T}^{v}_{x_{1}x_{2}x_{3}}$ that represents a
tuple $R^{\mathbf{H}_{3}}(x_{1},x_{2},x_{3})=v$, the problem
$\textrm{MP}_{\star}(\mathbf{T}^{v}_{x_{1}x_{2}x_{3}})$ is solvable in P-time
and
$v_{x}=R^{\mathbf{H}_{3}}(x_{1},x_{2},x_{3})\preceq_{\star}R^{\mathbf{H}_{3}}(y_{1},y_{2},y_{3})=v_{y}$
if and only if
$\mathbf{T}^{v_{x}}_{x_{1}x_{2}x_{3}}\to\mathbf{T}^{v_{y}}_{y_{1}y_{2}y_{3}}$.

  2. (2)

Let $\mathbf{H}_{2},\mathbf{H}_{2}^{\prime}$ be two $\star$-graphs obtained
from $({\star},\tilde{\sigma})$-structures
$\mathbf{H}_{3},\mathbf{H}_{3}^{\prime}$ by this approach. Then, for any
homomorphism $h\colon\mathbf{H}_{2}\to\mathbf{H}_{2}^{\prime}$, it is true
that for all $x\in H_{2}$, $x\in H_{3}\subseteq H_{2}\Leftrightarrow h(x)\in
H_{3}^{\prime}\subseteq H_{2}^{\prime}$.

  3. (3)

For each $\star$-graph $\mathbf{A}$ that is an input instance of
$\textrm{MP}_{\star}(\mathbf{H}_{2})$, one can decide in time polynomial in
$|A|$ which elements of $\mathbf{A}$ can only map to the elements of $H_{3}$.
That is, we can decide, for every $x\in A$, if any
$h\colon\mathbf{A}\to\mathbf{H}_{2}$, implies that $h(x)\in H_{3}\subset
H_{2}$. Also, for every $x\in A$, either any homomorphism from
$\mathbf{A}\to\mathbf{H}_{2}$ maps $x$ to $H_{3}$, or any homomorphism from
$\mathbf{A}\to\mathbf{H}_{2}$ maps $x$ to $H_{2}\setminus H_{3}$.

  4. (4)

For two elements $w,w^{\prime}\in H_{2}$ such that $w,w^{\prime}\notin H_{3}$
and $w,w^{\prime}$ do not belong to the same $T^{v}_{xyz}$, then
$E^{\mathbf{H}_{2}}(w,w^{\prime})=0$.

  5. (5)

Let $\mathbf{A}$ be a $\star$-graph. Suppose that for some $v\not=v^{\prime}$
there is $h\colon\mathbf{A}\to\mathbf{T}^{v}_{xyz}$ and
$\mathbf{A}\not\to\mathbf{T}^{v^{\prime}}_{xyz}$. Suppose that, for every
$a_{0},a_{n}\in A$ such that $h(a_{0}),h(a_{n})\in\\{x,y,z\\}$, there exist
$a_{1},\ldots,a_{n-1}\in A$ such that:

     * •

for every $1\leq i<n$, $h(a_{i})\not\in\\{x,y,z\\}$,

     * •

for every $0\leq i<n$, $E^{\mathbf{A}}(a_{i},a_{i+1})\not=0$ or
$E^{\mathbf{A}}(a_{i+1},a_{i})\not=0$.

Then, for any other $h^{\prime}\colon\mathbf{A}\to\mathbf{T}^{v}_{xyz}$ and
for all $a\in A$ such that $h(a)\in\\{x,y,z\\}$, we have that
$h(a)=h^{\prime}(a)$.

In particular, the reduction from $\textrm{CSP}^{\sigma}$ to CSP on directed
graphs in [10] satisfies the first four conditions. The fifth one cannot be
applied to CSP because there are no three different types of $\mathbf{T}^{v}$
in that case. Any polynomial time reduction satisfying these five conditions,
cannot prove the P-equivalence with $\star$-graphs, unless CSP is P-time
equivalent to MP. We assume that CSP is equivalent to
$\textrm{MP}_{\varnothing}$ by Section 3.

######  Proposition 5.8.

Let a $\star$-graph $\mathbf{H}_{2}$ be constructed from some
$({\star},\tilde{\sigma})$-structure $\mathbf{H}_{3}$ and satisfy all the five
conditions above. Then $\textrm{MP}_{\star}^{\tilde{\sigma}}(\mathbf{H}_{3})$
reduces in P-time to $\textrm{MP}_{\star}(\mathbf{H}_{2})$, and
$\textrm{MP}_{\star}(\mathbf{H}_{2})$ reduces in P-time to
$\textrm{MP}_{\varnothing}^{\tilde{\sigma}}(\mathbf{H}_{3})$.

###### Proof.

Consider $({\star},\tilde{\sigma})$-structures $\mathbf{G}_{3},\mathbf{H}_{3}$
and the corresponding $\star$-graphs $\mathbf{G}_{2}$ and $\mathbf{H}_{2}$
that satisfy the conditions 1–5. If there is
$h\colon\mathbf{G}_{3}\to\mathbf{H}_{3}$, then, by the conditions 1 and 2,
there is $h_{2}\colon\mathbf{G}_{2}\to\mathbf{H}_{2}$. If there is
$h_{2}\colon\mathbf{G}_{2}\to\mathbf{H}_{2}$, then, by the condition 2, one
can consider the restriction $h$ of this map on the set $G_{3}$, and the
codomain of this map will be the set $H_{3}$. By the condition 1, $h$ is a
homomorphism between $\mathbf{G}_{3}$ and $\mathbf{H}_{3}$.

Now, consider any $\star$-graph $\mathbf{A}$ from the input of
$\textrm{MP}_{\star}(\mathbf{H}_{2})$. By the condition 3, we can mark in
P-time all the elements that can map only to the elements of $H_{3}$, denote
the set containing them by $A_{3}$. Then on the set $A\setminus A_{3}$ we
define the following equivalence relation $eq(\cdot,\cdot)$: for two elements
$a_{0},a_{n}\in A\setminus A_{3}$, we say that $eq(a_{0},a_{n})$ if there
exists a sequence of elements $a_{0},a_{1},\ldots,a_{n-1},a_{n}\in A\setminus
A_{3}$ such that for any $0\leq i<n$, either
$E^{\mathbf{A}}(a_{i},a_{i+1})\not=0$ or
$E^{\mathbf{A}}(a_{i+1},a_{i})\not=0$. For every $eq$-equivalence class
$A_{a}$ (containing an element $a$), consider an induced $\star$-subgraph
$\mathbf{A}_{a}$ on the subset consisting of $A_{a}$ itself together with
those $b\in A_{3}$ such that there exists $c\in A_{a}$ such that either
$E^{\mathbf{A}}(b,c)\not=0$ or $E^{\mathbf{A}}(b,c)\not=0$. Below we will show
that the image of every $\mathbf{A}_{a}$ can only be contained in some
$\mathbf{T}^{v}_{xyz}$.

######  Claim 5.8.1.

If there is $h\colon\mathbf{A}_{a}\to\mathbf{H}_{2}$, then
$h({A}_{a})\subseteq{T}^{v}_{xyz}$ for some $\mathbf{T}^{v}_{xyz}$.

###### Proof of Claim 5.8.1.

For any two elements $a_{0},a_{n}$ of the $eq$-equivalence class $A_{a}$,
there exists a sequence $a_{1},\ldots,a_{n-1}$ of elements of $A_{a}$ such
that, for any $0\leq i\leq n-1$, one of $E^{\mathbf{A}}(a_{i},a_{i+1})$ and
$E^{\mathbf{A}}(a_{i+1},a_{i})$ is not $0$. As for all $a\in A\setminus A_{3}$
and for all $h^{\prime}\colon\mathbf{A}\to\mathbf{H}_{2}$,
$h^{\prime}(a)\not\in H_{3}$, $h(a_{0}),\ldots,h(a_{n})\in H_{2}\setminus
H_{3}$ (by condition (3)). Then, by the condition 4, that is in
$\mathbf{H}_{2}$ any two elements $w$ and $w^{\prime}$ belonging to different
$\mathbf{T}^{v},\mathbf{T}^{v^{\prime}}$,
$E^{\mathbf{H}_{2}}(w,w^{\prime})=0$, we have that all
$h(a_{0}),\ldots,h(a_{n})$ are in the same $\mathbf{T}^{v}$. ∎

By the condition 1, we find in P-time for every $\mathbf{A}_{a}$ the list of
values $v\in\\{0,1,\star\\}$ such that $\mathbf{A}_{a}$ maps to
$\mathbf{T}^{v}_{xyz}$. If $\mathbf{A}_{a}\not\to\mathbf{T}^{v}_{xyz}$ for any
$v$, then there is no way that $\mathbf{A}$ can be mapped to $\mathbf{H}_{2}$
and we reject this instance. Among all $v$ such that
$\mathbf{A}_{a}\to\mathbf{T}^{v}$, we label $\mathbf{A}_{a}$ with the smallest
possible such $v$ with respect to $\preceq_{\star}$. If $\mathbf{A}_{a}$ maps
to $\mathbf{T}^{v}_{xyz}$ for any possible $v$, then we say that
$\mathbf{A}_{a}$ is $\varnothing$-labelled. Introduce a new equivalence
relation $map(\cdot,\cdot)$ on the set $A_{3}$, we say that $map(a_{1},a_{2})$
if there exists $\mathbf{A}_{a}\ni a_{1},a_{2}$ and there is
$h\colon\mathbf{A}_{a}\to\mathbf{T}^{v}$ such that $h(a_{1})=h(a_{2})$. By the
condition 5, for any $a_{1},a_{2}\in A_{3}$ such that $map(a_{1},a_{2})$:
there is $h\colon\mathbf{A}\to\mathbf{H}_{2}\Rightarrow h(a_{1})=h(a_{2})$.
Let us construct a new $\star$-graph $\mathbf{A}_{2}$ based on $\mathbf{A}$.
Take the domain $A_{2}=A_{3}/map$ and, for any
$(a_{1},a_{2},a_{3})\in(A_{2})^{3}$, add a gadget
$\mathbf{T}_{a_{1}a_{2}a_{3}}^{v}$ following the rules below. Consider
$\mathbf{A}_{a}$ labelled with $v\not=\varnothing$ such that for any element
$x\in H_{3}$ (or $y$ or $z$) of $\mathbf{T}^{v}_{xyz}$ there exists an
$A_{3}$-element $a_{x}$ of $\mathbf{A}_{a}$ such that $a_{x}$ is mapped to
$x$. In this case we substitute $\mathbf{A}_{a}$ by
$\mathbf{T}^{v}_{a_{x}a_{y}a_{z}}$ for $a_{x},a_{y},a_{z}\in A_{2}$. Consider
those $\mathbf{A}_{a}$ labelled with $v\not=\varnothing$ where there exists an
element $x\in H_{3}$ (or $y$ or $z$) of $\mathbf{T}^{v}_{xyz}$ so that no
element $a_{x}$ of $\mathbf{A}_{a}$ maps to $x$. For such a case we add to
$A_{2}$ a new element $a_{\mathbf{A}_{a},x}$ and substitute $\mathbf{A}_{a}$
by $\mathbf{T}^{v}$ for the corresponding 3 elements of $A_{2}$. All the
$eq$-equivalence classes $A_{a}$ labelled with $\varnothing$ are not
substituted with anything in $\mathbf{A}_{2}$. The $\star$-graph
$\mathbf{A}_{2}$ corresponds to a $({\varnothing},\tilde{\sigma})$-structure
$\mathbf{A}_{3}$ as follows: each triple $a_{1},a_{2},a_{3}$ of $A_{3}$ is
either contained in $\mathbf{T}^{v}_{a_{1}a_{2}a_{3}}$ or not. If yes, then we
set $R^{\mathbf{A}_{3}}(a_{1},a_{2},a_{3})=v$, if not, then
$R^{\mathbf{A}_{3}}(a_{1},a_{2},a_{3})=\varnothing$. It is routine to check
now that $\mathbf{A}\to\mathbf{H_{2}}$ if and only if
$\mathbf{A_{3}}\to\mathbf{H_{3}}$. ∎

##  6\. Obstructions

We prove in this section that the inclusion-minimal obstructions considered in
[17] coincide with finite duality in $\textrm{Cat}_{01}$. We also show that
being characterised by a finite set of inclusion-minimal obstructions in
$\textrm{Cat}_{01}$ is equivalent to be characterised by a finite set of
inclusion-minimal obstructions in $\textrm{Cat}_{\star}$. The main results of
this section are summarised in the following.

######  Theorem 6.1.

Let $\mathbf{H}$ be a $\star$-structure. Then, the following are equivalent.

  1. (1)

$\textrm{Obs}_{01}^{\to}(\mathbf{H})$ is finite.

  2. (2)

$\textrm{Obs}_{01}^{\subset}(\mathbf{H})$ is finite.

  3. (3)

$\textrm{Obs}_{\star}^{\to}(\mathbf{H})$ is finite.

  4. (4)

$\textrm{Obs}_{\star}^{\subset}(\mathbf{H})$ is finite.

Throughout this section, let $\sigma=\\{R_{1},\ldots,R_{p}\\}$ be a fixed
signature. We recall that, for $*\in\\{01,\star,\varnothing\\}$,
$\textrm{Cat}_{*}$ is the set of all $({*},\sigma)$-structures.

Let us now recall the definition of obstructions from [17], that we extend to
all structures.

######  Definition 6.2 ([17]).

Let $*\in\\{01,\star,\varnothing\\}$ and let $\mathbf{H}$ be a
$\star$-structure. A $*$-structure $\mathbf{G}$ is called an _inclusion-
minimal obstruction_ for $\textrm{MP}_{*}(\mathbf{H})$ if
$\mathbf{G}\not\to\mathbf{H}$ and for all $v\in G$,
$\mathbf{G}\setminus\\{v\\}\to\mathbf{H}$. The set of all obstructions for the
problem $\textrm{MP}_{*}(\mathbf{H})$ is denoted by
$\textrm{Obs}_{*}^{\subset}(\mathbf{H})$.

We propose below another definition, that uses homomorphisms.

######  Definition 6.3.

Let $*\in\\{01,\star,\varnothing\\}$ and let $\mathbf{H}$ be a
$\star$-structure. A $*$-structure $\mathbf{G}$ is called a _hom-minimal
obstruction_ for a problem $\textrm{MP}_{*}(\mathbf{H})$ if (1) $\mathbf{G}$
is a core and $\mathbf{G}\not\to\mathbf{H}$, and (2) for every
$\mathbf{G}^{\prime}$ such that $\mathbf{G}^{\prime}\to\mathbf{G}$ and
$\mathbf{G}\not\to\mathbf{G}^{\prime}$, we have that
$\mathbf{G}^{\prime}\to\mathbf{H}$. The set of all hom-minimal obstructions
for $\textrm{MP}_{*}(\mathbf{H})$ is denoted by
$\textrm{Obs}_{*}^{\to}(\mathbf{H})$.

We prove in this section that one obstruction set is finite if and only if the
other is, and consider also the equivalences between different categories. We
summarise in Figure 2 all the equivalences that we have proved.

Figure 2. Every arrow of this diagram states that : if the class at the tail
is finite, then the class at the head is finite.

Let us first prove that on $\textrm{Cat}_{01}$ the two obstruction sets
coincide. Before, let us notice the following.

######  Observation 6.4.

Any hom-minimal obstruction is inclusion-minimal.

###### Proof.

Let $\mathbf{H}$ be a $\star$-structure, and let
$*\in\\{01,\star,\varnothing\\}$. Suppose that
$\mathbf{G}\in\textrm{Obs}_{*}^{\to}(\mathbf{H})$. Consider any proper induced
substructure $\mathbf{G}^{\prime}$ of $\mathbf{G}$. Then,
$\mathbf{G}\not\to\mathbf{G}^{\prime}$ (recall $\mathbf{G}$ is a core), and so
$\mathbf{G}^{\prime}\to\mathbf{H}$. Then
$\mathbf{G}\in\textrm{Obs}_{*}^{\subset}(\mathbf{H})$. ∎

######  Proposition 6.5.

$\textrm{Obs}_{01}^{\subset}(\mathbf{H})=\textrm{Obs}_{01}^{\to}(\mathbf{H})$.

###### Proof.

We have that
$\textrm{Obs}_{01}^{\subset}(\mathbf{H})\subseteq\textrm{Obs}_{01}^{\to}(\mathbf{H})$
by Observation 6.4. For the other direction, let $\mathbf{G}$ be an inclusion-
minimal $01$-obstruction. First, $\mathbf{G}$ is a core, otherwise it contains
a strict induced substructure that does not map to $\mathbf{H}$, a
contradiction. Assume now that $\mathbf{G}$ is not hom-minimal. Then, there
exists a $01$-structure $\mathbf{G}_{1}$ that is a core and there is
$h\colon\mathbf{G}_{1}\to\mathbf{G}$, and $\mathbf{G}\not\to\mathbf{G}_{1}$,
and both $\mathbf{G},\mathbf{G}_{1}$ do not map to $\mathbf{H}$. Let
$G^{\prime}=h(G_{1})$ and let $\mathbf{G^{\prime}}$ be the substructure of
$\mathbf{G}$ induced by $G^{\prime}$. If $\mathbf{G^{\prime}}$ is a proper
induced substructure of $\mathbf{G}$, then by the assumption of inclusion-
minimality, and by transitivity of homomorphism: $\mathbf{G}_{1}\to\mathbf{H}$
– a contradiction. Thus, $h(G_{1})=G$, but since $h$ is a full homomorphism,
we have that $\mathbf{G}$ is either a proper induced substructure of
$\mathbf{G}_{1}$, which would contradict our assumption that $\mathbf{G}_{1}$
is a core, or is isomorphic to $\mathbf{G_{1}}$, which would contradict the
assumption that $\mathbf{G}\not\to\mathbf{G_{1}}$. We can then conclude that
$\mathbf{G}$ is hom-minimal. ∎

The following proposition shows that if $\mathbf{H}\in\textrm{Cat}_{01}$, then
these two classes are not the same:
$\textrm{Obs}_{\star}^{\subset}(\mathbf{H})\neq\textrm{Obs}_{\star}^{\to}(\mathbf{H})$.

######  Proposition 6.6.

For all $01$-structures $\mathbf{H}$,
$\textrm{Obs}_{\star}^{\subset}(\mathbf{H})\neq\textrm{Obs}_{\star}^{\to}(\mathbf{H})$.

###### Proof.

By Proposition 6.5, we only need to find a counterexample among
$\star$-structures. For simplicity, let us assume that $\mathbf{H}$ is a
$01$-graph and let $x\in H$. Consider a $\star$-graph
$\mathbf{G}=(\\{u,v\\},E^{\mathbf{G}})$ with
$E^{\mathbf{G}}(u,u)=E^{\mathbf{G}}(v,v)=E^{\mathbf{H}}(x,x)$ and
$E^{\mathbf{G}}(u,v)=E^{\mathbf{G}}(v,u)=\star$. Also consider a $\star$-graph
$\mathbf{G}^{\prime}$ obtained from $\mathbf{G}$ by setting
$E^{\mathbf{G^{\prime}}}(v,u)=0$, and keeping the rest as in $\mathbf{G}$.
Notice that $\mathbf{G}\not\to\mathbf{H}$ and similarly
$\mathbf{G^{\prime}}\not\to\mathbf{H}$ because both has a $\star$-edge and
$\mathbf{H}$ is a $01$-graph. Also, $\mathbf{G}$ is not hom-minimal because
$\mathbf{G}^{\prime}\to\mathbf{G}$ and $\mathbf{G}\not\to\mathbf{G^{\prime}}$.
But, on the other hand, $\mathbf{G}$ is inclusion-minimal as $\mathbf{H}$ has
an element $x$ such that
$E^{\mathbf{H}}(x,x)=E^{\mathbf{G}}(u,u)=E^{\mathbf{G}}(v,v)$. For arbitrary
signature $\sigma$ the proof will be similar. ∎

Before continuing, let us recall the link between finite duality and hom-
minimal obstructions. Again, let $*\in\\{01,\star,\varnothing\\}$. We say that
a set $\mathcal{F}$ of $*$-structures is a _duality set_ for the problem
$\textrm{MP}_{*}(\mathbf{H})$ if

$\displaystyle\mathbf{G}\notin\textrm{MP}_{*}(\mathbf{H})$
$\displaystyle\Longleftrightarrow\mathbf{F}\to\mathbf{G},\qquad\textrm{for
some $\mathbf{F}\in\mathcal{F}$.}$

If, moreover, the set $\mathcal{F}$ is finite, we say that
$\textrm{MP}_{*}(\mathbf{H})$ has _finite duality_. One checks that if
$\mathcal{F}$ is a duality set for $\textrm{MP}_{*}(\mathbf{H})$, then no
$*$-structure in $\mathcal{F}$ belongs to $\textrm{MP}_{*}(\mathbf{H})$.
Hence, we can state the following. Indeed, one can see
$\textrm{Obs}_{*}^{\to}$, for $*\in\\{01,\star,\varnothing\\}$, as a concrete
duality set.

######  Proposition 6.7.

Let $*\in\\{01,\star,\varnothing\\}$ and let $\mathbf{H}$ be a
$\star$-structure. Then, $\textrm{MP}_{*}(\mathbf{H})$ has finite duality if
and only if $\textrm{Obs}_{*}^{\to}(\mathbf{H})$ is finite.

While Proposition 6.6 tells that the two obstructions sets may be different on
$\star$-structures, we show in the next section that one is finite if and only
if the other is.

###  6.1. Finiteness of obstruction sets for $01$-structures and
$\star$-structures

We prove Theorem 6.1 in this section. From now on, we fix $\mathbf{H}$ a
$\star$-structure. We have proved in Proposition 6.5 that Theorem 6.1(1.) and
Theorem 6.1(2.) are equivalent. We prove the other equivalences with the
following propositions. The following proves that Theorem 6.1(3.) is
equivalent to Theorem 6.1 (1.).

######  Proposition 6.8.

$\textrm{Obs}_{\star}^{\to}(\mathbf{H})=\textrm{Obs}_{01}^{\to}(\mathbf{H})$.

###### Proof.

We first prove that
$\textrm{Obs}_{01}^{\to}(\mathbf{H})\subseteq\textrm{Obs}_{\star}^{\to}(\mathbf{H})$.
Indeed, if a $01$-structure $\mathbf{G}$ is a hom-minimal obstruction in
$\textrm{Cat}_{01}$, then it will be a hom-minimal obstruction in
$\textrm{Cat}_{\star}$ because we add only $\star$-structures to
$\textrm{Cat}_{\star}$ and no $\star$-structure with a $\star$-tuple can be
mapped to $\mathbf{G}$.

We turn our attention to the right inclusion. By Theorem 4.1, for any
$\mathbf{G}\in\textrm{Cat}_{\star}\setminus\textrm{Cat}_{01}$, there exists
$\mathbf{G}_{01}\in\textrm{Cat}_{01}$ such that

  * •

there is a surjective homomorphism
$\pi_{\mathbf{G}}\colon\mathbf{G}_{01}\twoheadrightarrow\mathbf{G}$;

  * •

$\mathbf{G}\not\to\mathbf{G}_{01}$;

  * •

$\mathbf{G}\in\textrm{MP}_{\star}(\mathbf{H})\Leftrightarrow\mathbf{G}_{01}\in\textrm{MP}(\mathbf{H})$.

Thus $\mathbf{G}\in\textrm{Obs}_{\star}^{\to}(\mathbf{H})$ only if it is a
$01$-structure. Therefore,
$\textrm{Obs}_{\star}^{\to}(\mathbf{H})\subseteq\textrm{Obs}_{01}^{\to}(\mathbf{H})$.
∎

The following proves the equivalence between the parts Theorem 6.1(2.) and
Theorem 6.1(4.).

######  Proposition 6.9.

$\textrm{Obs}_{\star}^{\subset}(\mathbf{H})$ is finite if and only if
$\textrm{Obs}_{01}^{\subset}(\mathbf{H})$ is finite.

###### Proof.

Let us first prove the right implication. As any $01$-structure is also a
$\star$-structure, we can conclude that
$\textrm{Obs}_{01}^{\subset}(\mathbf{H})\subseteq\textrm{Obs}_{\star}^{\subset}(\mathbf{H})$.

Let us now turn our attention to the left implication. Let us consider the
class $\overline{\textrm{Obs}_{01}^{\subset}}(\mathbf{H})$, that is obtained
from $\textrm{Obs}_{01}^{\subset}(\mathbf{H})$ by taking all
$\star$-structures $\mathbf{A}$ such that there exists a surjective
homomorphism from $\mathbf{B}$ to $\mathbf{A}$ for some
$\mathbf{B}\in\textrm{Obs}_{01}^{\subset}(\mathbf{H})$. Observe that
$|\overline{\textrm{Obs}_{01}^{\subset}}(\mathbf{H})|$ is finite. We know by
Theorem 4.1 that, for any
$\mathbf{G}\in\textrm{Obs}_{\star}^{\subset}(\mathbf{H})$, there exists a
$01$-structure $\mathbf{G}_{01}$ such that:

  * •

there is a surjective homomorphism
$\pi_{\mathbf{G}}\colon\mathbf{G}_{01}\twoheadrightarrow\mathbf{G}$;

  * •

$\mathbf{G}\not\to\mathbf{G}_{01}$;

  * •

$\mathbf{G}\in\textrm{MP}_{\star}(\mathbf{H})\Leftrightarrow\mathbf{G}_{01}\in\textrm{MP}(\mathbf{H})$.

Because $\mathbf{G}\notin\textrm{MP}_{\star}(\mathbf{H})$, we can conclude
that $\mathbf{G}_{01}\notin\textrm{MP}(\mathbf{H})$. And because
$\mathbf{G}_{01}$ is a $01$-structure, there exists
$\mathbf{G}_{01}^{\prime}\in\textrm{Obs}_{01}^{\subset}(\mathbf{H})$ such that
$\mathbf{G}_{01}^{\prime}$ is an induced substructure of $\mathbf{G}_{01}$,
and thus, by transitivity, $\mathbf{G}_{01}^{\prime}\to\mathbf{G}$. By
inclusion-minimality of $\mathbf{G}$ (recall that
$\mathbf{G}\in\textrm{Obs}_{\star}^{\subset}(\mathbf{H})$), this homomorphism
is surjective, i.e.
$\mathbf{G}\in\overline{\textrm{Obs}_{01}^{\subset}}(\mathbf{H})$. We have
thus proved that
$\textrm{Obs}_{\star}^{\subset}(\mathbf{H})\subseteq\overline{\textrm{Obs}_{01}^{\subset}}(\mathbf{H})$,
i.e. is finite. ∎

###  6.2. Looking at obstructions in $\textrm{Cat}_{\varnothing}$

The goal now is to prove the remaining arrows in Figure 2. As in the previous
section, let $\mathbf{H}$ be a fixed $\star$-structure. For a
$\varnothing$-structure
$\mathbf{G}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$, let
$\mathcal{G}_{\mathbf{G}}$ be the set of all $\star$-structures
$\mathbf{G^{\prime}}$ obtained from $\mathbf{G}$ by setting
$R_{i}^{\mathbf{G^{\prime}}}(\mathbf{t})\in\\{0,1,\star\\}$ for any tuple
$\mathbf{t}\in G^{k_{i}}$ such that
$R_{i}^{\mathbf{G}}(\mathbf{t})=\varnothing$, for any $R_{i}\in\sigma$.

######  Proposition 6.10.

For every $\mathbf{G_{\star}}\in\textrm{Obs}_{\star}^{\to}(\mathbf{H})$, there
is $\mathbf{G}_{\varnothing}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$
such that $\mathbf{G_{\varnothing}}\to\mathbf{G_{\star}}$ and there is no
$\mathbf{G}^{\prime}_{\star}\in\textrm{Cat}_{\star}$ such that
$\mathbf{G}_{\varnothing}\to\mathbf{G}^{\prime}_{\star}\to\mathbf{G}_{\star}$.
Moreover, for every $\varnothing$-structure
$\mathbf{G}_{\varnothing}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$,
there is only a finite number of $\star$-structures in
$\textrm{Obs}_{\star}^{\to}(\mathbf{H})$ with such a property.

###### Proof.

Let $\mathbf{G_{\star}}\in\textrm{Obs}_{\star}^{\to}(\mathbf{H})$ and let
$\mathbf{G_{\varnothing}}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$ such
that $\mathbf{G_{\varnothing}}\to\mathbf{G_{\star}}$
($\mathbf{G_{\varnothing}}$ exists because
$\mathbf{G_{\star}}\notin\textrm{MP}_{\star}(\mathbf{H})$). We know that
$\mathbf{G}_{\varnothing}\not\to\mathbf{H}$, so if there is another
$\mathbf{G}^{\prime}_{\star}$ such that
$\mathbf{G}_{\varnothing}\to\mathbf{G}^{\prime}_{\star}\to\mathbf{G}_{\star}$,
we have $\mathbf{G}^{\prime}_{\star}\notin\textrm{MP}(\mathbf{H})$, but this
contradicts $\mathbf{G}_{\star}\in\textrm{Obs}_{\star}^{\to}(\mathbf{H})$.

For the second part, let
$\mathbf{G}_{\varnothing}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$.
Suppose that there is a $\star$-structure
$\mathbf{G}_{\star}^{\prime}\in\textrm{Obs}_{\star}^{\to}(\mathbf{H})\setminus\mathcal{G}_{\mathbf{G}_{\varnothing}}$,
and that $\mathbf{G}_{\varnothing}\to\mathbf{G}_{\star}^{\prime}$. Then, there
is a homomorphism $h\colon G\to G^{\prime}$ such that for any $R_{i}$ and
tuple $\mathbf{t}\in G^{k_{i}}$, we have
$R_{i}^{\mathbf{G}_{\star}^{\prime}}(h(\mathbf{t}))\in\\{0,1,\star\\}$. It
means that there exists a $\star$-structure
$\mathbf{G}_{\star}^{\prime\prime}\in\mathcal{G}_{\mathbf{G}_{\varnothing}}$
such that
$\mathbf{G}_{\star}^{\prime\prime}=h(\mathbf{G}_{\varnothing})\hookrightarrow\mathbf{G}_{\star}^{\prime}$,
which contradicts our assumption that
$\mathbf{G}^{\prime}\in\textrm{Obs}_{\star}^{\to}(\mathbf{H})$. ∎

As a corollary, we have that
$\textrm{Obs}_{\star}^{\to}(\mathbf{H})\subseteq\bigcup_{\mathbf{G}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})}\mathcal{G}_{\mathbf{G}}$,
and then the following.

######  Corollary 6.11.

If $\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$ is finite, then
$\textrm{Obs}_{\star}^{\to}(\mathbf{H})$ is finite.

###### Proof.

By Proposition 6.10,
$\textrm{Obs}_{\star}^{\to}(\mathbf{H})\subseteq\bigcup_{\mathbf{G}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})}\mathcal{G}_{\mathbf{G}}$.
As $\mathcal{G}_{\mathbf{G}}$ is finite, the family
$\bigcup_{\mathbf{G}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})}\mathcal{G}_{\mathbf{G}}$
if $\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$ is finite. ∎

We now prove a similar statement for inclusion-wise minimal obstructions.

######  Proposition 6.12.

If $\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$ is finite, then
$\textrm{Obs}_{\star}^{\subset}(\mathbf{H})$ is finite.

###### Proof.

Any $\star$-structure is also a $\varnothing$-structure. Then,
$\textrm{Obs}_{\star}^{\subset}(\mathbf{H})\subseteq\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$.
∎

We are now going to prove that
$\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$ is finite if and only if
$\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$ is.

######  Proposition 6.13.

If $\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$ is finite, then
$\textrm{Obs}_{\varnothing}^{\subset}$ is finite.

###### Proof.

Consider any $\mathbf{G}\in\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$.
Suppose that it is not hom-minimal, so there exists
$\mathbf{T}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$ such that
$\mathbf{T}\to\mathbf{G}$ and $\mathbf{G}\not\to\mathbf{T}$. Moreover, we know
that $\mathbf{T}$ always maps surjectively to $\mathbf{G}$, because otherwise
the substructure of $\mathbf{G}$ induced by the image of $\mathbf{T}$ would
not map to $\mathbf{H}$, contradicting that $\mathbf{G}$ is an inclusion-
minimal obstruction. The set of $\varnothing$-structures $\mathbf{G}$ such
that $\mathbf{T}$ surjectively maps to $\mathbf{G}$ is finite because
$|G|\leq|T|$. Thus, for every $\varnothing$-structure in
$\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$, there exists
$\mathbf{T}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$ such that
$\mathbf{T}$ surjectively maps to $\mathbf{G}$, and we can then conclude that
$\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$ is finite. ∎

We have proved in Proposition 6.5 that any hom-minimal obstruction is also an
inclusion-minimal obstruction. We can therefore state the following which
finishes the proof of the diagram in Figure 2.

######  Proposition 6.14.

Assume that $\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$ exists. Then, if
$\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$ is finite, then
$\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$ is finite.

One might wonder why the existence condition in the previous proposition.
However, we cannot avoid it as shown by the following, which is the
counterpart of a similar result in the CSP problems. Recall, from Section 3,
the bijection $(\cdot)_{\textrm{CSP}}$ between $\varnothing$-structures and
relational structures.

######  Proposition 6.15.

For every $\varnothing$-structure
$\mathbf{G}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$, the corresponding
relational structure $\mathbf{G}_{\textrm{CSP}}$ does not contain a cycle.

To prove Proposition 6.15, we will use Lemma 6.16. We recall that
$\mathbf{G}_{\textrm{CSP}}$, a relational $\sigma$-structure, has a _cycle of
length $n$_ if there exist $n$ distinct elements $x_{1},\ldots,x_{n}$ and $n$
distinct tuples $\mathbf{t}_{1},\ldots,\mathbf{t}_{n}$ with
$R^{\mathbf{G}_{\textrm{CSP}}}_{i_{j}}(\mathbf{t}_{j})=1$ for some
$R_{i_{j}}\in\sigma$ such that for all $1\leq i\leq n-1$,
$x_{i}\in\mathbf{t}_{i}$, $x_{i}\in\mathbf{t}_{i+1}$, and
$x_{n}\in\mathbf{t}_{n},x_{1}\in\mathbf{t}_{1}$. As $\varnothing$-structures
bijectively correspond to relational structures by $(\cdot)_{\textrm{CSP}}$,
we can say that a $\varnothing$-structure $\mathbf{G}$ has a cycle if
$\mathbf{G}_{\textrm{CSP}}$ has one.

######  Lemma 6.16 ([18]).

Let $\mathbf{G},\mathbf{H}$ be relational $\sigma$-structures such that
$\mathbf{G}$ has a cycle. Then, for any $l\in\mathbb{N}$, there exists a
relational $\sigma$-structure $\mathbf{G}^{\prime}$ such that it hasn’t cycles
of length lesser than $l$, and $\mathbf{G}\to\mathbf{H}$ if and only if
$\mathbf{G}^{\prime}\to\mathbf{H}$.

###### Proof of Proposition 6.15.

Let $\mathbf{G}\in\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$ and assume
that it contains a cycle of length $k$. Then, by Theorem 5.2 and Lemma 6.16,
there is a $\varnothing$-structure $\mathbf{G^{\prime}}$ such that
$\mathbf{G^{\prime}}\to\mathbf{G}$, $\mathbf{G}\not\to\mathbf{G^{\prime}}$,
and $\mathbf{G^{\prime}}\to\mathbf{H}\Leftrightarrow\mathbf{G}\to\mathbf{H}$.
But, then $\mathbf{G}$ cannot be a hom-minimal obstruction. ∎

It is possible to show that there exists $\mathbf{H}$ such that
$\textrm{Obs}_{01}^{\subset}(\mathbf{H})$ is finite and
$\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$ is infinite. Hence, there
is no arrow on the Figure 2 neither from
$\textrm{Obs}_{\star}^{\subset}(\mathbf{H})$ to
$\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$, nor from
$\textrm{Obs}_{\star}^{\to}(\mathbf{H})$ to
$\textrm{Obs}_{\varnothing}^{\to}(\mathbf{H})$.

######  Proposition 6.17.

Let $\mathbf{H}=\mathbf{K}_{2}$ be a $01$-graph, the clique on $2$ vertices.
Then $\textrm{Obs}_{01}^{\subset}(\mathbf{H})$ is finite and
$\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$ is infinite.

###### Proof.

Feder and Hell proved in [13] that once $\mathbf{H}$ is a $01$-graph, the
inclusion-minimal obstructions for $\textrm{MP}(\mathbf{H})$ have bounded
size. Thus, $\textrm{Obs}_{01}^{\subset}(\mathbf{H})$ is finite.

Let us show that $\textrm{Obs}_{\varnothing}^{\subset}(\mathbf{H})$ is
infinite. Consider a $\varnothing$-graph $\mathbf{C}_{n}$ on the domain
$C_{n}=\\{v_{1},\ldots,v_{n}\\}$ with $E^{\mathbf{C}_{n}}(v_{i},v_{i+1})=1$
for all $i\in[n-1]$ and with $E^{\mathbf{C}_{n}}(v_{n},v_{1})=1$, and with all
other edges equal to $\varnothing$. The problem $\mathbf{C}_{n}\to\mathbf{H}$
is equivalent to the $2$-coloring of a directed cycle that is a directed
graph, for which we know that odd cycles are all inclusion-minimal
obstructions. Similarly, deleting any vertex from $\mathbf{C}_{n}$ creates a
$\varnothing$-graph that maps to $\mathbf{H}$. Thus, the set
$\mathcal{C}=\\{\mathbf{C}_{n}\mid n\text{ is odd}\\}$ is an infinite set of
inclusion-minimal obstructions for $\textrm{MP}_{\varnothing}(\mathbf{H})$. ∎

##  7\. Remarks on tractability

Despite some cases (see for instance [21, 16, 14]), the tractability of Matrix
Partition Problems on some graph classes is not that studied. As we have
proved some similarities with usual CSPs, one can for instance ask whether
well-known graph classes with tractable CSPs still have tractable Matrix
Partition Problems. However, this is unlikely and deserves to be investigated.
Let us explain.

_Tree-width_ [2, 20] is a well-known graph parameter due to its numerous
algorithmic applications, in particular, any $\textrm{CSP}(\mathbf{H})$ is
polynomial time solvable in graphs of bounded tree-width. More importantly,
asking whether for two graphs $\mathbf{G}$ and $\mathbf{H}$, there is a
homomorphism from $\mathbf{G}$ to $\mathbf{H}$ can be solved in time
$(|G|+|H|)^{poly(k)}$ with $k$ the tree-width of $\mathbf{G}$. A natural
question is whether such an algorithm exists for Matrix Partitions. One can
define the _$\star$ -tree-width_ of a $\star$-graph $\mathbf{G}$ as the
minimum tree-width over its three subgraphs, each obtained by removing all
$*$-edges, with $*\in\\{0,1,\star\\}$. This definition seems natural, because
we can describe in $\mathsf{FO}$ the omitted edges using those that are
present, and one checks easily, by Courcelle’s theorem (see for instance
[11]), for any fixed $\star$-graph $\mathbf{H}$, in time $f(k)\cdot|G|$
whether $\mathbf{G}\in\textrm{MP}_{\star}(\mathbf{H})$, for any $\star$-graph
$\mathbf{G}$ of $\star$-tree-width $k$. We prove however that, unless
$\textrm{P}=\textrm{NP}$, there is no algorithm running in time
$(|G|+|H|)^{k}$ where $k$ is the $\star$-tree-width of $\mathbf{G}$, and on
input $(\mathbf{G},\mathbf{H})$ checks whether
$\mathbf{G}\in\textrm{MP}_{\star}(\mathbf{H})$, even for $k=1$.

For a family of $\star$-graphs $\mathcal{G}$, we denote by
$\textrm{MP}_{\star}(\mathcal{G},-)$ the set of all pairs of $\star$-graphs
$\mathbf{G},\mathbf{H}$ such that $\mathbf{G}\in\mathcal{G}$ and
$\mathbf{G}\in\textrm{MP}_{\star}(\mathbf{H})$.

A graph is called a _tree_ if it does not contain a cycle. Denote by
$\mathcal{T}$ the class of all $01$-graphs, called _$01$ -trees_, where, when
seen as a CSP-graph, it is a tree. We will prove the following theorem in this
section.

######  Theorem 7.1.

The problem $\textrm{MP}(\mathcal{T},-)$ is NP-complete.

For any 3-SAT formula, we are going to choose the right $01$-tree and
$\star$-graph and reduce 3-SAT to our problem. At first, we will do the
construction of the instance that corresponds to a 3-SAT formula $\varphi$
with $m$ clauses:

$\varphi=\neg(n_{11}x_{11}\wedge n_{12}x_{12}\wedge
n_{13}x_{13})\wedge\ldots\wedge\neg(n_{m1}x_{m1}\wedge n_{m2}x_{m2}\wedge
n_{m3}x_{m3})$

where all $x_{ij}$ belong to the set of variables $\\{x_{1},\ldots,x_{n}\\}$
and $n_{ij}$ denotes either the negation or the absence of negation.

We will construct an oriented tree $\mathbf{T}_{\textrm{CSP}}$ and then obtain
a $01$-tree $\mathbf{T}$ according to the definition.

To any variable $x_{i}$ we correspond an oriented path $\mathbf{P}_{i}$ of
length $n+4$ with all edges going to the same direction except for the edge
between the $(i+1)$st and $(i+2)$nd elements. As on the Figure 3 below.

Figure 3. Correspondence between paths and variables.

Let us denote by $\mathbf{N}_{ijk}$ (for $i,j,k\in\\{0,1\\}$) an oriented path
of length $12$ that corresponds to the values of $n_{l1}=i,n_{l2}=j,n_{l3}=k$
of the $l$th clause for each $l$. $\mathbf{N}_{ijk}$ is equal to
$\mathbf{P}_{d}$, for the case where $n=8$ and $d$ is the positive integer
associated with the binary sequence $ijk$. We assume that the variables
$x_{1},\ldots,x_{n}$ are lexicographically ordered. Such paths for the
following clauses are drawn on the Figure 4:

$\neg(x_{2}\wedge x_{1}\wedge x_{3})\text{, }\neg(\neg x_{1}\wedge\neg
x_{3}\wedge x_{2})\text{, }\neg(\neg x_{1}\wedge\neg x_{2}\wedge\neg x_{3}).$

Figure 4. Additional paths to distinguish clauses with the same variables but
different negations.

We will need the following result for the proof.

######  Lemma 7.2.

[10] For any $i,j$:

$\mathbf{P}_{i}\to\mathbf{P}_{j}\Leftrightarrow i=j.$

The same is also true for $\mathbf{N}_{i},\mathbf{N}_{j}$.

Now we need to construct an oriented tree $\mathbf{T}_{\textrm{CSP}}$,
transform it to a $01$-tree, and to construct a $\star$-graph $\mathbf{H}$
such that there exists a homomorphism $h\colon\mathbf{T}\to\mathbf{H}$ iff
there is a valid assignment for $x_{1},\ldots,x_{n}$ such that $\varphi$ is
satisfied.

We construct $\mathbf{T}_{\textrm{CSP}}$ now. Firstly, add an element $r_{T}$
that will be the root of $\mathbf{T}$, then for every clause
$\neg(n_{i1}x_{i1}\wedge n_{i2}x_{i2}\wedge n_{i3}x_{i3})$ of $\varphi$ do the
following:

  1. (1)

Add the path $\mathbf{N}_{i1i2i3}$ with its left end in $r_{T}$. This path
corresponds to the values $n_{i1},n_{i_{2}},n_{i3}$ of the clause.

  2. (2)

Concatenate an edge to the right end of each $\mathbf{N}_{i1i2i3}$.

  3. (3)

For variables $x_{i1},x_{i2},x_{i3}$ concatenate the paths
$\mathbf{P}_{i1},\mathbf{P}_{i2},\mathbf{P}_{i3}$ to the head of the edge.

The $01$-tree $\mathbf{T}$ is defined trivially: for each pair $(x,y)\in
T^{2}$ we set $E^{\mathbf{T}}(x,y)=1$ if the edge $E(x,y)$ is present in
$\mathbf{T}_{\textrm{CSP}}$ and we set $E^{\mathbf{T}}(x,y)=0$ if it is not
present.

Such a $01$-tree $\mathbf{T}$ looks like the one on the Figure 5.

Figure 5. The construction of the $01$-tree $\mathbf{T}$.

Let us construct a $\star$-graph $\mathbf{H}$. It is constructed in a similar
fashion as $\mathbf{T}$, we start with picking an element $r_{H}$ and then for
every clause $\neg(n_{i1}x_{i1}\wedge n_{i2}x_{i2}\wedge n_{i3}x_{i3})$ of
$\varphi$ do the following:

  1. (1)

Add the path $\mathbf{N}_{i1i2i3}$ with its left end in $r_{H}$.

  2. (2)

Concatenate 7 edges to the right end of $\mathbf{N}_{i1i2i3}$, each edge
correspond to 7 valid assignments $v_{i1},v_{i2},v_{i3}$ to the variables
$x_{i1},x_{i2},x_{i3}$ of the clause.

  3. (3)

To the head of each of these 7 edges we concatenate the 3 paths
$\mathbf{P}_{i1},\mathbf{P}_{i2},\mathbf{P}_{i3}$, each such path
$\mathbf{P}_{ij}$ is labelled with the value $v_{ij}$ that we chose to assign
to $x_{ij}$ when we drew edges on the previous step.

By now $\mathbf{H}$ is an oriented tree. We make it a $01$-tree similarly as
$\mathbf{T}$: $E^{\mathbf{H}}(x,y)=1$ if $x,y$ are adjacent, and
$E^{\mathbf{H}}=0$ otherwise. After that we make $\mathbf{T}$ a $\star$-graph
by the following procedure. Let $x,y\in H$ be the endpoints of two copies of
the same path $P_{i}$ such that the copy containing $x$ is labelled with 1 and
the copy of $y$ is labelled with 0. Then we set $E^{\mathbf{H}}(x,y)=1$. The
construction is presented on the Figure 6.

Figure 6. The construction of $\mathbf{H}$.

The goal of the edges between two copies of the same $\mathbf{P}_{i}$ with
different labels is to forbid two copies of this path in the input to map into
two paths with opposite labels, it is equivalent to forbidding the same
variable $x_{i}$ to take value 0 in one clause and take 1 in another clause.

######  Lemma 7.3.

The size of both $\mathbf{T}$ and $\mathbf{H}$ is $O(mn)$, where $m$ is the
number of clauses and $n$ is the number of variables in $\varphi$.

###### Proof.

The size of each $\mathbf{P}_{i}$ is $O(n)$, the size of each $\mathbf{N}_{i}$
is $O(1)$, so the size of $\mathbf{T}$ is $O(mn)$. $\mathbf{H}$ is 7 times
larger than $\mathbf{T}$. ∎

######  Lemma 7.4.

If there is a homomorphism $h\colon\mathbf{T}\to\mathbf{H}$, then the root
$r_{T}$ of $\mathbf{T}$ is mapped to the root $r_{H}$ of $\mathbf{H}$.

###### Proof.

For any oriented path starting in an element $a$ and ending in $b$ we say that
an edge of the path is _fore-coming_ if its direction coincides with the
direction of the walk from $a$ to $b$, if the direction of the edge is
opposite to the direction of the walk, then it is called _back-coming_.
Observe that for any two elements of an oriented tree the shortest path
between them is uniquely defined. Denote by $height_{T}(x,y)$ the number of
fore-coming edges minus the number of back-coming 1-edges for the shortest
path starting in $x$ and ending in $y$ for any $x,y\in T$. Observe that for
any leaf $l\in T$ the value of $height_{T}(r_{G},l)$ is always the same. Also
observe that for any element $l_{H}$ of $\mathbf{H}$ that is the endpoint of a
copy of some path $\mathbf{P}_{i}$ the $height_{H}(r_{H},l_{H})$ is not
uniquely defined: it is either $height_{T}(r_{T},l)$ or
$height_{T}(r_{T},l)+1$. The latter appears because the endpoints of every two
copies of one path $\mathbf{P}_{i}$ that have different labels are adjacent by
1-edge. The difference of fore- and back-coming edges is preserved by taking
homomorphisms, thus we can conclude that if there is a homomorphism from
$\mathbf{T}$ to $\mathbf{H}$, then either it maps $r_{T}$ to $r_{H}$ or it
maps $r_{T}$ to one of elements adjacent to $r_{H}$. Suppose the second case,
that $r_{T}$ is mapped to an element $s$ such that
$E^{\mathbf{H}}(r_{H},s)=1$. By the construction of $\mathbf{H}$, we know that
$s$ belongs to the path $\mathbf{N}_{i}$ of the $i$th clause of $\varphi$.
Which implies that all the paths $\mathbf{N}_{j}$ of $\mathbf{T}$ are mapped
by a full homomorphism to the $\mathbf{N}_{i}$ of $\mathbf{H}$, which is
impossible. ∎

###### Proof of Theorem 7.1.

Let $v\colon\\{x_{1},\ldots,x_{n}\\}\to\\{0,1\\}$ be an assignment for the
variables of $\varphi$. By Lemma 7.3, construct in P-time a $01$-tree
$\mathbf{T}$ and a $\star$-graph $\mathbf{H}$ as above. Take the $i$th clause
and map the corresponding part of $\mathbf{T}$ to the triple of paths that
have labels corresponding to the assignment $v$. By construction, it will be a
homomorphism.

Let $h\colon\mathbf{T}\to\mathbf{H}$ be a homomorphism. Then we know by Lemma
7.4 that $h(r_{T})=r_{H}$. By Lemma 7.2 we know that the part of $\mathbf{T}$
corresponding to the $i$th clause is mapped to the part of $\mathbf{H}$
corresponding to the same clause of $\varphi$. Then we construct $v$, for any
variable $x\in\\{x_{1},\ldots,x_{n}\\}$ we know that there is no such a pair
of paths $\mathbf{P}_{x},\mathbf{P}_{x}^{\prime}$ that correspond to the
presence of the same variable $x$ in different clauses such that
$\mathbf{P}_{x}$ is mapped to a path labelled with $0$ and
$\mathbf{P}_{x}^{\prime}$ is mapped to a path labelled with 1. Thus, all the
paths $\mathbf{P}_{x}$ are mapped to paths of the same label: either all to 0
or all to 1. So $v(x)$ can be correctly defined for any variable $x$. And this
assignment will be valid because we added to $\mathbf{H}$ all 7 possible valid
assignments for each clause. ∎

######  Remark 7.5.

Observe that the $01$-tree $\mathbf{T}$ that represents a 3-SAT formula also
has bounded pathwidth, so the result of Theorem 7.1 will remain true if we
require that all the $01$-trees of $\mathcal{T}$ have bounded pathwidth.

##  8\. Conclusion

We have proposed several generalisations of the Matrix Partition Problems
studied by Hell et al. We have shown that MP and $\textrm{MP}_{\star}$ are
P-time equivalent and we have used this to show that a dichotomy for every
class $\textrm{MP}^{\tilde{\sigma}}$ with $|\tilde{\sigma}|=1$ implies a
dichotomy for $\textrm{MP}^{\sigma}$ for any finite $\sigma$. Despite this, we
leave open the question of whether MP on directed graphs is P-time equivalent
to $\textrm{MP}^{\sigma}$, for any finite signature $\sigma$, and, a fortiori,
the dichotomy question for MP. We have introduced the generalisation
$\textrm{MP}_{\varnothing}$ as a way to see MP as a CSP on ”complete input”.
We have also studied the set of inclusion-wise minimal obstructions proposed
by Feder et al. [17] and have proved that their finiteness coincides with
finite duality for MP and $\textrm{MP}_{\star}$ problems. This, we believe,
would allow to characterise the finiteness of inclusion-wise minimal
obstructions for MP problems. Finally, we have shown the difference between MP
and CSP wrt the bounded tree-width input by reducing 3-SAT to
$\textrm{MP}(\mathcal{T},-)$.

## Acknowledgement

The authors thank Florent Madelaine for the many fruitful discussions on the
subject.

## References

  * [1] Alon, N. Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory.  Comb. 6, 3 (1986), 207–219.
  * [2] Atserias, A. On digraph coloring problems and treewidth duality.  Eur. J. Comb. 29, 4 (2008), 796–820.
  * [3] Ball, R. N., Nešetřil, J., and Pultr, A. Dualities in full homomorphisms.  Eur. J. Comb. 31, 1 (2010), 106–119.
  * [4] Barto, L., and Kozik, M. Absorption in universal algebra and CSP.  In The Constraint Satisfaction Problem: Complexity and Approximability, A. A. Krokhin and S. Zivný, Eds., vol. 7 of Dagstuhl Follow-Ups. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 45–77.
  * [5] Bodirsky, M., Kára, J., and Martin, B. The complexity of surjective homomorphism problems - a survey.  Discret. Appl. Math. 160, 12 (2012), 1680–1690.
  * [6] Bodirsky, M., Madelaine, F. R., and Mottet, A. A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP.  In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018 (2018), A. Dawar and E. Grädel, Eds., ACM, pp. 105–114.
  * [7] Bulatov, A. A. A dichotomy theorem for constraint satisfaction problems on a 3-element set.  J. ACM 53, 1 (2006), 66–120.
  * [8] Bulatov, A. A. A dichotomy theorem for nonuniform csps.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 (2017), C. Umans, Ed., IEEE Computer Society, pp. 319–330.
  * [9] Bulatov, A. A., Jeavons, P., and Krokhin, A. A. Classifying the complexity of constraints using finite algebras.  SIAM J. Comput. 34, 3 (2005), 720–742.
  * [10] Bulin, J., Delic, D., Jackson, M., and Niven, T. A finer reduction of constraint problems to digraphs.  Log. Methods Comput. Sci. 11, 4 (2015).
  * [11] Courcelle, B., and Engelfriet, J. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, vol. 138 of Encyclopedia of mathematics and its applications.  Cambridge University Press, 2012.
  * [12] Diestel, R. Graph Theory, 4th Edition, vol. 173 of Graduate texts in mathematics.  Springer, 2012.
  * [13] Feder, T., and Hell, P. On realizations of point determining graphs, and obstructions to full homomorphisms.  Discret. Math. 308, 9 (2008), 1639–1652.
  * [14] Feder, T., Hell, P., and Hernández-Cruz, C. Colourings, homomorphisms, and partitions of transitive digraphs.  Eur. J. Comb. 60 (2017), 55–65.
  * [15] Feder, T., Hell, P., Klein, S., and Motwani, R. List partitions.  SIAM J. Discret. Math. 16, 3 (2003), 449–478.
  * [16] Feder, T., Hell, P., and Shklarsky, O. Matrix partitions of split graphs.  Discret. Appl. Math. 166 (2014), 91–96.
  * [17] Feder, T., Hell, P., and Xie, W. Matrix partitions with finitely many obstructions.  Electron. J. Comb. 14, 1 (2007).
  * [18] Feder, T., and Vardi, M. Y. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory.  SIAM J. Comput. 28, 1 (1998), 57–104.
  * [19] Frankl, P., Rödl, V., and Wilson, R. M. The number of submatrices of a given type in a hadamard matrix and related results.  J. Comb. Theory, Ser. B 44, 3 (1988), 317–328.
  * [20] Grohe, M. The complexity of homomorphism and constraint satisfaction problems seen from the other side.  J. ACM 54, 1 (2007), 1:1–1:24.
  * [21] Hell, P. Graph partitions with prescribed patterns.  Eur. J. Comb. 35 (2014), 335–353.
  * [22] Hell, P., and Nešetřil, J. On the complexity of _H_ -coloring.  J. Comb. Theory, Ser. B 48, 1 (1990), 92–110.
  * [23] Hell, P., and Nešetřil, J. Graphs and homomorphisms, vol. 28 of Oxford lecture series in mathematics and its applications.  Oxford University Press, 2004.
  * [24] Hell, P., and Nesetril, J. On the density of trigraph homomorphisms.  Graphs Comb. 23, Supplement-1 (2007), 275–281.
  * [25] Hell, P., and Rafiey, A. The dichotomy of list homomorphisms for digraphs.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011 (2011), D. Randall, Ed., SIAM, pp. 1703–1713.
  * [26] Kolmogorov, V., and Zivný, S. The complexity of conservative valued csps.  J. ACM 60, 2 (2013), 10:1–10:38.
  * [27] Ladner, R. E. On the structure of polynomial time reducibility.  J. ACM 22, 1 (1975), 155–171.
  * [28] MacGillivray, G., and Swarts, J. The complexity of locally injective homomorphisms.  Discret. Math. 310, 20 (2010), 2685–2696.
  * [29] Pudlák, P., Rödl, V., and Savický, P. Graph complexity.  Acta Informatica 25, 5 (1988), 515–535.
  * [30] Schaefer, T. J. The complexity of satisfiability problems.  In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA (1978), R. J. Lipton, W. A. Burkhard, W. J. Savitch, E. P. Friedman, and A. V. Aho, Eds., ACM, pp. 216–226.
  * [31] Stanley, R. P. Enumerative combinatorics, 1st ed., vol. Volume 1 of Cambridge Studies in Advanced Mathematics.  Wadsworth and Brooks / Cole, Chapman and Hall, 2000.
  * [32] Walsh, J. L. A closed set of normal orthogonal functions.  American Journal of Mathematics 45, 1 (Jan. 1923), 5–24.
  * [33] Zhuk, D. A proof of the CSP dichotomy conjecture.  J. ACM 67, 5 (2020), 30:1–30:78.
  * [34] Zhuk, D., and Martin, B. QCSP monsters and the demise of the chen conjecture.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 (2020), K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, and J. Chuzhoy, Eds., ACM, pp. 91–104.