Aspectos algorítmicos e estruturais de problemas de cobertura e empacotamento em grafos

Resumo

Este é um projeto de pesquisa para o estágio de Phablo Fernando Soares Moura (FAPESP Proc. 2016/21250-3), pesquisador pós-doutoral sob supervisão do professor Flávio Keidi Miyazawa no Instituto de Computação da Universidade Estadual de Campinas. Esse estágio, a ser realizado na Charles University em Praga, República Tcheca, é planejado para o período de 1 de agosto de 2018 até 31 de julho de 2019 (12 meses). Durante esse período, Phablo será supervisionado pelo professor Zdenek Dvorak. O foco deste projeto de pesquisa é o estudo de problemas de cobertura e empacotamento em grafos e digrafos. Estamos particularmente interessados em estudar o problema de cobertura por caminhos, o problema das Quatro Cores e problemas relativos a conjectura de Mader sobre subdivisão de digrafos. No primeiro problema, queremos cobrir o conjunto de vértices de um grafo usando uma quantidade mínima de caminhos disjuntos nos vértices. No segundo, estudamos a reducibilidade de configurações no contexto do Teorema das Quatro Cores. Finalmente, no contexto da conjectura de Mader, temos como objetivo encontrar condições suficientes para que um digrafo contenha alguma subdivisão de um dado digrafo acíclico.