Defesa de Proposta de Tese de Doutorado de Arnaldo Cesar Almeida Oliveira, em 11/03/2024, às 10h, na sala 310 do Instituto de Computação
O Problema da H-Partição e suas Relações com Isomorfismo de Grafos e Decomposição Modular
Resumo:
Nesta proposta de tese é considerado um problema de particionamento dos vértices de grafos em subconjuntos não-vazios disjuntos de vértices em que os elementos de cada parte reservam as mesmas relações de adjacência com os elementos das outras partes, dizemos que um grafo G admite uma H-partição se existe uma partição P dos vértices de G tal que o grafo quociente G\P é isomorfo ao grafo H. Problemas de particionamento de grafos tem vários aplicações importantes como alocação de recursos, otimização de redes de computadores, design de circuitos integrados, entre outros. O problema da H-partição mostra-se um problema, a priori, GI-difícil o que nos induz a explorar classes de grafos em que o problema pode ser resolvido em tempo polinomial. Então neste trabalho foi desenvolvido um algoritmo que resolve o problema em tempo exponencial e foi demonstrado alguns casos de classes notáveis de grafos em que o problema pode ser resolvido em tempo polinomial como no caso dos grafos caminho, ciclo, árvores e cografos. Ao avançar nossa compreensão deste problema de particionamento espera-se delinear limites da tratabilidade do problema para diferentes classes de grafos e de um modo geral, caso possível.
Abstract:
In this thesis proposal, we consider a vertex partitioning problem in graphs, where the vertices are divided into disjoint subsets in such a way that the vertices within each subset maintain the same adjacency relationships with vertices in other subsets. We say that a graph G admits an H-partition if there exists a partition P of the vertices of G such that the resulting quotient graph G\P is isomorphic to the graph H. Graph partitioning problems have several important applications such as resource allocation, optimization of computer networks, integrated circuit design, among others. The H-partition problem proves to be, a priori, GI-hard, which motivates us to explore classes of graphs where the problem can be solved in polynomial time. Therefore, in this work, an algorithm was developed that solves the problem in exponential time, and it was demonstrated that for some notable classes of graphs, the problem can indeed be solved in polynomial time, as in the case of path graphs, cycle graphs, trees, and cographs. By advancing our understanding of this partitioning problem, we aim to delineate the tractability boundaries of the problem for different classes of graphs and, if possible, in a general manner.
Banca examinadora:
Prof. Uéverton dos Santos Souza, UFF – Presidente
Prof. Fábio Protti, UFF
Prof. Luis Antonio Brasil Kowada, UFF
Prof. Luerbio Faria, UERJ