Problema da Coloração de Arestas: um problema de 1 milhão de dólares e alguns avanços dos últimos 40 anos
Na terça-feira, 31 de maio, às 19:30, o fórum traz a palestra “Problema da Coloração de Arestas: um problema de 1 milhão de dólares e alguns avanços dos últimos 40 anos“, com a Profa. Dra. Sheila Morais de Almeida (UTFPR-PG)
Transmissão: https://youtu.be/gzpGpQ8ONSk
Ative o lembrete e compartilhe!
Resumo: Uma coloração de arestas de um grafo é uma atribuição de cores para as arestas do grafo de maneira que arestas incidentes no mesmo vértice tenham cores diferentes. O Problema da Coloração de Arestas é determinar o menor número de cores para uma coloração de aresta de um grafo. Este problema surgiu no final do século XIX, quando Alfred Kempe tentava encontrar uma prova para um outro problema famoso, conhecido como Problema das Quatro Cores. Em 1981, foi provado que, dado um grafo G e um número inteiro k, decidir se G tem uma coloração de arestas com k cores é um Problema NP-completo. No ano 2000, o Clay Mathematics Institute apresentou uma lista com os sete problemas matemáticos que considerou os mais desafiadores deste milênio. Nesta lista, está o problema P vs NP, que consiste em responder se existe um algoritmo polinomial para resolver algum dos problemas NP-completos. O Clay Mathematics Institute oferece um prêmio de 1 milhão de dólares para o primeiro que apresentar solução correta para cada um dos sete problemas. Desta lista, apenas um problema foi resolvido, a Conjectura de Poincaré. Em 1985, David Johnson publicou a 6a edição de sua coluna trimestral “The NP-completeness column: an ongoing guide”. Nessa edição, ele apresentou problemas conhecidos da Teoria dos Grafos e discutiu a complexidade computacional desses problemas quando restritos a classes de grafos relevantes do ponto de vista algorítmico. Na lista há diversos problemas que são NP-completos, mesmo quando restritos a classes de grafos bastante conhecidas. Dentre os onze problemas considerados, o Problema da Coloração de Arestas destacou-se por ser aquele cuja complexidade computacional era desconhecida para o maior número de classes de grafos (vinte e duas das trinta classes apresentadas). Trinta e seis anos depois, a complexidade computacional do Problema da Coloração de Arestas permanece em aberto para quatorze destas classes e o provou-se que este problema é NP-completo mesmo quando restrito a quatro das classes de grafos listadas. Dentre as classes de grafos para as quais a complexidade computacional do Problema da Coloração de Arestas permanece desconhecida, estão os grafos split e os grafos de intervalos. Neste encontro vamos falar sobre os principais avanços no conhecimento do Problema da Coloração de Arestas quando restrito a grafos split e grafos de intervalos.
Bio: Sheila é professora Adjunta da Universidade Tecnológica Federal do Paraná (UTFPR), Câmpus Ponta Grossa, desde 2012. Bacharel (2002), Mestre (2005) e Doutora (2012) em Ciência da Computação pelo Instituto de Computação da UNICAMP. Participou dos processos de abertura e reconhecimento dos cursos de graduação em Ciência da Computação e Sistemas de Informação da Universidade Federal do Mato Grosso do Sul – Ponta Porã, dos quais também foi coordenadora. Participou do processo de criação e abertura do curso de Pós-Graduação em Ciência da Computação da Universidade Tecnológica Federal do Paraná – Ponta Grossa, do qual também foi coordenadora. É revisora de artigos submetidos a conferências e periódicos nacionais e internacionais. Participa dos comitês organizadores do Workshop de Pesquisa em Computação dos Campos Gerais e do Latin American Workshop on Cliques in Graphs (2020 – 2022). Atua como parecerista ad hoc na avaliação de projetos de pesquisa submetidos à agências estaduais. Desenvolve pesquisas em Teoria dos Grafos há 20 anos, atuando principalmente em problemas de coloração, caracterização e reconhecimento de subclasses de grafos perfeitos.
