NP-Hardness and Approximation Results for the Minimally Labeled k-Spanning Forest Problem

• Kennedy Corrêa USP / UFC
• Manoel Campêlo UFC

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

Abstract

Given an edge-labeled graph G, the minimum labeling spanning k-forest problem consists in finding a spanning forest F of G with minimum number of labels and number of components bounded by k. In this work, we present a proof of the NP-completeness of the problem in split graphs and propose an approximation algorithm for solving it.

References

Cerulli, R., Ambrosio, C., Serra, D., and Sorgente, C. (2024). The budgeted labeled minimum spanning tree problem. Mathematics, 12(2).

Cerulli, R., Fink, A., and Gentili, M. (2006). Extensions of the minimum labelling spanning tree problem. Journal of Telecommunications and Information Technology, 26(4):39–45.

Chang, R.-S. and Leu, S.-J. (1997). The minimum labeling spanning trees. Inf. Process. Lett., 63(5):277–282.

Chwatal, A. M., Raidl, G. R., and Dietzel, O. (2007). Compressing fingerprint templates by solving an extended minimum label spanning tree problem.

Corrêa, L. and Campêlo, M. (2024). O problema da k-floresta geradora minimamente rotulada. In Anais do LVI SBPO, Fortaleza.

Fellows, M. R., Guo, J., and Kanj, I. (2010). The parameterized complexity of some minimum label problems. Journal of Computer and System Sciences, 76(8):727–740.

Krumke, S. O. and Wirth, H.-C. (1998). On the minimum label spanning tree problem. Information Processing Letters, 66(2):81–85.

West, D. (1996). Introduction to Graph Theory. Introduction to Graph Theory. Prentice Hall.

Xiong, Y., Golden, B., and Wasil, E. (2005). Worst-case behavior of the mvca heuristic for the minimum labeling spanning tree problem. Operations Research Letters, 33(1):77–80.