Heavy and leafy trees

• Cristina G. Fernandes USP
• Carla N. Lintzmayer UFABC
• Mário César San Felice UFSCar

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

Resumo

The MAXIMUM WEIGHTED LEAF TREE problem consists of, given a connected graph G and a weight function w: V (G) → Q⁺, finding a tree in G whose weight on the leaves is maximized. The variant that requires the tree to be spanning is at least as hard to approximate as the maximum independent set problem. If all weights are unitary, it turns into the well-known problem of finding a spanning tree with maximum number of leaves, which is NP-hard, but is in APX. No further innapproximability result is known for MAXIMUM WEIGHTED LEAF TREE, and the best approximation is an O(lg n)-approximation. In this paper, we present an O(lg W)-approximation where W is the maximum weight divided by the minimum weight that appears on the vertices.

Palavras-chave: Approximation Algorithms, Leafy Trees, Weighted Problems

Referências

Alon, N., Fomin, F., Gutin, G., Krivelevich, M., and Saurabh, S. (2009). Spanning directed trees with many leaves. SIAM Journal on Discrete Mathematics, 23(1):466–476.

Daligault, J. and Thomassé, S. (2009). On Finding Directed Trees with Many Leaves. In International Workshop on Parameterized and Exact Computation, volume 5917 of Lecture Notes in Computer Science, pages 86–97.

Drescher, M. and Vetta, A. (2010). An Approximation Algorithm for the Maximum Leaf Spanning Arborescence Problem. ACM Transactions on Algorithms, 6(3).

Fernandes, C. G. and Lintzmayer, C. N. (2021). Leafy spanning arborescences in DAGs. Discrete Applied Mathematics. In press. Available also at https://arxiv.org/abs/2007.07660.

Galbiati, G., Maffioli, F., and Morzenti, A. (1994). A short note on the approximability of the maximum leaves spanning tree problem. Information Processing Letters, 52(1):45–49.

Gandhi, R., Hajiaghayi, M. T., Kortsarz, G., Purohit, M., and Sarpatwar, K. (2018). On maximum leaf trees and connections to connected maximum cut problems. Information Processing Letters, 129:31–34.

Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability. W.H. Freeman and Co., New York.

Schwartges, N., Spoerhase, J., and Wolff, A. (2011). Approximation algorithms for the Maximum Leaf Spanning Tree Problem on acyclic digraphs. In 9th Workshop on Approximation and Online Algorithms (WAOA), volume 7164 of Lecture Notes in Computer Science, pages 77–88.

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.