Computational complexity of covering cyclic graphs Original Research Article

We show that the problem of covering cycles with loops, defined in Kratochvı́l et al. (Graph-Theoretical Concepts in Computer Science, Proceedings of the 23rd WG ’97, Berlin, Lecture Notes in Computer Science, Vol. 1335, Springer, Berlin, 1997, pp. 242–254) is NP-complete. We also prove NP-completeness of the 8-starfish cover problem, which concludes complete computational complexity characterization of k-starfish cover problems.