Complexity of the Girth Problem on Arc-colored Digraphs

• Manoel Campelo UFC
• Rafael de Paiva Lima UFC
• Cláudia Linhares Sales UFC

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

Resumo

The girth of a graph G = (V,E) is the length of its smallest cycle. This parameter is usually used as a support to obtain information about bounds or complexity of several other graph problems. In digraphs D = (V,A), the girth of D is determined by the length of the smallest directed cycle. In this work, we deal with the problem of determining the girth of edge-colored graphs, where the girth is the number of colors of a cycle with the smallest number of colors. This problem is open for general graphs. In this paper we prove that its decision version is NP-complete for arc-colored digraphs. Additionally, we prove that it is W[2]-hard on this class when parameterized by the number of colors to be minimized.

Referências

Bazgan, C. (1995). Schémas d’approximation et complexité paramétrée. Rapport de stage de DEA d’Informatiquea Orsay, 300.

Broersma, H. and Li, X. (1997). Spanning trees with many or few colors in edge-colored graphs. Discussiones Mathematicae Graph Theory, 17:259.

Broersma, H., Li, X., Woeginger, G., and Zhang, S. (2005). Paths and cycles in colored graphs. Australasian Journal of Combinatorics, 31:299 – 311.

Cesati, M. and Trevisan, L. (1997). On the efficiency of polynomial time approximation schemes. Information Processing Letters, 64(4):165–171.

Chang, R.-S. and Shing-Jiuan, L. (1997). The minimum labeling spanning trees. Information Processing Letters, 63(5):277–282.

dos Santos, V. F. and Souza, U. d. S. (2015). Uma introdução à complexidade parametrizada. Anais da 34º Jornada de Atualização em Informática, CSBC, pages 232–273.

Downey, R. G. and Fellows, M. R. (1998). Parameterized complexity. Monographs in Computer Science. Springer, New York, NY, 1999 edition.

Figueredo, P. J. d. A. (2020). O problema da floresta geradora k-rotulada. Dissertação de mestrado, Universidade Federal do Ceará.

Figueredo, P. J. d. A. and Campêlo, M. (2020). Propriedades do problema da floresta geradora k-rotulada. In Anais do V Encontro de Teoria da Computação, pages 69–72, Porto Alegre, RS, Brasil. SBC.

Granata, D., Cerulli, R., Scutellà, M. G., and Raiconi, A. (2013). Maximum Flow Problems and an NP-Complete Variant on Edge-Labeled Graphs, pages 1913–1948. Springer New York, New York, NY.

Karp, R. M. (1972). Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA.

Zhang, P., Cai, J.-Y., Tang, L.-Q., and Zhao, W.-B. (2011). Approximation and hardness results for label cut and related problems. Journal of Combinatorial Optimization, 21(2):192–208.