Neighborhood hypergraphs of digraphs and some matrix permutation problems Original Research Article

Given a digraph image, the set of all pairs image constitutes the neighborhood dihypergraph image of image. The Digraph Realization Problem asks whether a given dihypergraph image coincides with image for some digraph image. 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.