Neighborhood hypergraphs of digraphs and some matrix permutation problems

• Published in: Discrete Applied Mathematics 2009-07, Vol.157 (13), p.2836-2845
• Main Authors: Gurvich, Vladimir, Zverovich, Igor E.
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Combinatorics; Combinatorics. Ordered structures; Computer science; control theory; systems; Exact sciences and technology; Functional analysis; Graph Isomorphism Problem; Graph theory; Information retrieval. Graph; Involutory automorphisms; Mathematical analysis; Mathematics; Matrix complementation; Matrix symmetrization; Neighborhood hypergraphs of digraphs and orgraphs; Sciences and techniques of general use; Skew-symmetrizability; Symmetrizability; Theoretical computing
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2009.03.023

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 [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 } matrices ( a i j = − a j i ) is NP-complete. This result can be compared with the known fact that the Matrix Symmetrization Problem for square 0–1 matrices ( a i j = a j i ) 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 H -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.