Point determining digraphs, {0,1}{0,1}-matrix partitions, and dualities in full homomorphisms

A digraph DD is point determining if for any two distinct vertices u,vu,v there exists a vertex ww which has an arc to (or from) exactly one of u,vu,v. We prove that every point-determining digraph DD contains a vertex vv such that D−vD−v is also point determining. We apply this result to show that for any {0,1}{0,1}-matrix MM, with kk diagonal zeros and ℓℓ diagonal ones, the size of a minimal MM-obstruction is at most (k+1)(ℓ+1)(k+1)(ℓ+1). This is a best possible bound, and it extends the results of Sumner, and of Feder and Hell, from undirected graphs and symmetric matrices to digraphs and general matrices.