Open AccessSuper-colored paths in digraphs
Author(s) -
Álvaro Junio Pereira Franco,
Marcelo E. Vendramin
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/etc.2021.16389
Subject(s) - colored , digraph , vertex (graph theory) , combinatorics , path (computing) , simple (philosophy) , mathematics , computer science , discrete mathematics , graph , philosophy , materials science , epistemology , composite material , programming language
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.