Um trabalho da área da Teoria da Computação realizado durante a dissertação de mestrado em Ciência da Computação do Campus Ponta Grossa promete avançar em um problema matemático sem solução há 35 anos. Os estudos são do mestrando Luis Gustavo da Soledade Gonzaga, com a orientação das professoras Sheila Almeida (Campus Ponta Grossa) e Cândida Nunes Silva (UFSCar).

Em 1985, o pesquisador David Johnson lançou uma questão sobre a dificuldade de se resolver um problema conhecido como Problema da Coloração de Arestas. Ele escreveu que era possivelmente fácil descobrir qual a complexidade computacional do Problema da Coloração de Arestas quando restrito a três conjuntos específicos de entradas, conhecidos como grafos de comparabilidade, grafos de intervalos, e grafos split. Porém, em 1991, descobriu-se que, se a entrada do Problema da Coloração de Arestas é um grafo de comparabilidade, então ele seria computacionalmente muito difícil. Em razão disso, o Clay Mathematics Institute lançou o desafio de que quem conseguisse descobrir uma maneira eficiente de resolver o problema, ganharia um prêmio de US$ 1 milhão.

Ou seja, até o momento apenas a complexidade do problema para grafo de comparabilidade foi descoberta. Para os outros dois casos, grafos de intervalos e grafos split, a dificuldade computacional de se resolver o Problema da Coloração de Arestas também permanece sem resposta há 35 anos, após a publicação de Johnson, e os últimos avanços foram publicados há mais de uma década.

Luis Gustavo Gonzaga descreveu, em sua dissertação, que se a entrada para o problema for um grafo que pertence à interseção das classes intervalos e split, então há sim uma solução computacionalmente eficiente, respondendo parcialmente à questão colocada por Johnson em 1985.

Além disso, em outras pesquisas em conjunto com o aluno de doutorado do Instituto de Computação da UNICAMP, Jadder Sousa Cruz, eles também demonstraram que se a entrada for um grafo pertencente à interseção das classes de comparabilidade (do prêmio de US$ 1 milhão) e split, também há uma solução computacionalmente eficiente.
Com esses estudos, os pesquisadores já receberam o prêmio de terceiro melhor artigo no Simpósio LAGOS 2021 (Latin and American Graphs and Optimization Symposium).

Coloração de arestas
A coloração de arestas de um grafo é a atribuição de “cores” para as arestas dele, sem que haja duas arestas adjacentes com a mesma cor. O Problema da coloração de arestas pergunta se é possível colorir um dado grafo usando no máximo n cores. O número mínimo exigido de cores para um grafo é chamado de índice cromático.

da Comunicação UTFPR