Super-colored paths in digraphs

  • Álvaro J. P. Franco UFSC
  • Marcelo E. Vendramin UFSC

Resumo


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.

Palavras-chave: graph, path, ring, colors

Referências

Bondy, J. A., Murty, U. S. R., et al. (1976).Graph theory with applications, volume 290.Macmillan London.

Chartrand, G., Johns, G. L., McKeon, K. A., and Zhang, P. (2008). Rainbow connectionin graphs.Mathematica Bohemica, 133(1):85–98.

Cowen, L., Goddard, W., and Jesurum, C. E. (1997). Defective coloring revisited.Journalof Graph Theory, 24(3):205–219.

Hamberger, K., Houseman, M., Daillant, I., White, D. R., and Barry, L. (2004). Matri-monial ring structures.Math ́ematiques et sciences humaines. Mathematics and socialsciences, 168:83–119.

Poz, J. d. and Silva, M. F. d. (2009). Maqpar: a homemade tool for the study of kinshipnetworks.Vibrant, 6(2):29–51.
Publicado
18/07/2021
FRANCO, Álvaro J. P.; VENDRAMIN, Marcelo E.. Super-colored paths in digraphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 6. , 2021, Evento Online. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2021 . p. 94-97. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2021.16389.