We show that the problem of covering cycles with loops, defined in Kratochvil 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.
展开▼
