Leafy spanning k-forests

• Cristina G. Fernandes USP http://orcid.org/0000-0002-5259-2859
• Carla N. Lintzmayer UFABC https://orcid.org/0000-0003-0602-6298
• Mário César San Felice UFSCar https://orcid.org/0000-0001-6476-4534

DOI: https://doi.org/10.5753/etc.2021.16375

Resumo

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

Referências

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.