Super-colored paths in digraphs - Franco, Álvaro J. P.; Vendramin, Marcelo E. (Anais do Encontro de Teoria da Computação (ETC); 2021: Anais do VI Encontro de Teoria da Computação, 2021)
We work in an Anthropology application where it is desired to enumerate colored rings (structures that look like cycles) present in kinship net-works. For this goal, we came across the following question: for all vertex v of a vertex-colored digraph, how many colors (in maximum) a path starting in v can have? The answer for this question would help us to enumerate the colored rings since we would know how many colors a ring evolving some vertices could have, in maximum. Here, we call a path as v-super-colored if it starts in vertex v and it has the maximum amount of colors among all paths starting in v. We show that the problem to find the number of colors of v-super-colored paths for all v is NP-hard when the input digraph is general. We describe a simple algorithm which demonstrates that the problem is tractable if the input digraphis acyclic and the number of colors is small.