  A symmetric $m\times m$ matrix $M$ with entries taken from $\{0,1,\ast\}$
gives rise to a graph partition problem, asking whether a graph can be
partitioned into $m$ vertex sets matched to the rows (and corresponding
columns) of $M$ such that, if $M_{ij}=1$, then any two vertices between the
corresponding vertex sets are joined by an edge, and if $M_{ij}=0$ then any two
vertices between the corresponding vertex sets are not joined by an edge. The
entry $\ast$ places no restriction on the edges between the corresponding sets.
This problem generalises graph colouring and graph homomorphism problems.
  A graph with no $M$-partition but such that every proper subgraph does have
an $M$-partition is called a minimal obstruction. Feder, Hell and Xie have
defined friendly matrices and shown that non-friendly matrices have infinitely
many minimal obstructions. They showed through examples that friendly matrices
can have finitely or infinitely many minimal obstructions and gave an example
of a friendly matrix with an NP-hard partition problem. Here we show that
almost all friendly matrices have infinitely many minimal obstructions and an
NP-hard partition problem.
