Algoritmos de supercoloração para grafos dirigidos acíclicos com 4 cores e aplicações em redes de parentesco

Abstract

Esse trabalho explora o problema da supercoloração, que consiste em, para um digrafo D com n vértices, m arcos e cada vértice colorido com uma cor de {1,2,...,k}, encontrar, para cada vértice v, o valor super(v), isto é, o número máximo de cores distintas de um caminho partindo de v. O problema tem aplicações no estudo das rela ções matrimoniais na antropologia, permitindo, por exemplo, a análise da transmissão de características e propriedades de ancestrais para descendentes, observação da movimentação no espaço ao longo de uma genealogia e a visualização das relações entre clãs ou diferentes comunidades. Foi desenvolvido um algoritmo que o resolve para grafos direcionados acíclicos (DAGs) com k = 4 cores e complexidade assintóti ca O(|V|^3), aprimorando algoritmos ingênuos Ω(|V|^k) para k-cores e fornecendo uma alternativa para algoritmos parametrizados com tempo O(2^k k^2 m), desenvolvidos em trabalhos semelhantes. É possível aplicá-lo em grafos genealógicos (grafos mistos com grau de entrada igual a dois, exceto para os vértices fonte), demonstrando sua aplicabilidade no campo da antropologia, inclusive para o problema da enumeração de anéis cromáticos. O algoritmo proposto é comparado com outros algoritmos que resol vem o mesmo problema por meio de experimentos conduzidos em grafos sintéticos e redes genealógicas. Resultados mostram que sua menor complexidade nos permite aplicações em redes genealógicas maiores e mais densas.