Near-Bipartiteness e Problemas Relacionados em Classes Restritas de Grafos
Resumo:
O problema Near-Bipartiteness consiste em determinar se o conjunto de vértices de um grafo pode ser particionado em um conjunto independente S e uma floresta F. Esse problema e suas variantes ocupam posição de destaque na Teoria dos Grafos e na Complexidade Computacional, uma vez que modelam diferentes problemas de particionamento de vértices e apresentam comportamento computacional distinto em classes restritas de grafos. Esta tese investiga a complexidade computacional de variantes do problema Near-Bipartiteness em classes de grafos caracterizadas por propriedades estruturais específicas, com ênfase em grafos bipartidos. Para o desenvolvimento deste trabalho, empregam-se reduções polinomiais a partir de problemas clássicos de satisfatibilidade booleana e exploram-se as propriedades estruturais da classe de grafos investigada. Como principais contribuições, demonstra-se que o problema Connected Near-Bipartiteness permanece NP-completo mesmo quando restrito à classe dos grafos bipartidos. Além disso, estabelece-se a NP-dificuldade dos problemas Independent Feedback Vertex Set e Acyclic Vertex Cover nessa mesma classe de grafos. Por fim, são apresentadas duas linhas de pesquisa que compõem as próximas etapas deste doutorado. Os resultados obtidos até o momento contribuem para uma melhor compreensão da influência das propriedades estruturais dos grafos na complexidade computacional de problemas de particionamento de vértices, bem como para a delimitação entre casos polinomiais e NP-difíceis.
Abstract:
The Near-Bipartiteness problem consists of determining whether the vertex set of a graph can be partitioned into an independent set S and a forest F. This problem and its variants play an important role in Graph Theory and Computational Complexity because their complexity depends on the graph class we work with. This thesis studies the computational complexity of variants of the Near-Bipartiteness problem on graph classes with specific structural properties, with a focus on bipartite graphs. The results are obtained using polynomial reductions from classical boolean satisfiability problems and the structural properties of the graph class considered. The main contribution is the proof that the Connected Near-Bipartiteness problem remains NP-complete even when restricted to bipartite graphs. In addition, the Independent Feedback Vertex Set and Acyclic Vertex Cover problems are shown to be NP-hard on bipartite graphs. Finally, two research directions for the next stages of this research are presented. The results obtained so far contribute to a better understanding of how graph structural properties affect the computational complexity of vertex partitioning problems and help identify the boundary between polynomial-time solvable and NP-hard cases.
Banca examinadora:
Prof. Uéverton dos Santos Souza, UFF – Presidente
Prof. Luís Felipe Ignácio Cunha, UFF
Profa. Raquel de Souza Francisco Bravo, UFF
Profa. Diana Sasaki Nobrega, UERJ