AbstractFor a fixed graph H, the H-cover problem asks whether an input graph G allows a degree preserving mapping f:V(G) -> V(H) such that for every v in V(G), f(NG(v))=NH(f(v)). 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 H-cover problems defined by simple graphs H with 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.