Leafy spanning k-forests


We 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.
Palavras-chave: Approximation algorithms, Maximum leaf spanning tree, Maximum leaf spanning forest


Lu, H. and Ravi, R. (1998). Approximating maximum leaf spanning trees in almost linear time. Journal of Algorithms, 29(1):132–141.

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.
FERNANDES, Cristina G.; LINTZMAYER, Carla N.; SAN FELICE, Mário César. Leafy spanning k-forests. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 6. , 2021, Evento Online. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2021 . p. 38-41. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2021.16375.