Algoritmos Exatos para Problemas de Cobertura de Arestas com Caminhos

• Processo: 22/15408-4
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de março de 2023
• Data de Término da vigência: 30 de novembro de 2023
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Rafael Crivellari Saliba Schouery
• Beneficiário: Bernardo Panka Archegas
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Vinculado ao auxílio: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
• Assunto(s): Grafos Programação linear inteira
• Palavra(s)-Chave do Pesquisador: Algoritmos Exatos | grafos | programação linear inteira | Algoritmos Exatos

Resumo

O Minimum Path-Collection Exact Cover (PCEC) é um problema em que, dado um grafo dirigido G e um conjunto de caminhos de G, é necessário achar o subconjunto de caminhos de menor cardinalidade tal que toda aresta do grafo seja coberta exatamente uma vez. Já o Minimum k-Path Splitting Exact Cover (k-PSEC) é uma variante do PCEC em que existem restrições sobre os caminhos escolhidos. Estes problemas pertencem à classe NP-difícil, ou seja, não existem algoritmos que os resolvam de forma exata em tempo polinomial, a menos que P = NP. No entanto, ainda é possível buscar por algoritmos exatos para problemas NP-difíceis que sejam eficientes na prática, tendo ocorrido grandes avanços nesse aspecto na literatura nas últimas décadas. Neste projeto, desenvolveremos algoritmos exatos para o PCEC e k-PSEC, usando técnicas como o Branch and Bound e Programação Dinâmica. Ademais, o projeto também visa introduzir o candidato ao ramo da pesquisa científica, além de complementar a sua graduação.