Leafy spanning k-forests
ResumoWe denote by Maximum Leaf Spanning k-Forest the problem of, given a positive integer k and a graph G with at most k components, finding a spanning forest in G with at most k components and the maximum number of leaves. A leaf in a forest is defined as a vertex of degree at most one. The case k = 1 for connected graphs is known to be NP-hard, and is well studied in the literature, with the best approximation algorithm proposed more than 20 years ago by Solis-Oba. The best known approximation algorithm for Maximum Leaf Spanning k-Forest with a slightly different leaf definition is a 3-approximation based on an approach by Lu and Ravi for the k = 1 case. We extend the algorithm of Solis-Oba to achieve a 2-approximation for Maximum Leaf Spanning k-Forest.
Reis, M. F., Felice, M. C. S., Lee, O., and Usberti, F. L. (2017). A 3-approximation algorithm for the maximum leaf k-forest problem. Electronic Notes in Discrete Mathematics, 62:201–206.
Solis-Oba, R. (1998). 2-Approximation algorithm for finding a spanning tree with maximum number of leaves. In Proceedings of the European Symposium on Algorithms (ESA), volume 1461 of Lecture Notes in Computer Science, pages 441–452.
Solis-Oba, R., Bonsma, P., and Lowski, S. (2017). A 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Algorithmica, 77:374–388.