AbstractFor a fixed graph

H, theH-cover problem asks whether an input graphGallows a degree preserving mappingf:V(G)->V(H)such that for everyvinV(G),f(N. In this paper we design efficient algorithms for certain graph covering problems according to two basic techniques. The first is based in part on a reduction to the 2-SAT problem. The second technique exploits necessary and sufficient conditions for the partition of a graph into 1-factors and 2-factors. For other infinite classes of graph covering problems we derive NP-completeness results by reductions from graph coloring problems. We illustrate this methodology by classifying the complexity of all_{G(v)})=N_{H(f(v))}H-cover problems defined by simple graphsHwith at most 6 vertices.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory

Additional Key Words and Phrases: local isomorphism, algorithms, complexity

Selected references

- Dana Angluin. Local and global properties in networks of processors (extended abstract). In Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pages 82-93, Los Angeles, California, 28-30 April 1980.

- Daniel Leven and Zvi Galil. NP completeness of finding the chromatic index of regular graphs. Journal of Algorithms, 4(1):35-44, March 1983.