\section{Introduction}

Ladner showed in \cite{ladner1975} that, under the assumption $\polynomial \not= \NP$, there exist problems that are neither in $\polynomial$ nor  $\NPc$. This raises the question of knowing which subclasses of $\NP$ admit a dichotomy between $\polynomial$ and $\NPc$, that is subclasses where every problem is either in $\polynomial$  or is $\NPc$.  For instance, Schaefer proved in his seminal paper \cite{schaefer1978} that any SAT problem is either in $\polynomial$ or is $\NPc$, and Hell and Ne{\v s}et{\v r}il  \cite{hellnesetril1990} showed a similar dichotomy for homomorphism problems on  undirected graphs. The \emph{Constraint Satisfaction Problems} ($\CSP$s for short) form a large and well-known class of problems that are usually described (see \cite{hellnesetril}) as decision problems that check the existence of a homomorphism between two given relational structures. Since, general $\CSP$s are generalisations of both SAT problems and homomorphism problems on undirected graphs, people wonder whether a dichotomy can hold for general $\CSP$s. Indeed, Feder and Vardi explicitly asked for such a result in \cite{federvardi1998}, known as the \emph{$\CSP$ conjecture}, and showed in the same paper many $\polynomial$-time equivalences\footnote{We refer to \Cref{sec:preliminaries} for definitions, but roughly two problems are \emph{$\polynomial$-time equivalent} if one can reduce in $\polynomial$-time one to the other, and vice-versa. Notice that if two families of problems are $\polynomial$-time equivalent, then one admits a dichotomy if and only if the other does.}, in particular, a $\polynomial$-time  equivalence of $\CSP$ with the directed graph homomorphism and with the logical language $\ensuremath{\mathsf{MMSNP}}$. For around two decades, the $\CSP$ conjecture has been verified for many special cases, see for instance \cite{bulatov2006,federvardi1998,grohe2007}, but, more importantly, its study brings many mathematical tools in studying algorithmic and complexity questions, in particular, the algebraic tools \cite{bulatov2005}.    Recently, Bulatov \cite{bulatov2017} and Zhuk \cite{zhuk2020} 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., \emph{full homomorphism} \cite{ballpultrnesetril2010}, \emph{locally injective/surjective homomorphism} \cite{macgillivray2010, bodirsky_surjective_2012}, \emph{list homomorphism} \cite{hell_list_2011}, \emph{quantified $\CSP$} \cite{zhukmartin2020}, \emph{infinite $\CSP$} \cite{bodirsky2018}, \emph{$\VCSP$} \cite{kolmogorov2013}, etc. In this paper, we are interested in the \emph{Matrix Partition} Problem introduced in \cite{federhellkleinmotwani2003} which finds its origin in combinatorics as other variants of the $\CSP$ conjecture, e.g., list or surjective homomorphism.
A \emph{trigraph} is a pair $\structure{G}=(G,\relation{E}^\structure{G})$ where $\relation{E}^\structure{G}\colon G^2\to\{0,1,\star\}$. A \emph{homomorphism} between two trigraphs $\structure{G}$ and $\structure{H}$ is a mapping $h\colon G\to H$ such that for all $(x,y)\in G^2$, $\relation{E}^\structure{H}(h(x),h(y))\in\{\relation{E}^\structure{G}(x,y),\star\}$. As any graph is a trigraph, Hell et al. (\cite{federhellkleinmotwani2003,federhell2007,hell2014}) proposed a way to consider combinatorial problems on graphs as trigraph homomorphism problems, and called them \emph{Matrix Partition Problems}\footnote{The term \emph{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. \cite{federhell2007,hell2014} asks whether Matrix Partition Problems may satisfy the same dichotomy as $\CSP$.

 Motivated by the $\polynomial$-time equivalence between  general $\CSP$ and $\CSP$ on directed graphs \cite{federvardi1998}, 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 \cite{hellnesetriltrigraph2007}. We denote such new problems by $\MP_\star(\structure{H})$, and the original ones by $\MP(\structure{H})$ where $\structure{H}$ is the target structure of the problem. As in the $\CSP$ case, we wonder whether this generalisation is $\polynomial$-time equivalent to trigraph homomorphism. We prove that $\MP_\star$ and $\MP$ are $\polynomial$-time equivalent. Hell and Ne{\v s}et{\v r}il in \cite{hellnesetriltrigraph2007} 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 \emph{Hadamard matrix} \cite{frankl1988}. 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 $\polynomial$-time equivalence (see \Cref{sec:fromemptysettocsp}).

 Feder and Vardi in \cite{federvardi1998} showed that a $\CSP$ over a finite signature is $\polynomial$-time equivalent to a $\CSP$ on directed graphs. Bulin et al. in \cite{bulin2015} gave a more detailed proof of this fact and showed that all the reductions are log-space. In \Cref{sec:arity}, we raise  similar questions about Matrix Partition Problems. Using the result achieved in \Cref{sec:mpstar=mp}, we show that any problem in $\MP$ over any finite signature is $\polynomial$-time equivalent to a problem in $\MP$ on relational structures with  one single relation.

 We then turn our attention to the $\polynomial$-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 $\polynomial$-time equivalent to $\CSP$. In order to show this, we introduce another generalisation of Matrix Partition Problems, denoted by $\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 $\relation{R}$ two relations $\relation{R}_0$, for $0$-labelled tuples, and $\relation{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 $\relation{R}_0$ or in $\relation{R}_1$. When we relax this completeness property, we obtain the class of problems $\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 \Cref{sec:fromemptysettocsp} that $\MP_\varnothing$ is $\polynomial$-time equivalent to $\CSP$, and that the correspondence is a bijection between the classes of problems.  We later use this correspondence to show in \Cref{sec:arity} that any reduction similar to the one of Bulin et al. cannot prove the $\polynomial$-time equivalence between $\MP$ over any finite signature and $\MP$ on directed graphs, unless $\MP$ is $\polynomial$-time equivalent to $\CSP$.

A natural way to prove that a problem is in $\polynomial$ is to show that it is described by a finite set of obstructions. In the case of $\CSP$, $\family{F}$ is called a \emph{duality set} for an instance $\CSP(\structure{H})$ if for any structure $\structure{G}$, $\structure{G}$ does not homomorphically map to $\structure{H}$ if and only if there is $\structure{F}\in \family{F}$ such that $\structure{F}$ homomorphically maps to $\structure{G}$. It is known that $\CSP(\structure{H})$ has a finite set of obstructions if and only if it is definable by a \emph{first-order formula} \cite{atserias2008}. Feder, Hell and Xie proposed in \cite{federhell2007} 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 $\family{F}$ of forbidden graphs. They proposed a necessary (but not sufficient) condition for a matrix $\matrice{M}$ to have finitely many obstructions, and Feder, Hell and Shklarsky later showed in \cite{federhellsplit2014} that any Matrix Partition Problem has finitely many obstructions if the input consists only of split graphs. In \Cref{sec:obstructions}, 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 $\MP_\star$ case. We also consider duality sets for Matrix Partition Problems. We show that the following are equivalent  for a trigraph $\structure{H}$ (it holds also for relational structures):
\begin{enumerate}
    \item $\MP(\structure{H})$ has a finite duality set.
    \item $\MP(\structure{H})$  has a finite set of inclusion-wise minimal obstructions.
    \item $\MP_\star(\structure{H})$ has a finite duality set.
    \item $\MP_\star(\structure{H})$ has a finite set of inclusion-wise minimal obstructions.
\end{enumerate}

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

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

{\bf Outline.} After giving all the necessary definitions in \Cref{sec:preliminaries}, we show in \Cref{sec:fromemptysettocsp} that $\MP_\varnothing$ and $\CSP$ are $\polynomial$-time equivalent. $\polynomial$-time equivalence of $\MP$ and $\MP_\star$ is shown in \Cref{sec:mpstar=mp}. In \Cref{sec:arity} 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. \Cref{sec:obstructions} covers the finiteness for the obstruction sets. We discuss with some remarks in \Cref{sec:tractability}, the potential utility of tree-width for the $\MP$ problems.

\section{Preliminaries}\label{sec: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., $\tuple{t}$), and the $i$-th coordinate of a tuple $\tuple{t}$ is denoted by $t_i$; if $f:V\to A$ is a mapping from $V$ to a set $A$, we denote by $f(\tuple{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 \cite{Diestel12}. 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 \cite{stanley_enumerative_combinatorics}.

\begin{definition}[$(\symb{*},\sigma)$-structures]
A \emph{signature} $\sigma$ is a set $\{\relation{R}_1,\ldots,\relation{R}_n\}$, each $\relation{R}_i$ has arity $k_i\in \mathbb{N},\ i\in [n]$.

Let $(P_*, \preceq_*)$ be a partially ordered set (poset). A \emph{$(\symb{*},\sigma)$-structure} is a tuple $\structure{G} := (G; \relation{R}_1^\structure{G},\ldots,\relation{R}_n^\structure{G})$ with $G$ a finite set, and for each $i\in [n]$,
$\relation{R}_i^\structure{G}\colon G^{k_i} \to P_*$
is interpreted as a mapping to the elements of the poset.
\end{definition}

We will always denote a $(\symb{*},\sigma)$-structure by a boldface capital letter, e.g. $\structure{A}$, and its domain by the same letter in plain font, e.g. $A$. It is worth mentioning that the notion of $(\symb{*},\sigma)$-structure is different from the one in \emph{universal algebra}, where in the latter case the functional symbol $\relation{R}_i$ is interpreted in $\structure{G}$ as a function from $G^{k_i}\to G$.

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

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

\begin{definition}[homomorphism for $(\symb{*},\sigma)$-structures] For two $(\symb{*},\sigma)$-structures $\structure{G}$ and $\structure{H}$, a  mapping $h\colon G\to H$ is called a \emph{homomorphism from $\structure{G}$ to $\structure{H}$} if, for each $\relation{R} \in \sigma$ of arity $k$, and $\tuple{t}\in G^{k}$,
$\relation{R}^\structure{G}(\tuple{t}) \preceq_\symb{*} \relation{R}^\structure{H}(h(\tuple{t}))$.

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

We can now explain how the notion of homomorphism between  $(\symb{*},\sigma)$-structures subsumes the usual ones. Before, let us recall the  partial orders we consider in this paper.
\begin{itemize}
    \item $(P_{01}, \preceq_{01})$, where $P_{01}=\{0,1\}$ and $\preceq_{01}$ is the empty order with $0$ and $1$ incomparable.

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

    \item $(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$.

    \item $(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$.
\end{itemize}

\begin{remark}
If the signature $\sigma$ is clear from the context,  then we will just write \emph{$*$-structure} instead of $(\symb{*},\sigma)$-structure, for $*\in \{01,\star,\varnothing\}$. Also, if $\sigma = \{E(\cdot,\cdot)\}$, then we will write \emph{$*$-graph} instead.  Finally, we will talk about \emph{relational $\sigma$-structures} and \emph{directed graphs}, instead of $(\symb{\CSP},\sigma)$-structures and $\symb{\CSP}$-graphs. Furthermore, for any tuple (edge) $\tuple{t}\in A^k$ of a $*$-structure ($*$-graph) $\structure{A}$ corresponding to a symbol $R\in\sigma$ that is clear from the context, we will call $\tuple{t}$ a \emph{$p$-tuple ($p$-edge)} if $\relation{R}^\structure{A}(\tuple{t})=p$ for some element $p$ of the poset $(P_*, \preceq_*)$.
\end{remark}

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

\begin{proposition}\label{prop:subposet}
Let $(P_*, \preceq_*)$ and $(P_{*'}, \preceq_{*'})$ be two posets, with $(P_*, \preceq_*)$ a sub-poset of $(P_{*'}, \preceq_{*'})$. Then every $(\symb{*},\sigma)$-structure is also a $(\symb{*'},\sigma)$-structure, for any $\sigma$.
\end{proposition}

Particularly, for any $\sigma$, every $(\symb{{01}},\sigma)$-structure is a $(\symb{\star},\sigma)$-structure, and every $(\symb{\star},\sigma)$-structure is a $(\symb{\varnothing},\sigma)$-structure. For $*\in\{01,\star,\varnothing\}$, we denote by $\Cat_*$ the set of
all $(\symb{*},\sigma)$-structures\footnote{We use the notation $\Cat_*$ because one can use $(\symb{*},\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:
\begin{align*}
\Cat_{01}^\sigma\subset \Cat_\star^\sigma \subset \Cat_\varnothing^\sigma.
\end{align*}

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_\CSP, \preceq_\CSP)$.

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

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

By $\MP^\sigma$, $\MP_\star^\sigma$, $\MP_\varnothing^\sigma$ and $\CSP^\sigma$ we denote, respectively, the families of problems $\MP^\sigma(\structure{H})$,
$\MP_\star^\sigma(\structure{H})$, $\MP_\varnothing^\sigma(\structure{H})$ and $\CSP^\sigma(\structure{H})$, for all $\star$-structures\footnote{For
  $\CSP^\sigma(\structure{H})$ we of course demand that $\structure{H}$ is a $(\symb{\CSP},\sigma)$-structure, and for
  $\MP_\varnothing^\sigma(\structure{H})$, we consider $\structure{H}$ to be a $(\varnothing,\sigma)$-structure.} $\structure{H}$. If $\sigma = \{\relation{E}(\cdot,\cdot)\}$ -- the directed graph signature, then we will omit the $\sigma$-superscript and will just write $\MP$, $\MP_\star$, $\MP_\varnothing$ and $\CSP$.
\end{definition}

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.

\begin{observation}[Matrix Partitions \cite{federhell2007}]
Let $\matrice{M}$ be a an $n\times n$-matrix with entries on $\{0,1,\star\}$.  A graph $\structure{G}$ admits an \emph{$\matrice{M}$-partition} if there is a function $m:G\to [n]$ such that for all distinct $x,y\in G$, $\relation{E}^{\structure{G}}(x,y)\preceq_\star M[m(x),m(y)]$.
\end{observation}

\begin{remark}
There are some differences between the definition of $\matrice{M}$-partition in \cite{federhell2007} and the definition of $\MP(\structure{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.
\end{remark}

It is  already observed in \cite{federhell2007,hell2014} that $\MP$ is a generalisation of $\CSP$ problems in directed graphs, and hence the
homomorphism problems $\MP^\sigma_\star$ are generalisations of $\CSP^\sigma$ problems.

Let us end these preliminaries with the notion of $\polynomial$-time equivalence between two families of problems, which allows to transfer dichotomy
results. Two decision problems $P_1$ and $P_2$ are \emph{$\polynomial$-time equivalent} if there is a $\polynomial$-time reduction from $P_1$ to $P_2$, and a $\polynomial$-time reduction from $P_2$ to $P_1$.

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

\begin{observation}\label{obs:trivial} All along the paper, whenever we consider a problem $\MP_*^\sigma(\structure{H})$, for $*\in
  \{01,\star,\varnothing\}$, we consider that there is no  $x\in H$  such that for all $\relation{R}\in \sigma$,
  $\relation{R}(x,\ldots,x)= \star$. Otherwise, the problem is trivial as then $\MP_*^\sigma(\structure{H})$ equals  $\Cat_*^\sigma$.
\end{observation}

\section{Equivalence between $\MP_\varnothing^\sigma$ and  $\CSP^{\sigma_\CSP}$}
\label{sec:fromemptysettocsp}

Let $\sigma=\{\relation{R}_1,\ldots,\relation{R}_n\}$ be a signature, the arity of each $\relation{R}_i$ denoted by $k_i$. We prove in this section that there is a signature $\sigma_\CSP$ such that
any problem in $\MP_\varnothing^\sigma$ is $\polynomial$-time equivalent to a problem in $\CSP^{\sigma_\CSP}$ and vice versa.

The signature $\sigma_\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_\CSP=\{\relation{R}_{1,0},\relation{R}_{1,1},\ldots,\relation{R}_{n,0},\relation{R}_{n,1}\}$,
for $i\in[n], \relation{R}_{i,0},\relation{R}_{i,1}$ both have arity $k_i$.

For every $\varnothing$-structure $\structure{A}_\varnothing$, we correspond a relational $\sigma_\CSP$-structure $\structure{A}_\CSP$ with the same domain $A$ and the symbols $\relation{R}_{i,0}, \relation{R}_{i,1}$ of $\sigma_\CSP$ are interpreted as follows:
\begin{equation}\label{eq:emptysetcsp_equation}
\forall \relation{R}_i\in\sigma, \tuple{t}\in A^{k_i}, j\in\{0,1\}\colon \relation{R}_{i,j}^{\structure{A}_\CSP}(\tuple{t})=1 \Leftrightarrow j \preceq_\varnothing \relation{R}_i^{\structure{A}_\varnothing}(\tuple{t}).
\end{equation}

\begin{observation}\label{obs:mptocsp_ptime}
$\structure{A}_\CSP$ is constructible in $\polynomial$-time in the size of $\structure{A}_\varnothing$.
\end{observation}

\begin{observation}\label{obs:mptocsp}
For any $(\symb{\varnothing},\sigma)$-structure $\structure{A}_\varnothing$, there exists a unique relational $\sigma_\CSP$-structure $\structure{A}_\CSP$, and for any
relational $\sigma_\CSP$-structure,  there exists a unique $(\symb{\varnothing},\sigma)$-structure $\structure{A}_\varnothing$ such that \cref{eq:emptysetcsp_equation} is satisfied. That is there is a bijective correspondence between $(\symb{\varnothing},\sigma)$-structures and relational $\sigma_\CSP$-structures.
\end{observation}

\begin{theorem}\label{thm:mptocsp} $\MP_\varnothing^\sigma$ and $\CSP^{\sigma_\CSP}$ are $\polynomial$-time equivalent.
\end{theorem}

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

  Assume that $\structure{B}_\varnothing\in \MP_\varnothing^\sigma(\structure{A}_\varnothing)$ and let $h:B\to A$ be a homomorphism from $\structure{B}_\varnothing$ to $\structure{A}_\varnothing$. We will
  show that the same map $h$ is a homomorphism from $\structure{B}_\CSP$ to $\structure{A}_\CSP$. For any tuple $\tuple{t}$ and its
  image $h(\tuple{t})$, we know that for any $\relation{R}_{i,j}\in \sigma_\CSP$:
\begin{displaymath}
\relation{R}_{i,j}^{\structure{B}_\CSP}(\tuple{t})=1 \Leftrightarrow j \preceq_\varnothing \relation{R}_i^{\structure{B}_\varnothing}(\tuple{t}) \Rightarrow j \preceq_\varnothing \relation{R}_i^{\structure{A}_\varnothing}(h(\tuple{t})) \Leftrightarrow \relation{R}_{i,j}^{\structure{A}_\CSP}(h(\tuple{t}))=1.
\end{displaymath}
Now, backwards, assume that $\structure{B}_\CSP\in \CSP^{\sigma_\CSP}(\structure{A}_\CSP)$, and let $h:B\to A$ a homomorphism from $\structure{B}_\CSP$ to
$\structure{A}_\CSP$. Similarly as in the first part, for a tuple $\tuple{t}$, we know that for all $\relation{R}_i\in \sigma, j\in\{0,1\}$:
\begin{displaymath}
j \preceq_\varnothing \relation{R}_i^{\structure{B}_\varnothing}(\tuple{t}) \Leftrightarrow
\relation{R}_{i,j}^{\structure{B}_\CSP}(\tuple{t}) =1 \Rightarrow \relation{R}_{i,j}^{\structure{A}_\CSP}(h(\tuple{t})) =1\Leftrightarrow j \preceq_\varnothing \relation{R}_i^{\structure{A}_\varnothing}(h(\tuple{t})).
\end{displaymath}
This implies that $h$ is a homomorphism from $\structure{B}_\varnothing$ to $\structure{A}_\varnothing$.
\end{proof}

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

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

\begin{proof}
We know that $\structure{A}_*$ is also a $\varnothing$-structure by \Cref{prop:subposet}. Then, consider the relational $\sigma_\CSP$-structure $\structure{A}_\CSP$ provided by \Cref{thm:mptocsp}. It has the core $\structure{C}_\CSP$ embedded into $\structure{A}_\CSP$. Let $\structure{C}_*$ be the corresponding $\varnothing$-structure by \Cref{thm:mptocsp}, it must also be homomorphically equivalent to $\structure{A}_*$ and be embedded into it. As $\structure{C}_*$ embeds into $\structure{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 $\structure{C}_\CSP$ which is impossible. Let $\structure{C}_*'$ be another core of $\structure{A}_*$, that is not isomorphic to $\structure{C}_*$. But then $\structure{C}_\CSP'$ must be the core of $\structure{A}_\CSP$ and $\structure{C}_\CSP\not\cong\structure{C}_\CSP'$ which is impossible as $\structure{C}_\CSP$ is a core.
\end{proof}

\section{Equivalence between $\MP^\sigma_\star$ and $\MP^\sigma$}\label{sec:mpstar=mp}

In this section we will prove the following theorem.

\begin{theorem}\label{thm:mpstardichotomy}
For any finite signature $\sigma$, $\MP^\sigma$ and $\MP_\star^\sigma$ are $\polynomial$-time equivalent.
\end{theorem}

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

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

\begin{definition}[Hadamard Matrices]
An $n\times n$-matrix $\matrice{H}_n$, which entries are in $\{1,-1\}$, is called a \emph{Hadamard matrix} if
\begin{displaymath}
    \matrice{H}_n\cdot \matrice{H}_n^T = n\cdot \matrice{I}_n,
\end{displaymath}
where $\matrice{I}_n$ is the identity matrix of size $n$, and $\matrice{H}^T$ is the transpose of $\matrice{H}$.

\end{definition}

Hadamard matrices exist for any power of $2$.

\begin{lemma}[\cite{walsh1923}]\label{lem:hadamard} For every positive integer $n>1$, one can construct in time $2^{poly(n)}$ a $2^n\times 2^n$-Hadamard matrix.
\end{lemma}

If $\matrice{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 $\matrice{H}_n[A,B]$ the submatrix of $\matrice{H}_n$, whose rows are indexed by $A$ and columns are indexed by $B$. If all the entries of
$\matrice{H}_n[A,B]$ are equal, then we call $\matrice{H}_n[A,B]$ a \emph{monochromatic submatrix}. We will need the following to prove that if
$\structure{G}_{01}\in \MP(\structure{H})$, then $\structure{G}\in\MP_\star(\structure{H})$.

\begin{lemma}[\cite{alon1986,pudlak1988}]\label{lem:monochrome}
  Let $\matrice{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 $\matrice{H}_n[A,B]$ of $\matrice{H}_n$ is not monochromatic.
  %

\end{lemma}

\begin{proof}[Proof of \Cref{thm:mpstardichotomy}] Let us first explain the case of $\star$-graphs. Let $\structure{H}$ be a $\star$-graph with $m=|H|$. We
  will show the $\polynomial$-time equivalence between the problems $\MP(\structure{H})$ and $\MP_\star(\structure{H})$.

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

  Let $k$ be the smallest positive integer such that $2^k > 4m^2+1$, and let $\matrice{H}_{2^k}$ be the Hadamard matrix ensured by \Cref{lem:hadamard}. Let
  the domain of $\structure{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$,

  \begin{align*}
    \relation{E}^{\structure{G}_{01}}(v_{g_1,i},v_{g_2,j}) &= \begin{cases} \relation{E}^\structure{G}(g_1,g_2) & \textrm{if $\relation{E}^\structure{G}(g_1,g_2)\ne
        \star$},\\
      (\matrice{H}_{2^k}[i,j] +1)/2 & \textrm{otherwise}. \end{cases}
  \end{align*}
  Observe that in the case $\relation{E}^\structure{G}(g_1,g_2) = \star$, if $\matrice{H}_{2^k}[i,j]=1$, then $\relation{E}^{\structure{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 \structure{G}_{01}\to \structure{G}$ such that for all $g\in G$,
  $\pi(V_g) = g$. If there exists a homomorphism $h\colon \structure{G}\to\structure{H}$, then, by transitivity, $h\circ\pi:G_{01}\to H$ will be a homomorphism. Suppose
  that there exists a homomorphism $h_{01}\colon \structure{G}_{01}\to\structure{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 $\structure{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
  $\relation{E}^\structure{G}(g_1,g_2) \in \{0,1\}$, then for all $a_1\in A_{g_1}, a_2\in A_{g_2}$,
  $\relation{E}^{\structure{G}_{01}}(a_1,a_2) = \relation{E}^\structure{G}(g_1,g_2)$, so
  $\relation{E}^\structure{G}(g_1,g_2)\preceq_\star \relation{E}^\structure{H}(h(g_1),h(g_2))$. If $\relation{E}^\structure{G}(g_1,g_2) = \star$, then
  $\matrice{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
\begin{displaymath}
    \frac{|V_g|}{2m} \geq \frac{4m^2+1}{2m} \geq \sqrt{4m^2+1}.
\end{displaymath}
By \Cref{lem:monochrome}, the submatrix $\matrice{H}_{2^k}[B_1,B_2]$ is not monochromatic. Thus, $\relation{E}^\structure{H}(h(g_1),h(g_2))=\star$ and $h$ is
a homomorphism from $\structure{G}$ to $\structure{H}$, and we are done.

Let us now prove the general case. Let $\sigma=\{\relation{R}_1,\ldots,\relation{R}_p\}$ a signature, with $k_i$ the arity of $\relation{R}_i$, for $i\in
[p]$. We recall that $\MP^{\sigma}(\structure{H})$ trivially reduces to $\MP_\star^{\sigma}(\structure{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 $\structure{G}_{01}$. For a given input
$\structure{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 $\matrice{H}_{2^k}$ be the Hadamard matrix guaranteed by \Cref{lem:hadamard}. Now, the domain $G_{01}$ of $\structure{G}_{01}$ is the
disjoint union $\bigsqcup_{g\in G}V_g$. For each $\relation{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}})$,
\begin{align*}
  \relation{R}_i^{\structure{G}_{01}}(v_{g_1,i_1}, \ldots,v_{g_{k_i},i_{k_i}}) &= \begin{cases} \relation{R}_i^{\structure{G}}(g_1,\ldots,g_{k_i}) & \textrm{if
      $\relation{R}_i^{\structure{G}}(g_1,\ldots,g_{k_i})\ne \star$},\\
    (\matrice{H}_{2^k}[i_1,i_2] +1)/2 & \textrm{otherwise}. \end{cases}
  \end{align*}

Suppose now that there exists $h_{01}\colon \structure{G}_{01}\to \structure{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
$\matrice{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.
\end{proof}

\section{Arity Reduction}\label{sec:arity}

Recall that a  \emph{primitive-positive formula} $\varphi( x_1,\ldots,x_n)$  is a first-order formula ($\ensuremath{\mathsf{FO}}^\sigma$) of the form
\begin{displaymath}
\exists x_{n+1},\ldots,x_m.(\psi_1\wedge\dots\wedge\psi_l)
\end{displaymath}
where each $\psi_i$ is either $x_s=x_j$, $\ensuremath{\mathsf{true}}$, or $\relation{R}(x_{i_1},\ldots,x_{i_k})=1$.

Let $\sigma = \{\relation{R}_1,\ldots,\relation{R}_n\},\sigma'=\{\relation{S}_1,\ldots,\relation{S}_m\}$ be two signatures, and
$\structure{A}, \structure{A}'$ be relational $\sigma$- and $\sigma'$-structures over the same domain $A$. We say that $\structure{A}$
\emph{pp-defines} $\structure{A}'$ if for every $k$-ary relation $\relation{S}_j^{\structure{A'}}$ of $\structure{A}'$ there
exists a primitive-positive formula $\varphi_j\in \ensuremath{\mathsf{FO}}^\sigma$ with $k$ free variables such that for all
$ (a_1,\ldots,a_k)\in A^{k}$, $\relation{S}_j^{\structure{A'}}(a_1,\ldots,a_n)=1 \Leftrightarrow \structure{A}'\models\varphi_j(
a_1/x_1,\ldots,a_n/x_n)$.

\begin{theorem}\cite{barto2017csp}\label{thm:pp-definition}
Suppose that a relational $\sigma$-structure $\structure{A}$ pp-defines a relational $\sigma'$-structure $\structure{A}'$. Then the problem $\CSP^{\sigma'}(\structure{A}')$ reduces in $\polynomial$-time to $\CSP^\sigma(\structure{A})$.
\end{theorem}

\subsection{From directed graphs to many relations}

Let $\sigma = \{\relation{R}_1,\ldots,\relation{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 $\MP_\star^\sigma$ implies the existence of a dichotomy for the class of $\star$-graphs $\MP_\star$. Let $\gamma = \{E(\cdot,\cdot)\}$ be the directed graph signature and let $\gamma_\CSP=\{E_0(\cdot,\cdot),E_1(\cdot,\cdot)\}$ be obtained from $\gamma$ by the construction from \Cref{sec:fromemptysettocsp}.

\begin{theorem}\label{thm:binary-to-many} For every $\star$-graph $\structure{H}_\star$, there exists a $(\symb{\star},\sigma)$-structure $\structure{A}_\star$ such that the problems
  $\MP_\star(\structure{H}_\star)$ and $\MP_\star^\sigma(\structure{A}_\star)$ are $\polynomial$-time equivalent.
\end{theorem}

\begin{proof}
Let us recall from the \Cref{sec:fromemptysettocsp} that there is a bijective correspondence between a $(\symb{\varnothing},\sigma)$-structure $\structure{A}_\varnothing$ and a relational $\sigma_\CSP$-structure $\structure{A}_\CSP$ such that for any two $(\symb{\varnothing},\sigma)$-structures $\structure{A}_\varnothing,\structure{B}_\varnothing$:
\begin{displaymath}
\structure{B}_\varnothing\to\structure{A}_\varnothing\Leftrightarrow\structure{B}_\CSP\to\structure{A}_\CSP.
\end{displaymath}
Now, let us consider a $\star$-graph $\structure{H}_\star$ with its corresponding relational $\gamma_\CSP$-structure $\structure{H}_\CSP$. We construct the
$\sigma_\CSP$-structure $\structure{A}_\CSP$ by the following pp-definition:
\begin{equation}\label{eq:bi-many1}
\forall j\in\{0,1\}\colon \relation{R}_{1,j}^{\structure{A}_\CSP}(x_1,\ldots,x_{k_1}) =1 \Leftrightarrow E_j^{\structure{H}_\CSP}(x_1,x_2)=1;
\end{equation}
\begin{equation}\label{eq:bi-many2}
\forall i>1,j\in\{0,1\}\colon \relation{R}_{i,j}^{\structure{A}_\CSP}(x_1,\ldots,x_{k_i}) = 1 \Leftrightarrow \ensuremath{\mathsf{true}}.
\end{equation}
Observe that the relational $\gamma_\CSP$-structure $\structure{H}_\CSP$ is also pp-definable from the relational $\sigma_\CSP$-structure $\structure{A}_\CSP$:
\begin{equation}\label{eq:many-bi}
\relation{E}^{\structure{H}_\CSP}(x_1,x_2) = 1 \Leftrightarrow \exists x_3,\ldots,x_{k_1}. \relation{R}_1^{\structure{A}_\CSP}(x_1,\ldots,x_{k_1}).
\end{equation}
Now consider any $\star$-graph $\structure{G}_\star$. Every $\star$-graph is also a $\varnothing$-graph, so there is a relational $\gamma_\CSP$-structure
$\structure{G}_\CSP$ such that $\structure{G}_\star\to\structure{H}_\star$ if and only if $\structure{G}_\CSP\to\structure{H}_\CSP$. By the pp-definability in \cref{eq:many-bi} and
\Cref{thm:pp-definition}, we construct a relational $\sigma_\CSP$-structure $\structure{B}_\CSP$ such that $\structure{G}_\CSP\to\structure{H}_\CSP$ if
and only if $\structure{B}_\CSP\to\structure{A}_\CSP$. From $\structure{B}_\CSP$ we obtain a $(\symb{\star},\sigma)$-structure
$\structure{B}_\star$ such that $\structure{B}_\CSP\to\structure{A}_\CSP$ if and only if $\structure{B}_\star\to\structure{A}_\star$. Observe
that, because $\structure{G}_\star$ is a $\star$-graph, in $\structure{G}_\CSP$ for any $(x,y)\in G^2$, we have either $E_0^{\structure{G}_\CSP}(x,y)=1$ or $E_1^{\structure{G}_\CSP}(x,y)=1$; thus in $\structure{B}_\CSP$ any relation other than $\relation{R}_1$ is interpreted trivially and for each tuple $\tuple{x}\in B^{k_1}$ either $\relation{R}_{1,0}^{\structure{B}_\CSP}(\tuple{x})=1$ or $\relation{R}_{1,1}^{\structure{B}_\CSP}(\tuple{x})=1$. So, $\structure{B}_\star$ is indeed a $(\symb{\star},\sigma)$-structure, that finishes the reduction from $\MP_\star(\structure{H}_\star)$ to $\MP_\star^\sigma(\structure{A}_\star)$.

For the other direction, consider any $(\symb{\star},\sigma)$-structure $\structure{B}_\star$. Similarly, we construct a relational $\sigma_\CSP$-structure $\structure{B}_\CSP$, and by the pp-definition in
\cref{eq:bi-many1,eq:bi-many2}, we can compute a relational $\gamma_\CSP$-structure $\structure{G}_\CSP$ such that
$\structure{G}_\CSP\to \structure{H}_\CSP$ if and only if $\structure{B}_\star\to \structure{A}_\star$, and then a $\star$-graph $\structure{G}_\star$ such that
$\structure{B}_\star\to\structure{A}_\star$ if and only if $\structure{G}_\star\to\structure{H}_\star$. With similar arguments as in the other direction, we can prove
that $\structure{G}_\star$ is indeed a $\star$-graph. We have then shown that $\MP_\star(\structure{G}_\star)$ and $\MP_\star^\sigma(\structure{A}_\star)$ are $\polynomial$-time
equivalent.
\end{proof}

One notices that the proof of \Cref{thm:binary-to-many} is still correct if we replace $\gamma$ by any relation $\relation{R}$ of arity $\ell \geq 2$, we require
in this case that $\relation{R_1}$ has arity at least $\ell$.

\subsection{From many relations to one}

Suppose that $\sigma = \{\relation{R}_1,\ldots,\relation{R}_p\}$, $\relation{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} = \{\relation{R}\}$ with $\relation{R}$ of arity $k+p-1$ such that for any $(\symb{\star},\sigma)$-structure $\structure{A}$ there exists a $(\symb{\star},\tilde{\sigma})$-structure $\tilde{\structure{A}}$ such that $\MP_\star^\sigma(\structure{A})$ and $\MP_\star^{\tilde{\sigma}}(\tilde{\structure{A}})$ are $\polynomial$-time equivalent.

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

\begin{itemize}
    \item Let $\family{A}_1 = \{\tilde{\tuple{t}}=(\underbrace{c_A,\ldots,c_A}_{i-1},\tuple{t},\underbrace{c_A,\ldots,c_A}_{k+p-k_i-i})\mid
      \relation{R}_i\in\sigma,\tuple{t}\in A^{k_i}\}$, and
    \begin{equation}\label{eq:frombtotildeb}
        \textrm{for all},\ \tilde{\tuple{t}}\in\family{A}_1,\ \relation{R}^{\tilde{\structure{A}}}(\tilde{\tuple{t}}) = \relation{R}^\structure{A}_i(\tuple{t});
    \end{equation}
    \item Let $\family{A}_2 = \{(c_A,\ldots,c_A)\}$, then for all $\tilde{\tuple{t}}\in \family{A}_2\colon\relation{R}^{\tilde{\structure{A}}}(\tilde{\tuple{t}})=1$;
    \item Let $\family{A}_3=\tilde{A}^{k+p-1}\setminus(\family{A}_1\sqcup\family{A}_2)$, then for all $\tilde{\tuple{t}}\in\family{A}_3\colon\relation{R}^{\tilde{\structure{A}}}(\tilde{\tuple{t}}) = 0$.
\end{itemize}

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

\begin{lemma}\label{lem:sigmatotildesigma}
$\MP_\star^\sigma(\structure{A})$ reduces in polynomial time to $\MP_\star^{\tilde{\sigma}}(\tilde{\structure{A}})$.
\end{lemma}
\begin{proof}
Let $\structure{B}$ be an input instance of the problem $\MP_\star^{\sigma}(\structure{A})$. Assume that there is $h\colon \structure{B}\to \structure{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}=\family{B}_1\sqcup\family{B}_2\sqcup\family{B}_3$. Consider $\tilde{\tuple{t}}=(c_B,\ldots,c_B,\tuple{t},c_B,\ldots,c_B)\in\family{B}_1$, where $\tuple{t} = (b_1,\ldots,b_{k_i})\in B^{k_i}$ for
$\relation{R}_i\in\sigma$. Then $\tilde h(\tilde{\tuple{t}})=(c_A,\ldots,c_A,h(\tuple{t}),c_A,\ldots,c_A)\in\family{A}_1$. As $h$ is a homomorphism, we have
that by \cref{eq:frombtotildeb}:
\begin{displaymath}
\relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}}) = \relation{R}_i^\structure{B}(\tuple{t})\preceq_\star \relation{R}_i^\structure{A}(h(\tuple{t})) = \relation{R}^{\tilde{\structure{A}}}(\tilde h(\tilde{\tuple{t}})).
\end{displaymath}
For $\tilde{\tuple{t}}\in\family{B}_2$, we have that $\tilde h(\tilde{\tuple{t}})=(c_A,\ldots,c_A)$, so $\relation{R}^{\tilde{\structure{A}}}(\tilde h(\tilde{\tuple{t}}))=\relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}})=1.$
Let us consider a tuple $\tilde{\tuple{t}}=(x_1,\ldots,x_{k+p-1})\in\family{B}_3$. We know that $\tilde{h}(x)=c_A$ if and only if $x=c_B$, thus $\tilde h(\tilde{\tuple{t}})\in\family{A}_3$. Then $\relation{R}^{\tilde{\structure{A}}}(\tilde h(\tilde{\tuple{t}}))=\relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}})=0.$ We have shown that $\tilde{h}$ is a homomorphism.

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

For any $\relation{R}_i\in\sigma$ and $\tuple{t}\in B^{k_i}$, $\tuple{t}$ corresponds to $\tilde{\tuple{t}}=(c_B,\ldots,c_B,\tuple{t},c_B\ldots,c_B)\in \family{B}_1$
and its image $h(\tuple{t})\in A^{k_i}$ corresponds to $\tilde{h}(\tilde{\tuple{t}}) = (c_A,\ldots,c_A,h(\tuple{t}),c_A,\ldots,c_A)\in\family{A}_1$. We know
that by the construction of $\tilde{\structure{A}}$ and $\tilde{\structure{B}}$, and by \cref{eq:frombtotildeb}:
\begin{displaymath}
\relation{R}_i^\structure{B}(\tuple{t}) = \relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}}) \preceq_\star \relation{R}^{\tilde{\structure{A}}}(\tilde h(\tilde{\tuple{t}})) = \relation{R}_i^\structure{A}(h(\tuple{t})).
\end{displaymath}
So, $h$ is a homomorphism and $\MP_\star^\sigma(\structure{A})$ reduces to $\MP_\star^{\tilde{\sigma}}(\tilde{\structure{A}})$.
\end{proof}

Now we have to find in polynomial time for any input $(\symb{\star},\tilde{\sigma})$-structure $\tilde{\structure{G}}$ of $\MP_\star^{\tilde{\sigma}}(\structure{A})$ a $(\symb{\star},\sigma)$-structure $\structure{B}$ such that
\begin{displaymath}
\tilde{\structure{G}}\to\tilde{\structure{A}}\Leftrightarrow\structure{B}\to\structure{A}.
\end{displaymath}

\begin{lemma}\label{lem:tildesigmatosigma}
$\MP_\star^{\tilde{\sigma}}(\tilde{\structure{A}})$ reduces in polynomial time to $\MP_\star^\sigma(\structure{A})$.
\end{lemma}
\begin{proof}
Let $\tilde{\structure{G}}$ be an input instance of $\MP_\star^{\tilde{\sigma}}(\tilde{\structure{A}})$. Firstly, for any element $x\in\tilde{G}$, we check
whether $\relation{R}^{\tilde{\structure{G}}}(x,\ldots,x)=\star$. If such an $x$ exists, then we cannot map $\tilde{\structure{G}}$ to $\tilde{\structure{A}}$
as for all $y\in\tilde{A}$ we have that $\relation{R}^{\tilde{\structure{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 $\MP_\star^\sigma(\structure{A})$, e.g., some $\structure{B}$ where there is $b\in B$ and
$\relation{R}_i^\structure{B}(b,\ldots,b)=\star$ for all $\relation{R}_i\in \sigma$.

Now we can assume that, for all $x\in\tilde{G}$, $\relation{R}^{\tilde{\structure{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:
\begin{equation}\label{eq:definingc1}
\textrm{for all}\ x\in\tilde{G},\ x\in C_i \Leftrightarrow \relation{R}^{\tilde{\structure{G}}}(x,\ldots,x) = i.
\end{equation}
Observe that if there exists a homomorphism $h\colon \tilde{\structure{G}}\to\tilde{\structure{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{\structure{B}}$ with the following properties:
\begin{enumerate}
        \item $\tilde{\structure{G}}\to\tilde{\structure{B}}$;
        \item $\tilde{\structure{G}}\to\tilde{\structure{A}}\Leftrightarrow\tilde{\structure{B}}\to\tilde{\structure{A}}$;
        \item Either we can check in $\polynomial$-time that $\tilde{\structure{B}}\not\to\tilde{\structure{A}}$ or there exists a $\sigma$-structure $\structure{B}$ such that $\tilde{\structure{B}}$ can be obtained from $\structure{B}$ by the construction described above in this section.
\end{enumerate}

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{\tuple{t}}=(b_1,\ldots,b_{k+p-1})\in\tilde{B}^{k+p-1}$. Denote by $\family{I}_{\tilde{\tuple{t}}}\subseteq[k+p-1]$ the set of indices such that $b_i=c_B$ in $\tilde{\tuple{t}}$. Denote by $\family{C}_{\tilde{\tuple{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
\begin{displaymath}
\forall i\in[k+p-1]\colon \left(i\in\family{I}_{\tilde{\tuple{t}}}\Rightarrow x_i \in C_1\right)\ \wedge \left(i\notin\family{I}_{\tilde{\tuple{t}}}\Rightarrow b_i=x_i\right).
\end{displaymath}
The interpretation $\relation{R}^{\tilde{\structure{B}}}$ is defined as follows, here $\bigvee$ denotes the join operation w.r.t. $\preceq_{\star}$:
\begin{equation}\label{eq:identifyingc1}
\relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}}) = \bigvee_{(x_1,\ldots,x_{k+p-1})\in\family{C}_{\tilde{\tuple{t}}}}\relation{R}^{\tilde{\structure{G}}}(x_1,\ldots,x_{k+p-1}).
\end{equation}
Observe that we can construct $\tilde{\structure{B}}$ in time polynomial in the size of the input $\tilde{\structure{G}}$.

Let us check the property 1, that $\tilde{\structure{G}}\to\tilde{\structure{B}}$. Let us consider a map $\pi\colon\tilde{G}\to\tilde{B}$ s.t.
\begin{itemize}
        \item if $x\in C_1$, then $\pi(x)=c_B$;
        \item if $x\in C_0$, then $\pi(x)=x$.
\end{itemize}
Consider a tuple $\tilde{\tuple{x}}=(x_1,\ldots,x_{k+p-1})\in\tilde{G}^{k+p-1}$ and $\pi(\tilde{\tuple{x}})=(b_1,\ldots,b_{k+p-1})\in\tilde{B}^{k+p-1}$ where
\begin{itemize}
        \item $b_i=c_B$, if $x_i\in C_1$;
        \item $b_i=x_i$, otherwise.
\end{itemize}
As $\tilde{\tuple{x}}\in\family{C}_{\pi(\tilde{\tuple{x}})}$, by \cref{eq:identifyingc1} we have $\relation{R}^{\tilde{\structure{G}}}(\tilde{\tuple{x}})\preceq_\star \relation{R}^{\tilde{\structure{B}}}(\pi(\tilde{\tuple{x}}))$. This proves that $\pi$ is a homomorphism.

Let us check the property 2, that $\tilde{\structure{G}}\to\tilde{\structure{A}}\Leftrightarrow\tilde{\structure{B}}\to\tilde{\structure{A}}$. As
$\tilde{\structure{G}}\to\tilde{\structure{B}}$, we need to show only one direction, i.e. $\Rightarrow$.  Assume that there is
$h_G\colon\tilde{\structure{G}}\to\tilde{\structure{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:
\begin{itemize}
        \item if $x=c_B$, then $h_B(x)=c_A$;
        \item if $x\not=c_B$, then $h_B(x)=h_G(x)$.
\end{itemize}
Consider a tuple $\tilde{\tuple{t}}=(b_1,\ldots,b_{k+p-1})\in\tilde{B}^{k+p-1}$. Observe that $h_B(\tilde{\tuple{t}}) = h_G(\family{C}_{\tilde{\tuple{t}}})$ that is any tuple from $\family{C}_{\tilde{\tuple{t}}}$ is mapped to $h_B(\tilde{\tuple{t}})$ by $h_G$. We know that
\begin{displaymath}
\relation{R}^{\tilde{\structure{A}}}(h_B(\tilde{\tuple{t}}))\succeq_\star \relation{R}^{\tilde{\structure{G}}}(x_1,\ldots,x_{k+p-1})
\end{displaymath}
for all $(x_1,\ldots,x_{k+p-1})\in\family{C}_{\tilde{\tuple{t}}}$. Thus,
\begin{displaymath}
\relation{R}^{\tilde{\structure{A}}}(h_B(\tilde{\tuple{t}}))\succeq_\star \bigvee_{(x_1,\ldots,x_{k+p-1})\in \family{C}_{\tilde{\tuple{t}}}}\relation{R}^{\tilde{\structure{G}}}(x_1,\ldots,x_{k+p-1}) = \relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}}).
\end{displaymath}
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: $\family{B}_1,\family{B}_2,\family{B}_3$. Observe that for any homomorphism $h:\tilde{\structure{B}}\to \tilde{\structure{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(\family{B}_j)\subseteq \family{A}_j$. At first, we look at the tuple $\tilde{\tuple{t}}=(c_B,\ldots,c_B)\in\family{B}_2$. By \cref{eq:definingc1,eq:identifyingc1}, we know that $\relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}})\succeq_\star 1$. If $\relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}})=\star$, then we output some fixed NO input instance of $\MP_\star^\sigma(\structure{A})$ for $\tilde{\structure{G}}$. If $\relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}})=1$, then we continue.

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

Now we can assume that $\relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}}_2)=1$ and $\relation{R}^{\tilde{\structure{B}}}(\tilde{\tuple{t}}_3)=0$, for all $\tilde{\tuple{t}}_2\in\family{B}_2,\tilde{\tuple{t}}_3\in\family{B}_3$. We are ready to construct the $(\symb{\star},\sigma)$-structure $\structure{B}$:
\begin{itemize}
        \item the domain $B$ of $\structure{B}$ is $\tilde{B}\setminus\{c_B\}$;
        \item for any relation $\relation{R}_i\in\sigma$ and any tuple $\tuple{t}=(b_1,\ldots,b_{k_i})\in B^{k_i}$ it is interpreted as follows:
        \begin{equation}\label{eq:fromtildebtob}
        \relation{R}^{\structure{B}}_i(\tuple{t})=\relation{R}^{\tilde{\structure{B}}}(\underbrace{c_B,\ldots,c_B}_{i-1},\tuple{t},\underbrace{c_B,\ldots,c_B}_{k+p-k_i-i}).
        \end{equation}
\end{itemize}

If we apply the $\tilde{(\cdot)}$-transformation to this $(\symb{\star},\sigma)$-structure $\structure{B}$, then we will get $\tilde{\structure{B}}$, because for all tuples of $\family{B}_2,\family{B}_3$: $\relation{R}^{\tilde{\structure{B}}}$ always has values 1 and 0 correspondingly, and for all tuples of $\family{B}_1$ there is a bijective correspondence with the tuples of all $\relation{R}_i\in\sigma$, the equivalence of their values is provided by \cref{eq:frombtotildeb,eq:fromtildebtob}. By \Cref{lem:sigmatotildesigma}, $\structure{B}\to\structure{A}$ if and only if $\tilde{\structure{B}}\to\tilde{\structure{A}}$.
We have shown that, for any $(\symb{\star},\tilde{\sigma})$-structure $\tilde{\structure{G}}$, we can find in time polynomial in $|\tilde{G}|$ a $(\symb{\star},\sigma)$-structure $\structure{B}$ such that $\tilde{\structure{G}}\to\tilde{\structure{A}}\Leftrightarrow \tilde{\structure{B}}\to\tilde{\structure{A}}$.
Thus $\MP_\star^{\tilde{\sigma}}(\tilde{\structure{A}})$ reduces in polynomial time to $\MP_\star^\sigma(\structure{A})$.
\end{proof}
\Cref{lem:sigmatotildesigma} and \Cref{lem:tildesigmatosigma} provide the following statement about the $\polynomial$-$\NPc$ dichotomy property.
\begin{theorem}\label{thm:manytoone}
If the class of problems $\MP_\star^{\tilde{\sigma}}$ has a dichotomy, then the class $\MP_\star^{\sigma}$ has a dichotomy.
\end{theorem}

Observe that in order to prove the other direction, for every $(\symb{\star},\tilde{\sigma})$-structure $\structure{A}$, we have to find a
$(\symb{\star},\sigma)$-structure $\hat{\structure{A}}$ such that $\MP_\star^{\sigma}(\hat{\structure{A}})$ and $\MP_\star^{\tilde{\sigma}}(\structure{A})$
are $\polynomial$-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 \Cref{fig:aritiesdiagram}. One can see now that the existence of a dichotomy for $\MP^{\tilde{\sigma}}$ implies such existence for all other classes considered on the figure.

\begin{figure}[ht]
\centering
\includegraphics{arities.pdf}
\caption{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 \Cref{sec:mpstar=mp}, and the horizontal ones are shown in \Cref{sec:arity}.}
\label{fig:aritiesdiagram}
\end{figure}

\subsection{From one relation to directed graphs}

In this section we do not prove that for any $(\symb{\star},\tilde{\sigma})$-structure $\structure{H}$, with $\tilde{\sigma}$ consisting of one single symbol,
there exists a $\star$-graph $\structure{H}_2$ such that the two problems $\MP_\star^{\tilde{\sigma}}(\structure{H})$ and $\MP_\star(\structure{H}_2)$ are
$\polynomial$-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 \cite{bulin2015,federvardi1998} 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} = \{\relation{R}(\cdot,\cdot,\cdot)\}$ to $\star$-graphs. In the very
beginning, we are going to show that if there exists such a correspondence between $(\symb{\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 $\family{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
$\structure{G}\in \family{G}_2^n$ cannot have an element $x$ with $\relation{E}^{\structure{G}}(x,x)=\star$. Let $\family{G}_3^n$ be the class of
$(\symb{\star},\tilde{\sigma})$-structures with the same property.

\begin{lemma}\label{lem:3to2many} For every positive integer $n$, $|\family{G}_3^n| \geq |\family{G}_2^n| \cdot 3^{n(n-1)^2-1}$.

\end{lemma}
\begin{proof}
  We suppose that all $\structure{G}\in\family{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 $\structure{G}\in\family{G}_2^n$. We will construct a family of
  $(\symb{\star},\tilde{\sigma})$-structures $\family{G}_\structure{G}$ of size $3^{n(n-1)^2-1}$ such that every two
  $(\symb{\star},\tilde{\sigma})$-structures from there will not be homomorphically equivalent. We will construct such a class for every $\star$-graph in
  $\family{G}_2^n$, and then show that any two structures from different classes will not be homomorphically equivalent as well.

Any $\structure{G}_3\in\family{G}_\structure{G}$ must satisfy the following properties:
\begin{itemize}
    \item the domain is the same as the one of $\structure{G}$: $G_3 = G = \{a,x_1,\ldots,x_{n-1}\}$;
    \item for all $x,y\in G_3\colon \relation{R}^{\structure{G}_3}(a,x,y) = \relation{E}^\structure{G}(x,y)$ -- we define all the relations of $\structure{G}$
      using only the triples that have $a$ on the first coordinate;
    \item for all $x\in G_3\setminus\{a\}\colon \relation{R}^{\structure{G}_3}(x,x,x) = 1 - \relation{E}^\structure{G}(a,a)$ -- all the elements other than $a$
      have the value on the loop, that is different from the loop $\relation{R}^{\structure{G}_3}(a,a,a)=\relation{E}^\structure{G}(a,a)$; the \emph{loop property}
    \item for all $i,j\in [n]$,  $\relation{R}^{\structure{G}_3}(x_i,x_j,a) = \star$ if $i<j$ and $\relation{R}^{\structure{G}_3}(x_i,x_j,a) = 0$ if $i\geq j$;
      the \emph{linear ordering property}
    \item 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 $\relation{R}^{\structure{G}_3}(x_{i_1},x_{i_2},x_{i_3})=\star$.
\end{itemize}
The values are restricted for the $n^2$ tuples that correspond to the edges of $\structure{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
$\relation{R}^{\structure{G}_3}$ among $\{0,1,\star\}$. Thus,
\begin{displaymath}
|\family{G}_\structure{G}| = 3^{n^3 - n^2 - (n-1)^2 - (n-1)-1} = 3^{n(n - 1)^2-1}.
\end{displaymath}
Let us consider $\structure{A},\structure{B}\in\family{G}_\structure{G}$, suppose that there is a homomorphism $h\colon\structure{A}\to\structure{B}$, then $h(a)
= a$ and for all $x\not=a$, $h(x)\not=a$ by the loop property of $\structure{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 $\structure{A}_1\in\family{G}_{\structure{G}_1},\structure{A}_2\in\family{G}_{\structure{G}_2}$ -- structures from different classes of two
$\star$-graphs $\structure{G}_1,\structure{G}_2$ that are not hom-equivalent. Suppose that there is no homomorphism from $\structure{G}_1$ to $\structure{G}_2$
and there is a homomorphism $h\colon \structure{A}_1\to\structure{A}_2$. If $\relation{E}^{\structure{G}_1}(a,a) \not= \relation{E}^{\structure{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 $\relation{E}^{\structure{G}_2}(a,a) \not=\star$ on one
hand and
$\star = \relation{R}^{\structure{A}_1}(x_{i_1},x_{i_2},x_{i_3})\preceq_\star \relation{R}^{\structure{A}_2}(a,a,a) = \relation{E}^{\structure{G}_2}(a,a)$ on
the other hand. Thus, we assume that $\relation{E}^{\structure{G}_1}(a,a) = \relation{E}^{\structure{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 $\structure{G}_1$ to $\structure{G}_2$ that is a contradiction as $\structure{G}_1$ and $\structure{G}_2$ are pairwise not homomorphically equivalent.

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

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.

\begin{corollary}
Let $n,m\in\mathbb{N}$. If $|\family{G}_3^n| < |\family{G}_2^m|$, then $m > \sqrt{n(n-1)^2-1}$.
\end{corollary}
\begin{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 \Cref{lem:3to2many}:
\begin{displaymath}
3^{m^2}\geq |\family{G}_2^m| > |\family{G}_3^n| \geq 3^{n(n-1)^2-1}|\family{G}_2^n| \geq 3^{n(n-1)^2-1} \Rightarrow m^2 > n(n-1)^2-1.
\end{displaymath}
\end{proof}

We will argue that all the approaches similar to the one used in \cite{bulin2015} do not work for the case of $\MP_\star$ (equivalently $\MP$, see
\Cref{sec:mpstar=mp}). Such an approach can be described by these steps: for any $(\symb{\star},\tilde{\sigma})$-structure $\structure{H}_3$ the corresponding
$\star$-graph $\structure{H}_2$ is constructed as follows:
\begin{enumerate}
    \item take the same domain $H_2=H_3$ and
    \item substitute every tuple $\relation{R}^{\structure{H}_3}(x_1,x_2,x_3)$ by a $\star$-graph $\structure{T}^v_{x_1x_2x_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 $\structure{T}$ stands for ``tuple'' and the superscript $v$ is for
      ``value''. It is required that for two different tuples $\tuple{t_1}$ and $\tuple{t_2}$, the domains of $\structure{T}^{v_1}_{\tuple{t_1}}$ and of
      $\structure{T}^{v_1}_{\tuple{t_2}}$ intersect only on $H_3$.
\end{enumerate}

So, the domain of $\structure{H}_2$ is the union of the domain $H_3$ of the $(\symb{\star},\tilde{\sigma})$-structure $\structure{H}_3$ and the domains of all the $\star$-graphs $\structure{T}^v$ that represent the tuples of $\structure{H}_3$:
\begin{displaymath}
H_2 = H_3\cup\bigcup_{(x_1,x_2,x_3)\in H_3^3,\ \relation{R}^{\structure{H_3}}(x_1,x_2,x_3)=v}T^v_{x_1x_2x_3}.
\end{displaymath}
This union is not disjoint because each $\structure{T}^v$ contains elements of $H_3$.

In \cite{bulin2015} every such $\structure{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 $\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 $\structure{H}_2$:
\begin{enumerate}
    \item For each $\star$-graph $\structure{T}^v_{x_1x_2x_3}$ that represents a tuple $\relation{R}^{\structure{H}_3}(x_1,x_2,x_3)=v$, the problem $\MP_\star(\structure{T}^v_{x_1x_2x_3})$ is solvable in $\polynomial$-time and $v_x=\relation{R}^{\structure{H}_3}(x_1,x_2,x_3) \preceq_\star \relation{R}^{\structure{H}_3}(y_1,y_2,y_3)=v_y$ if and only if $\structure{T}^{v_x}_{x_1x_2x_3}\to\structure{T}^{v_y}_{y_1y_2y_3}$.
    \item Let $\structure{H}_2,\structure{H}_2'$ be two $\star$-graphs obtained from $(\symb{\star},\tilde{\sigma})$-structures
      $\structure{H}_3,\structure{H}_3'$ by this approach. Then, for any homomorphism $h\colon \structure{H}_2\to\structure{H}_2'$, it is true that
      for all $x\in H_2$, $x\in H_3 \subseteq H_2 \Leftrightarrow h(x)\in H_3'\subseteq H_2'$.
    \item For each $\star$-graph $\structure{A}$ that is an input instance of $\MP_\star(\structure{H}_2)$, one can decide in time polynomial in $|A|$ which
      elements of $\structure{A}$ can only map to the elements of $H_3$. That is, we can decide, for every $x\in A$, if any
      $h\colon \structure{A}\to\structure{H}_2$, implies that $h(x)\in H_3\subset H_2$. Also, for every $x\in A$, either any homomorphism from
      $\structure{A}\to \structure{H}_2$ maps $x$ to $H_3$, or any homomorphism from $\structure{A}\to \structure{H}_2$ maps $x$ to $H_2\setminus H_3$.
    \item For two elements $w,w'\in H_2$ such that $w,w'\notin H_3$ and $w,w'$ do not belong to the same $T^v_{xyz}$, then $\relation{E}^{\structure{H}_2}(w,w') = 0$.
    \item Let $\structure{A}$ be a $\star$-graph. Suppose that for some $v\not=v'$ there is $h\colon\structure{A}\to\structure{T}^v_{xyz}$ and $\structure{A}\not\to\structure{T}^{v'}_{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:
    \begin{itemize}
        \item for every $1\leq i<n$, $h(a_i)\not\in\{x,y,z\}$,
        \item for every $0\leq i<n$, $\relation{E}^\structure{A}(a_i,a_{i+1})\not=0$ or $\relation{E}^\structure{A}(a_{i+1},a_i)\not=0$.
    \end{itemize}
    Then, for any other $h'\colon\structure{A}\to\structure{T}^v_{xyz}$ and for all $a\in A$ such that $h(a)\in\{x,y,z\}$, we have that $h(a)=h'(a)$.
\end{enumerate}

In particular, the reduction from $\CSP^\sigma$ to $\CSP$ on directed graphs in \cite{bulin2015} satisfies the first four conditions. The fifth one cannot be applied
to $\CSP$ because there are no three different types of $\structure{T}^v$ in that case. Any polynomial time reduction satisfying these five conditions, cannot
prove the $\polynomial$-equivalence with $\star$-graphs, unless $\CSP$ is $\polynomial$-time equivalent to $\MP$. We assume that $\CSP$ is equivalent to $\MP_\varnothing$ by \Cref{sec:fromemptysettocsp}.

\begin{proposition}\label{prop:twotoincomplete}
  Let a $\star$-graph $\structure{H}_2$ be constructed from some $(\symb{\star},\tilde{\sigma})$-structure $\structure{H}_3$ and satisfy all the five
  conditions above. Then $\MP_\star^{\tilde{\sigma}}(\structure{H}_3)$ reduces in $\polynomial$-time to $\MP_\star(\structure{H}_2)$, and $\MP_\star(\structure{H}_2)$
  reduces in $\polynomial$-time to $\MP_\varnothing^{\tilde{\sigma}}(\structure{H}_3)$.
\end{proposition}
\begin{proof}
Consider $(\symb{\star},\tilde{\sigma})$-structures $\structure{G}_3,\structure{H}_3$ and the corresponding $\star$-graphs $\structure{G}_2$ and $\structure{H}_2$ that satisfy the conditions 1--5. If there is $h\colon\structure{G}_3\to\structure{H}_3$, then, by the conditions 1 and 2, there is $h_2\colon\structure{G}_2\to\structure{H}_2$. If there is $h_2\colon\structure{G}_2\to\structure{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 $\structure{G}_3$ and $\structure{H}_3$.

Now, consider any $\star$-graph $\structure{A}$ from the input of $\MP_\star(\structure{H}_2)$. By the condition 3, we can mark in $\polynomial$-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 $\relation{E}^\structure{A}(a_i,a_{i+1})\not=0$ or
$\relation{E}^\structure{A}(a_{i+1},a_i)\not=0$. For every $eq$-equivalence class $A_a$ (containing an element $a$), consider an induced $\star$-subgraph
$\structure{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
$\relation{E}^\structure{A}(b,c)\not=0$ or $\relation{E}^\structure{A}(b,c)\not=0$. Below we will show that the image of every $\structure{A}_a$ can only be
contained in some $\structure{T}^v_{xyz}$.

\begin{claim}\label{cl:a_atot}
If there is $h\colon \structure{A}_a\to\structure{H}_2$, then $h({A}_a)\subseteq {T}^v_{xyz}$ for some $\structure{T}^v_{xyz}$.
\end{claim}
\begin{proof}[Proof of \Cref{cl:a_atot}]
  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 $\relation{E}^\structure{A}(a_i,a_{i+1})$ and $\relation{E}^\structure{A}(a_{i+1},a_i)$ is not $0$. As for all
  $a\in A\setminus A_3$ and for all $h'\colon\structure{A}\to\structure{H}_2$, $h'(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 $\structure{H}_2$ any two elements $w$ and $w'$ belonging to different $\structure{T}^v,\structure{T}^{v'}$,
  $\relation{E}^{\structure{H}_2}(w,w')=0$, we have that all $h(a_0),\ldots,h(a_n)$ are in the same $\structure{T}^v$.
\end{proof}

By the condition 1, we find in $\polynomial$-time for every $\structure{A}_a$ the list of values $v\in\{0,1,\star\}$ such that $\structure{A}_a$ maps to
$\structure{T}^v_{xyz}$. If $\structure{A}_a\not\to\structure{T}^v_{xyz}$ for any $v$, then there is no way that $\structure{A}$ can be mapped to
$\structure{H}_2$ and we reject this instance. Among all $v$ such that $\structure{A}_a\to\structure{T}^v$, we label $\structure{A}_a$ with the smallest
possible such $v$ with respect to $\preceq_\star$. If $\structure{A}_a$ maps to $\structure{T}^v_{xyz}$ for any possible $v$, then we say that
$\structure{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 $\structure{A}_a\ni a_1,a_2$ and there is $h\colon \structure{A}_a\to\structure{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 \structure{A}\to\structure{H}_2\Rightarrow h(a_1)=h(a_2)$.  Let us construct a new $\star$-graph
$\structure{A}_2$ based on $\structure{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 $\structure{T}_{a_1a_2a_3}^v$
following the rules below.  Consider $\structure{A}_a$ labelled with $v\not=\varnothing$ such that for any element $x\in H_3$ (or $y$ or $z$) of
$\structure{T}^v_{xyz}$ there exists an $A_3$-element $a_x$ of $\structure{A}_a$ such that $a_x$ is mapped to $x$. In this case we substitute $\structure{A}_a$
by $\structure{T}^v_{a_xa_ya_z}$ for $a_x,a_y,a_z\in A_2$.  Consider those $\structure{A}_a$ labelled with $v\not=\varnothing$ where there exists an element
$x\in H_3$ (or $y$ or $z$) of $\structure{T}^v_{xyz}$ so that no element $a_x$ of $\structure{A}_a$ maps to $x$. For such a case we add to $A_2$ a new element
$a_{\structure{A}_a,x}$ and substitute $\structure{A}_a$ by $\structure{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 $\structure{A}_2$. The $\star$-graph $\structure{A}_2$ corresponds to a
$(\symb{\varnothing}, \tilde{\sigma})$-structure $\structure{A}_3$ as follows: each triple $a_1,a_2,a_3$ of $A_3$ is either contained in
$\structure{T}^v_{a_1a_2a_3}$ or not. If yes, then we set $\relation{R}^{\structure{A}_3}(a_1,a_2,a_3) = v$, if not, then
$\relation{R}^{\structure{A}_3}(a_1,a_2,a_3)=\varnothing$. It is routine to check now that $\structure{A}\to \structure{H_2}$ if and only if $\structure{A_3}\to
\structure{H_3}$.
\end{proof}

\section{Obstructions}\label{sec:obstructions}

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

\begin{theorem}\label{thm:finite-O1-star} Let $\structure{H}$ be a $\star$-structure. Then, the following are equivalent.
  \begin{enumerate}
  \item $\Obs_{01}^\to(\structure{H})$ is finite.
  \item $\Obs_{01}^\subset(\structure{H})$ is finite.
  \item $\Obs_{\star}^\to(\structure{H})$ is finite.
  \item $\Obs_{\star}^\subset(\structure{H})$ is finite.
  \end{enumerate}
\end{theorem}

Throughout this section, let $\sigma=\{\relation{R}_1,\ldots,\relation{R}_p\}$ be a fixed signature. We recall that, for $*\in\{01,\star,\varnothing\}$, $\Cat_*$ is the set of all $(\symb{*},\sigma)$-structures.

Let us now recall the definition of obstructions from \cite{federhell2007}, that we extend to all structures.

\begin{definition}[\cite{federhell2007}] Let $* \in \{01,\star,\varnothing\}$ and let $\structure{H}$ be a $\star$-structure.  A $*$-structure
  $\structure{G}$ is called an \emph{inclusion-minimal obstruction} for $\MP_*(\structure{H})$ if $\structure{G}\not\to\structure{H}$ and for all $v\in G$,
  $\structure{G}\setminus\{v\}\to\structure{H}$. The set of all obstructions for the problem $\MP_*(\structure{H})$ is denoted by
  $\Obs_*^\subset(\structure{H})$.
\end{definition}

We propose below another definition, that uses homomorphisms.

\begin{definition} Let $* \in \{01,\star,\varnothing\}$ and let $\structure{H}$ be a $\star$-structure.  A $*$-structure $\structure{G}$ is called a
  \emph{hom-minimal obstruction} for a problem $\MP_*(\structure{H})$ if (1) $\structure{G}$ is a core and $\structure{G}\not\to\structure{H}$, and (2) for
  every $\structure{G}'$ such that $\structure{G}'\to\structure{G}$ and $\structure{G}\not\to\structure{G}'$, we have that
  $\structure{G}'\to\structure{H}$. The set of all hom-minimal obstructions for $\MP_*(\structure{H})$ is denoted by $\Obs_*^\to(\structure{H})$.
\end{definition}

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 \Cref{fig:obs_diagram} all the equivalences that we have proved.

\begin{figure}[ht]
\centering
\includegraphics{obs_diagram.pdf}
\caption{Every arrow of this diagram states that : if the class at the tail is finite, then the class at the head is finite.}
\label{fig:obs_diagram}
\end{figure}

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

\begin{observation}\label{obs:hom-min-inc-min} Any hom-minimal obstruction is inclusion-minimal.
\end{observation}

\begin{proof} Let $\structure{H}$ be a $\star$-structure, and let $*\in \{01,\star,\varnothing\}$. Suppose that
  $\structure{G}\in \Obs_*^\to(\structure{H})$. Consider any proper induced substructure $\structure{G}'$ of $\structure{G}$. Then,
  $\structure{G}\not\to\structure{G}'$ (recall $\structure{G}$ is a core), and so $\structure{G}'\to\structure{H}$. Then
  $\structure{G}\in \Obs_*^\subset(\structure{H})$.
\end{proof}

\begin{proposition}\label{prop:homimpliesinclusion}
  $\Obs_{01}^{\subset}(\structure{H})=\Obs_{01}^\to(\structure{H})$.
\end{proposition}

\begin{proof} We have that $\Obs_{01}^{\subset}(\structure{H})\subseteq\Obs_{01}^\to(\structure{H})$ by \Cref{obs:hom-min-inc-min}. For the other direction, let $\structure{G}$ be an inclusion-minimal
  $01$-obstruction. First, $\structure{G}$ is a core, otherwise it contains a strict induced substructure that does not map to $\structure{H}$,
  a contradiction.  Assume now that $\structure{G}$ is not hom-minimal. Then, there exists a $01$-structure $\structure{G}_1$ that is a core and there is
  $h\colon \structure{G}_1\to \structure{G}$, and $\structure{G}\not\to \structure{G}_1$, and both $\structure{G},\structure{G}_1$ do not map to
  $\structure{H}$. Let $G'=h(G_1)$ and let $\structure{G'}$ be the substructure of $\structure{G}$ induced by $G'$. If $\structure{G'}$ is a proper induced
  substructure of $\structure{G}$, then by the assumption of inclusion-minimality, and by transitivity of homomorphism: $\structure{G}_1\to \structure{H}$ -- a
  contradiction. Thus, $h(G_1) = G$, but since $h$ is a full homomorphism, we have that $\structure{G}$ is either a proper induced substructure of
  $\structure{G}_1$, which would contradict our assumption that $\structure{G}_1$ is a core, or is isomorphic to $\structure{G_1}$, which would contradict the
  assumption that $\structure{G}\not\to\structure{G_1}$. We can then conclude that $\structure{G}$ is hom-minimal.
\end{proof}

The following proposition shows that if $\structure{H}\in\Cat_{01}$, then these two classes are not the same: $\Obs_\star^{\subset}(\structure{H})\ne \Obs_\star^\to(\structure{H})$.

\begin{proposition}\label{prop:obs-star1} For all $01$-structures $\structure{H}$, $\Obs_\star^{\subset}(\structure{H})\ne \Obs_\star^\to(\structure{H})$.
\end{proposition}

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

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 $\family{F}$ of $*$-structures is a \emph{duality set} for the problem $\MP_*(\structure{H})$ if
\begin{align*}
  \structure{G}\notin \MP_*(\structure{H}) & \Longleftrightarrow \structure{F}\to \structure{G}, \qquad \textrm{for some $\structure{F}\in
                                                \family{F}$.}
\end{align*}
If, moreover, the set $\family{F}$ is finite, we say that $\MP_*(\structure{H})$ has \emph{finite duality}. One checks that if $\family{F}$ is a duality set
for $\MP_*(\structure{H})$, then no $*$-structure in $\family{F}$ belongs to $\MP_*(\structure{H})$. Hence, we can state the following. Indeed, one
can see $\Obs_*^\to$, for $*\in \{01,\star,\varnothing\}$, as a concrete duality set.

\begin{proposition}\label{prop:finite-duality} Let $*\in \{01,\star,\varnothing\}$ and let $\structure{H}$ be a $\star$-structure. Then, $\MP_*(\structure{H})$ has finite duality if and only if
  $\Obs_*^\to(\structure{H})$ is finite.
\end{proposition}

While \Cref{prop:obs-star1} 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.

\subsection{Finiteness of obstruction sets for $01$-structures and $\star$-structures}

We prove \Cref{thm:finite-O1-star} in this section. From now on, we fix $\structure{H}$ a $\star$-structure. We have proved in \Cref{prop:homimpliesinclusion} that \Cref{thm:finite-O1-star}(1.) and \Cref{thm:finite-O1-star}(2.) are equivalent. We prove the other equivalences
with the following propositions. The following proves that \Cref{thm:finite-O1-star}(3.) is equivalent to \Cref{thm:finite-O1-star} (1.).

\begin{proposition}\label{prop:hommin-star-01}
$\Obs_\star^\to(\structure{H}) = \Obs_{01}^\to(\structure{H})$.
\end{proposition}

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

  We turn our attention to the right inclusion. By \Cref{thm:mpstardichotomy}, for any $\structure{G}\in\Cat_\star\setminus\Cat_{01}$, there exists
  $\structure{G}_{01}\in\Cat_{01}$ such that
  \begin{itemize}
    \item there is a surjective homomorphism $\pi_\structure{G}\colon\structure{G}_{01}\twoheadrightarrow\structure{G}$;
    \item $\structure{G}\not\to\structure{G}_{01}$;
    \item $\structure{G}\in \MP_\star(\structure{H})\Leftrightarrow\structure{G}_{01}\in\MP(\structure{H})$.
    \end{itemize}
    Thus $\structure{G}\in \Obs_\star^\to(\structure{H})$ only if it is a $01$-structure. Therefore, $\Obs_\star^\to(\structure{H}) \subseteq \Obs_{01}^\to(\structure{H})$.
\end{proof}

The following proves the equivalence between the parts \Cref{thm:finite-O1-star}(2.) and \Cref{thm:finite-O1-star}(4.).

\begin{proposition}
$\Obs_\star^\subset(\structure{H})$ is finite if and only if $\Obs_{01}^\subset(\structure{H})$ is finite.
\end{proposition}

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

  Let us now turn our attention to the left implication.  Let us consider the class $\overline{\Obs_{01}^\subset}(\structure{H})$, that is obtained from
  $\Obs_{01}^\subset(\structure{H})$ by taking all $\star$-structures $\structure{A}$ such that there exists a surjective homomorphism
  from $\structure{B}$ to $\structure{A}$ for some $\structure{B}\in \Obs_{01}^\subset(\structure{H})$. Observe that
  $|\overline{\Obs_{01}^\subset}(\structure{H})|$ is finite. We know by \Cref{thm:mpstardichotomy} that, for any
  $\structure{G}\in \Obs_\star^\subset(\structure{H})$, there exists a $01$-structure $\structure{G}_{01}$ such that:
\begin{itemize}
    \item there is a surjective homomorphism $\pi_\structure{G}\colon\structure{G}_{01}\twoheadrightarrow\structure{G}$;
    \item $\structure{G}\not\to\structure{G}_{01}$;
    \item $\structure{G}\in \MP_\star(\structure{H})\Leftrightarrow\structure{G}_{01}\in\MP(\structure{H})$.
\end{itemize}
Because $\structure{G}\notin \MP_\star(\structure{H})$, we can conclude that $\structure{G}_{01}\notin \MP(\structure{H})$. And because $\structure{G}_{01}$ is
a $01$-structure, there exists $\structure{G}_{01}'\in\Obs_{01}^\subset(\structure{H})$ such that $\structure{G}_{01}'$ is an induced substructure
of $\structure{G}_{01}$, and thus, by transitivity, $\structure{G}_{01}'\to\structure{G}$. By inclusion-minimality of $\structure{G}$ (recall that
$\structure{G}\in \Obs_\star^\subset(\structure{H})$), this homomorphism is surjective, i.e. $\structure{G}\in\overline{\Obs_{01}^\subset}(\structure{H})$. We
have thus proved that $\Obs_\star^\subset(\structure{H})\subseteq \overline{\Obs_{01}^\subset}(\structure{H})$, i.e. is finite.
\end{proof}

\subsection{Looking at obstructions in $\Cat_\varnothing$}

The goal now is to prove the remaining arrows in \Cref{fig:obs_diagram}. As in the previous section, let $\structure{H}$ be a fixed $\star$-structure. For a
$\varnothing$-structure $\structure{G}\in \Obs_\varnothing^\to(\structure{H})$, let $\family{G}_\structure{G}$ be the set of all $\star$-structures
$\structure{G'}$ obtained from $\structure{G}$ by setting $\relation{R}_i^{\structure{G'}}(\tuple{t})\in \{0,1,\star\}$ for any tuple $\tuple{t}\in G^{k_i}$
such that $\relation{R}_i^\structure{G}(\tuple{t}) = \varnothing$, for any $\relation{R}_i\in \sigma$.

\begin{proposition}\label{prop:emptycoversstar}
For every $\structure{G_\star}\in \Obs_\star^\to(\structure{H})$, there is $\structure{G}_\varnothing\in \Obs_\varnothing^\to(\structure{H})$ such that
$\structure{G_\varnothing}\to \structure{G_\star}$ and there is no $\structure{G}'_\star\in \Cat_\star$ such that
$\structure{G}_\varnothing\to\structure{G}'_\star\to\structure{G}_\star$. Moreover, for every $\varnothing$-structure $\structure{G}_\varnothing\in
\Obs_\varnothing^\to(\structure{H})$, there is only a finite number of $\star$-structures in $\Obs_\star^\to(\structure{H})$ with such a property.
\end{proposition}
\begin{proof} Let $\structure{G_\star}\in \Obs_\star^\to(\structure{H})$ and let $\structure{G_\varnothing}\in \Obs_\varnothing^\to(\structure{H})$ such that
  $\structure{G_\varnothing}\to \structure{G_\star}$ ($\structure{G_\varnothing}$ exists because $\structure{G_\star}\notin \MP_\star(\structure{H})$). We know
  that $\structure{G}_\varnothing\not\to\structure{H}$, so if there is another $\structure{G}'_\star$ such that
  $\structure{G}_\varnothing\to\structure{G}'_\star\to\structure{G}_\star$, we have $\structure{G}'_\star\notin \MP(\structure{H})$, but this
  contradicts $\structure{G}_\star\in \Obs_\star^\to(\structure{H})$.

  For the second part, let $\structure{G}_\varnothing\in \Obs_\varnothing^\to(\structure{H})$. Suppose that there is a $\star$-structure
  $\structure{G}_\star'\in \Obs_\star^\to(\structure{H})\setminus \family{G}_{\structure{G}_\varnothing}$, and that $\structure{G}_\varnothing\to\structure{G}_\star'$. Then, there is a
  homomorphism $h\colon G \to G'$ such that for any $\relation{R}_i$ and tuple $\tuple{t}\in G^{k_i}$, we have
  $\relation{R}_i^{\structure{G}_\star'}(h(\tuple{t}))\in \{0,1,\star\}$. It means that there exists a $\star$-structure $\structure{G}_\star^{\prime\prime}\in\family{G}_{\structure{G}_\varnothing}$
  such that $\structure{G}_\star^{\prime\prime}=h(\structure{G}_\varnothing)\hookrightarrow\structure{G}_\star'$, which contradicts our assumption that
  $\structure{G}'\in \Obs_\star^\to(\structure{H})$.
\end{proof}

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

\begin{corollary} If $\Obs_\varnothing^\to(\structure{H})$ is finite, then $\Obs_\star^\to(\structure{H})$ is finite.
\end{corollary}

\begin{proof} By \Cref{prop:emptycoversstar},
  $\Obs_\star^\to(\structure{H})\subseteq \bigcup_{\structure{G}\in\Obs_\varnothing^\to(\structure{H})} \family{G}_\structure{G}$. As $\family{G}_\structure{G}$ is finite, the family $\bigcup_{\structure{G}\in\Obs_\varnothing^\to(\structure{H})} \family{G}_\structure{G}$ if
  $\Obs_\varnothing^\to(\structure{H})$ is finite.
\end{proof}

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

\begin{proposition}
If $\Obs_\varnothing^\subset(\structure{H})$ is finite, then $\Obs_\star^\subset(\structure{H})$ is finite.
\end{proposition}
\begin{proof} Any $\star$-structure is also a $\varnothing$-structure. Then, $\Obs_\star^\subset(\structure{H})\subseteq \Obs_\varnothing^\subset(\structure{H})$.

\end{proof}

We are now going to prove that $\Obs_\varnothing^\subset(\structure{H})$ is finite if and only if $\Obs_\varnothing^\to(\structure{H})$ is.

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

We have proved in \Cref{prop:homimpliesinclusion} 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 \Cref{fig:obs_diagram}.

\begin{proposition}
  Assume that $\Obs_\varnothing^\to(\structure{H})$ exists. Then, if $\Obs_\varnothing^\subset(\structure{H})$ is finite, then
  $\Obs_\varnothing^\to(\structure{H})$ is finite.
\end{proposition}

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 \Cref{sec:fromemptysettocsp}, the bijection $(\cdot)_\CSP$ between $\varnothing$-structures and relational structures.

\begin{proposition}\label{prop:nocycle} For every  $\varnothing$-structure  $\structure{G}\in \Obs_\varnothing^\to(\structure{H})$, the corresponding relational
  structure $\structure{G}_\CSP$ does not contain a cycle.
\end{proposition}

To prove \Cref{prop:nocycle}, we will use \Cref{lem:girth_general}. We recall that  $\structure{G}_\CSP$, a relational $\sigma$-structure, has a \emph{cycle of length $n$} if there exist $n$ distinct elements $x_1,\ldots,x_n$ and $n$ distinct tuples $\tuple{t}_1,\ldots,\tuple{t}_n$ with $ \relation{R}^{\structure{G}_\CSP}_{i_j}(\tuple{t}_j)=1$ for some $\relation{R}_{i_j}\in\sigma$  such that for all $1\leq i\leq n-1$, $x_i\in\tuple{t}_i$, $x_i\in\tuple{t}_{i+1}$, and $x_n\in\tuple{t}_n, x_1\in\tuple{t}_1$. As $\varnothing$-structures bijectively correspond to relational structures by $(\cdot)_\CSP$, we can say that a $\varnothing$-structure $\structure{G}$ has a cycle if $\structure{G}_\CSP$ has one.

\begin{lemma}[\cite{federvardi1998}]\label{lem:girth_general}
 Let $\structure{G},\structure{H}$ be relational $\sigma$-structures such that $\structure{G}$ has a cycle. Then, for any $l\in\mathbb{N}$, there exists a relational $\sigma$-structure $\structure{G}'$ such that it hasn't cycles of length lesser than $l$, and $\structure{G}\to\structure{H}$ if and only if $\structure{G}'\to\structure{H}$.
\end{lemma}

\begin{proof}[Proof of \Cref{prop:nocycle}] Let $\structure{G}\in \Obs_\varnothing^\to(\structure{H})$ and assume that it contains a cycle of length $k$. Then, by \Cref{thm:binary-to-many} and \Cref{lem:girth_general}, there is a $\varnothing$-structure $\structure{G'}$ such that $\structure{G'}\to \structure{G}$, $\structure{G}\not\to
  \structure{G'}$, and $\structure{G'}\to \structure{H} \Leftrightarrow \structure{G}\to\structure{H}$. But, then $\structure{G}$
  cannot be a hom-minimal obstruction.
\end{proof}

It is possible to show that there exists $\structure{H}$ such that $\Obs_{01}^\subset(\structure{H})$ is finite and $\Obs_\varnothing^\subset(\structure{H})$ is infinite. Hence, there is no arrow on the \Cref{fig:obs_diagram} neither from $\Obs_\star^\subset(\structure{H})$ to $\Obs_\varnothing^\subset(\structure{H})$, nor from $\Obs_\star^\to(\structure{H})$ to $\Obs_\varnothing^\to(\structure{H})$.

\begin{proposition}\label{prop:emptyset_obstruction_infinite}
Let $\structure{H} = \structure{K}_2$ be a $01$-graph, the clique on $2$ vertices. Then $\Obs_{01}^\subset(\structure{H})$ is finite and $\Obs_\varnothing^\subset(\structure{H})$ is infinite.
\end{proposition}
\begin{proof}
Feder and Hell proved in \cite{feder_hell_obstructions_full_2008} that once $\structure{H}$ is a $01$-graph, the inclusion-minimal obstructions for $\MP(\structure{H})$ have bounded size. Thus, $\Obs_{01}^\subset(\structure{H})$ is finite.

Let us show that $\Obs_\varnothing^\subset(\structure{H})$ is infinite. Consider a $\varnothing$-graph $\structure{C}_{n}$ on the domain $C_n=\{v_1,\ldots,v_n\}$ with $\relation{E}^{\structure{C}_n}(v_i,v_{i+1})=1$ for all $i\in[n-1]$ and with $\relation{E}^{\structure{C}_n}(v_n,v_1)=1$, and with all other edges equal to $\varnothing$. The problem $\structure{C}_n\to\structure{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 $\structure{C}_n$ creates a $\varnothing$-graph that maps to $\structure{H}$. Thus, the set $\family{C} = \{\structure{C}_n\mid n\text{ is odd}\}$ is an infinite set of inclusion-minimal obstructions for $\MP_\varnothing(\structure{H})$.
\end{proof}

\section{Remarks on tractability}\label{sec:tractability}

Despite some cases (see for instance \cite{hell2014,federhellsplit2014,hell_transitive_2017}), the tractability of Matrix Partition Problems on some graph classes is not that studied. As we have proved some similarities with usual $\CSP$s, one can for instance ask whether well-known graph classes with tractable $\CSP$s still have tractable Matrix Partition Problems. However, this is unlikely and deserves to be investigated. Let us explain.

\emph{Tree-width} \cite{atserias2008,grohe2007} is a well-known graph parameter due to its numerous algorithmic applications, in particular,
any $\CSP(\structure{H})$ is polynomial time solvable in graphs of bounded tree-width. More importantly, asking whether for two graphs  $\structure{G}$ and
$\structure{H}$, there is a homomorphism from $\structure{G}$ to $\structure{H}$ can be solved in time $(|G|+|H|)^{poly(k)}$ with $k$ the tree-width of
$\structure{G}$.  A natural question is whether such an algorithm exists for Matrix Partitions. One can define the \emph{$\star$-tree-width} of a $\star$-graph
$\structure{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 $\ensuremath{\mathsf{FO}}$ the omitted edges using those that are present, and one checks easily, by Courcelle's theorem (see for instance \cite{courcelle2012}), for any fixed $\star$-graph $\structure{H}$, in time $f(k)\cdot |G|$ whether $\structure{G}\in \MP_\star(\structure{H})$, for any $\star$-graph $\structure{G}$ of $\star$-tree-width $k$. We prove however that, unless $\polynomial=\NP$, there is no algorithm running in time $(|G|+|H|)^k$ where $k$ is the $\star$-tree-width of $\structure{G}$, and on input $(\structure{G},\structure{H})$ checks whether $\structure{G}\in \MP_\star(\structure{H})$, even for $k=1$.

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

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

\begin{theorem}\label{thm:3sat}
The problem $\MP(\family{T}, -)$ is $\NPc$.
\end{theorem}

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:
\begin{displaymath}
    \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})
\end{displaymath}
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 $\structure{T}_\CSP$ and then obtain a $01$-tree $\structure{T}$ according to the definition.

To any variable $x_i$ we correspond an oriented path $\structure{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 \Cref{fig:paths} below.

 \begin{figure}[ht]
    \centering
    \includegraphics[width = 0.25\textwidth]{m_part_tree_paths.pdf}
    \caption{Correspondence between paths and variables.}
    \label{fig:paths}
\end{figure}

Let us denote by $\structure{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$. $\structure{N}_{ijk}$ is equal to $\structure{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 \Cref{fig:negs}:
\begin{displaymath}
    \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).
\end{displaymath}

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.35\textwidth]{m_part_tree_negs.pdf}
    \caption{Additional paths to distinguish clauses with the same variables but different negations.}
    \label{fig:negs}
\end{figure}

We will need the following result for the proof.

\begin{lemma}\label{lem:pathsincomp}\cite{bulin2015}
For any $i,j$:
\begin{displaymath}
\structure{P}_i \to \structure{P}_j \Leftrightarrow i=j.
\end{displaymath}
The same is also true for $\structure{N}_i,\structure{N}_j$.
\end{lemma}

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

We construct $\structure{T}_\CSP$ now. Firstly, add an element $r_T$ that will be the root of $\structure{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:

\begin{enumerate}
    \item Add the path $\structure{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.
    \item Concatenate an edge to the right end of each $\structure{N}_{i1i2i3}$.
    \item For variables $x_{i1},x_{i2},x_{i3}$ concatenate the paths $\structure{P}_{i1},\structure{P}_{i2},\structure{P}_{i3}$ to the head of the edge.
\end{enumerate}

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

Such a  $01$-tree $\structure{T}$ looks like the one on the \Cref{fig:input}.

\begin{figure}[ht]
    \centering
    \includegraphics[width = 0.35\textwidth]{m_part_tree_input.pdf}
    \caption{The construction of the  $01$-tree $\structure{T}$.}
    \label{fig:input}
\end{figure}

Let us construct a $\star$-graph $\structure{H}$. It is constructed in a similar fashion as $\structure{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:

\begin{enumerate}
    \item Add the path $\structure{N}_{i1i2i3}$ with its left end in $r_H$.
    \item Concatenate 7 edges to the right end of $\structure{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.
    \item To the head of each of these 7 edges we concatenate the 3 paths $\structure{P}_{i1},\structure{P}_{i2},\structure{P}_{i3}$, each such path $\structure{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.
\end{enumerate}

By now $\structure{H}$ is an oriented tree. We make it a  $01$-tree similarly as $\structure{T}$: $\relation{E}^\structure{H}(x,y) = 1$ if $x,y$ are adjacent, and $\relation{E}^\structure{H}=0$ otherwise. After that we make $\structure{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 $\relation{E}^\structure{H}(x,y) = 1$. The construction is presented on the \Cref{fig:target}.

\begin{figure}[ht]
    \centering
    \includegraphics[width = 0.5\textwidth]{m_part_tree_target.pdf}
    \caption{The construction of $\structure{H}$.}
    \label{fig:target}
\end{figure}

The goal of the edges between two copies of the same $\structure{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.

\begin{lemma}\label{lem:psize}
The size of both $\structure{T}$ and $\structure{H}$ is $O(mn)$, where $m$ is the number of clauses and $n$ is the number of variables in $\varphi$.
\end{lemma}
\begin{proof}
 The size of each $\structure{P}_i$ is $O(n)$, the size of each $\structure{N}_i$ is $O(1)$, so the size of $\structure{T}$ is $O(mn)$. $\structure{H}$ is 7 times larger than
 $\structure{T}$.
\end{proof}

\begin{lemma}\label{lem:root2root}
If there is a homomorphism $h\colon \structure{T}\to \structure{H}$, then the root $r_T$ of $\structure{T}$ is mapped to the root $r_H$ of $\structure{H}$.
\end{lemma}
\begin{proof}
For any oriented path starting in an element $a$ and ending in $b$ we say that an edge of the path is \emph{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 \emph{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 $\structure{H}$ that is the endpoint
of a copy of some path $\structure{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 $\structure{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 $\structure{T}$ to $\structure{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 $\relation{E}^\structure{H}(r_H,s)=1$. By the construction of $\structure{H}$, we know that $s$ belongs to the path $\structure{N}_i$ of the $i$th clause of $\varphi$. Which implies that all the paths $\structure{N}_j$ of $\structure{T}$ are mapped by a full homomorphism to the $\structure{N}_i$ of $\structure{H}$, which is impossible.
\end{proof}

\begin{proof}[Proof of \Cref{thm:3sat}]
 Let $v\colon\{x_1,\ldots,x_n\}\to\{0,1\}$ be an assignment for the variables of $\varphi$. By \Cref{lem:psize}, construct in $\polynomial$-time a $01$-tree $\structure{T}$ and a $\star$-graph $\structure{H}$ as above. Take the $i$th clause and map the corresponding part of $\structure{T}$ to the triple of paths that have
 labels corresponding to the assignment $v$. By  construction, it will be a homomorphism.

 Let $h\colon \structure{T}\to \structure{H}$ be a homomorphism. Then we know by \Cref{lem:root2root} that $h(r_T)=r_H$. By \Cref{lem:pathsincomp} we know that the part of $\structure{T}$ corresponding to the $i$th clause is mapped to the part of $\structure{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 $\structure{P}_x, \structure{P}_x'$ that correspond to the presence of the same variable $x$ in different clauses such that $\structure{P}_x$ is mapped to a path labelled with $0$ and $\structure{P}_x'$ is mapped to a path labelled with 1. Thus, all the paths
 $\structure{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 $\structure{H}$ all 7 possible valid assignments for each clause.
\end{proof}

\begin{remark}
Observe that the $01$-tree $\structure{T}$ that represents a 3-SAT formula also has bounded pathwidth, so the result of \Cref{thm:3sat} will remain true if we require that all the $01$-trees of $\family{T}$ have bounded pathwidth.
\end{remark}

\section{Conclusion}

We have proposed several generalisations of the Matrix Partition Problems studied by Hell et al.
We have shown that $\MP$ and $\MP_\star$ are $\polynomial$-time equivalent and we have used this to show that a dichotomy for every class $\MP^{\tilde{\sigma}}$ with $|\tilde{\sigma}|=1$ implies a dichotomy for $\MP^\sigma$ for any finite $\sigma$.
Despite this, we leave open the question of whether $\MP$ on directed graphs is $\polynomial$-time equivalent to $\MP^\sigma$, for any finite signature $\sigma$, and, a fortiori, the dichotomy question for $\MP$.
We have introduced the generalisation $\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. \cite{federhell2007} and have proved that their finiteness coincides with finite duality for $\MP$ and $\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 $\MP(\family{T},-)$.

\section*{Acknowledgement}
The authors thank Florent Madelaine for the many fruitful discussions on the subject.

\bibliographystyle{acm}