Algorithms for Super-coloring in Directed Graphs

Given a directed graph with colored vertices, for each vertex v, we want to know the largest number of colors that we can find in the vertices of a single path starting from v. Unlike other classical problems in colored graphs, there is no constraint that adjacent vertices must have different colors. Among the applications in literature, there is interest in Anthropology to investigate interaction between individuals from families and/or clans. This article seeks to design and analyze computational methods and some properties for this problem, particularly in directed acyclic graphs (DAG). As contributions, we constructed two algorithms and an integer programming model for this problem, and experimented them on real instances of genealogical data.