Given a digraph D , the set of all pairs (N-(v), N+(v)) constitutes the neighborhood dihypergraph N(D) of D. The Digraph Realization Problem asks whether a given dihypergraph H coincides with N(D) for some digraph D. This problem was introduced by Aigner and Triesch as a natural generalization of the Open Neighborhood Realization Problem for undirected graphs, which is known to be NP-complete.
We show that the Digraph Realization Problem remains NP-complete for orgraphs (orientations of undirected graphs). As a corollary, we show that the Matrix Skew-Symmetrization Problem for square {0, 1, -1} matrices ( a{ij} = -a_{ji} ) is NP-complete. This result can be compared with the known fact that the Matrix Symmetrization Problem for square 0-1 matrices ( a{ij} = a{ji} ) is NP-complete. Extending a negative result of Fomin, Kratochv, Lokshtanov, Mancini and Telle we show that the Digraph Realization Problem remains NP-complete for almost all hereditary classes of digraphs defined by a unique minimal forbidden subdigraph.
Finally, we consider the Matrix Complementation Problem for rectangular 0-1 matrices, and prove that it is polynomial-time equivalent to graph isomorphism. A related known result is that the Matrix Transposability Problem is polynomial-time equivalent to graph isomorphism.
DIMACS Home Page