  A trigraph is a graph where each pair of vertices is labelled either 0 (a
non-arc), 1 (an arc) or $\star$ (both an arc and a non-arc). In a series of
papers, Hell and co-authors proposed to study the complexity of homomorphisms
from graphs to trigraphs, called Matrix Partition Problems, where arcs and
non-arcs can be both mapped to $\star$-arcs, while a non-arc cannot be mapped
to an arc, and vice-versa. Even though Matrix Partition Problems are
generalisations of CSPs, they share with them the property of being
``intrinsically'' combinatorial. So, the question of a possible P-time vs
NP-complete dichotomy is a very natural one and was raised in Hell et al.'s
papers. We propose a generalisation of Matrix Partitions to relational
structures and study them with respect to the question of a dichotomy. We first
show that trigraph homomorphisms and Matrix Partitions are P-time equivalent,
and then prove that one can also restrict (with respect to having a dichotomy)
to relational structures with a single relation. Failing in proving that Matrix
Partitions on directed graphs are not P-time equivalent to Matrix Partitions on
relational structures, we give some evidence that it might be unlikely by
formalising the reductions used in the case of CSPs and by showing that such
reductions cannot work for the case of Matrix Partitions. We then turn our
attention to Matrix Partitions that can be described by finite sets of
(induced-subgraph) obstructions. We show, in particular, that any such problem
has finitely many minimal obstructions if and only if it has finite duality. We
conclude by showing that on trees (seen as trigraphs) it is NP-complete to
decide whether a given tree has a homomorphism to another input trigraph. The
latter shows a notable difference on tractability between CSP and Matrix
Partitions as it is well-known that CSP is tractable on the class of trees.
