25/08/2021 às 15h29min - Atualizada em 25/08/2021 às 15h29min
Estudo realizado em PG avança em problema matemático sem solução há 35 anos
Trabalho foi realizado durante dissertação de mestrado em Ciência da Computação
Da assessoria
Foto: Divulgação
Um trabalho da área da Teoria da Computação, realizado durante a dissertação de mestrado em Ciência da Computação da Universidade Tecnológica Federal do Paraná (UTFPR) - 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.
Foto: Divulgação 
