DIMACS TR: 2008-15

Neighborhood hypergraphs of digraphs and some matrix permutation problems



Authors: Vladimir Gurvich and Igor Zverovich

ABSTRACT

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.



Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2008/2008-15.pdf
DIMACS Home Page