Complexity of colored graph covers I. Colored directed multigraphs

Abstract

A covering projection from a graph G onto a graph H is a “local isomorphism”: a mapping from the vertex set of G onto the vertex set of H such that, for every v ɛ V(G), the neighborhood of v is mapped bijectively onto the neighborhood (in H) of the image of v. We continue the investigation of the computational complexity of the H-cover problem — deciding if a given graph G covers H. We introduce a more general notion of covers of directed colored multigraphs (cdmgraphs) and show that a complete characterization of the complexity of covering of simple undirected graphs would necessarily resolve the complexity of covering of cdm-graphs as well. On the other hand, we introduce reductions that will enable to consider only multigraphs with minimum degree ≽ 3. We illustrate the methodology by presenting a complete characterization of the complexity of covering problems for two-vertex cdm-graphs.

Research partially supported by Czech Research grants GAUK 194/1996 and GAČR 0194/1996.

Third author supported by a fellowship from the Norwegian Research Council.