Nordic Journal of Computing Bibliography

Jan Kratochvíl, Andrzej Proskurowski, and Jan Arne Telle. On the Complexity of Graph Covering Problems. Nordic Journal of Computing, 5(3):173-195, Fall 1998.

For 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


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database