Complexity of the Girth Problem on Arc-colored Digraphs - Campelo, Manoel; Lima, Rafael de Paiva; Sales, Cláudia Linhares (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2026.23502, 2026)
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.