## 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