Minimum k-labeled triangle forest: complexity and greedy approximations

• Santiago Valdés Ravelo UNICAMP
• Cristina G. Fernandes USP

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

Resumo

We study the k-LABELED TRIANGLE FOREST problem, where, given a triangle-forest graph with edges colored from a set C, the goal is to select k colors to minimize the number of components. We prove the problem is NP-hard, provide a tight 5 3 -approximation via a greedy algorithm that selects the most fre quent colors, and give a (1+2/e)-approximation using a second greedy strategy that iteratively chooses the color maximizing the reduction in components.

Referências

R. Karp. Reducibility among combinatorial problems. volume 40, pages 85–103, 01 1972.

G. L. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3):177–188, 1978.

G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions—i. Mathematical Programming, 14:265–294, 1978.

T. F. Pinheiro, S. V. Ravelo, and L. S. Buriol. A fix-and-optimize matheuristic for the k-labelled spanning forest problem. In 2022 IEEE Congress on Evolutionary Computation (CEC), pages 1–8, 2022.

D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.