Minimum k-labeled triangle forest: complexity and greedy approximations - Ravelo, Santiago Valdés; Fernandes, Cristina G. (Anais do Encontro de Teoria da Computação (ETC), 2026)
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.