Covering a Tree by a Forest

摘要

Consider a tree T and a forest F. The paper discusses the following new problems: The Forest vertex-cover problem (FVC): cover the vertices of T by a minimum number of copies of trees of F, such that every vertex of T is covered exactly once. The Forest edge-cover problem (FEC): cover the edges of T by a minimum number of copies of trees of F, such that every edge of T is covered exactly once. For a solution to always exist, we assume that F contains a one vertex (one edge) tree.rnTwo versions of Problem FVC are considered: ordered covers (OFVC), and unordered covers (UFVC). Three versions of Problem FEC are considered: ordered covers (OFEC), unordered covers (UFEC) and consecutive covers (CFEC). We describe polynomial time algorithms for Problems OFVC, UFVC and CFEC, and prove that Problems OFEC and UFEC are NP-complete.