Teoria de Grafos e Complexidade Computacional: Otimização Combinatória, Algoritmos, Classes, e Teoria do Aprendizado de Máquina

(Graph theory and computational complexity: Combinatorial optimization, algorithms, classes and machine learning theory)

Os grafos são ferramentas para modelar numerosos problemas da vida real. Para muitos desses problemas, se desconhecem soluções computacionais que possam ser executadas em tempo polinomial. Muitas vezes, a solução polinomial aparece ao restringir o problema a classes de grafos. É fundamental conhecer propriedades e estruturas dessas classes de grafos. Temos como objetivo principal estudar propriedades de diferentes classes de grafos e problemas computacionalmente difíceis restritos a estas classes. Pesquisas já foram iniciadas na maioria dos problemas mencionados com resultados alentadores. Também, os problemas mencionados são clássicos na literatura ou se relacionam com problemas já estudados, o que nos proporciona uma ampla base bibliográfica para direcionar nossa pesquisa. Muitos problemas em grafos se relacionam com importantes classes de Complexidade Computacional, que merecem atenção por si só. É por isso que neste projeto, pretendemos também investigar classes de Complexidade Computacional, especialmente as que têm relação com Computação Quântica, Álgebra de Grupos, e provas interativas, como ferramenta para melhor entendermos a estrutura combinatória dos problemas de grafos estudados. No contexto de problemas modelados com grafos a partir de fenômenos advindos de contextos reais, como por exemplo, redes sociais e econômicas, a incerteza torna-se uma variável inerente em tais problemas. Sendo assim, este projeto também investiga aspectos de análise probabilística em grafos. Em particular, resultados recentes da literatura mostram que algoritmos projetados a partir do estudo aprofundado da teoria de aprendizagem máquina - como, por exemplo, na computação de medidas de centralidade em grafos - apresentam não só resultados eficientes e de interesse prático, como também nos permitem obter conclusões sobre a estrutura combinatória de importantes problemas em grafos. Sendo assim, o estudo desta área também será investigado neste projeto.