Neighborhood hypergraphs of digraphs and some matrix permutation problems

Given a digraph DD, the set of all pairs (N−(v),N+(v))(N−(v),N+(v)) constitutes the neighborhood dihypergraph N(D)N(D) of DD. The Digraph Realization Problem asks whether a given dihypergraph HH coincides with N(D)N(D) for some digraph DD. This problem was introduced by Aigner and Triesch [M. Aigner, E. Triesch, Reconstructing a graph from its neighborhood lists, Combin. Probab. Comput. 2 (2) (1993) 103–113] 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}{0,1,−1} matrices (aij=−ajiaij=−aji) is NP-complete. This result can be compared with the known fact that the Matrix Symmetrization Problem for square 0–1 matrices (aij=ajiaij=aji) is NP-complete.Extending a negative result of Fomin, Kratochvíl, Lokshtanov, Mancini, and Telle [F.V. Fomin, J. Kratochvíl, D. Lokshtanov, F. Mancini, J.A. Telle, On the complexity of reconstructing HH-free graphs from their star systems, Manuscript (2007) 11 pp] 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.