Defesa de Dissertação de Mestrado de Maria Luíza López da Cruz, em 21/08/23, às 14:00h, na sala 310 do IC e por videoconferência. Link para defesa: https://meet.google.com/rqj-bava-afd
Near-Bipartiteness on Graphs Having Small Dominating Sets
Resumo:
No problema Near-Bipartiteness nos é fornecido um grafo simples G = (V, E) e per- guntado se V(G) pode ser particionado em dois conjuntos S e F de tal forma que S seja um conjunto estável e F induza uma floresta. Alternativamente, Near-Bipartiteness pode ser visto como o problema de determinar se G admite um conjunto de vértices de retroalimentação independente (independent feedback vertex set) S ou uma cobertura por vértices acíclica (acyclic vertex cover) F. Uma vez que tal problema é NP-completo até mesmo para grafos com diâmetro três, estudamos primeiramente a propriedade de ser quase-bipartido em grafos que possuem uma aresta dominante, uma subclasse natural de grafos com diâmetro três. No que diz respeito a grafos que possuem uma aresta domi- nante, apresentamos um algoritmo de tempo polinomial para Near-Bipartiteness e provamos que Connected Near-Bipartiteness, a variante em que a floresta deve ser conexa, é NP-completo. Além disso, mostramos que Independent Feedback Vertex Set, o problema de encontrar uma quase-bipartição (S, F) minimizando |S|, e Acyclic Vertex Cover, o problema de encontrar uma quase-bipartição (S, F) minimizando |F|, são ambos NP-difíceis quando restritos a essa classe de grafos. Estendendo nossa abor- dagem de tempo polinomial para lidar com Near-Bipartiteness em grafos que possuem conjuntos dominantes de tamanhos limitados, obtemos um algoritmo de tempo O(n2 · m) para resolver Near-Bipartiteness em grafos livres de P5, melhorando o atual estado da arte de tempo O(n16).
Abstract:
In the Near-Bipartiteness problem, we are given a simple graph G = (V, E) and asked whether V(G) can be partitioned into two sets S and F such that S is a stable set and F induces a forest. Alternatively, Near-Bipartiteness can be seen as the problem of determining whether G admits an independent feedback vertex set S or an acyclic vertex cover F. Since such a problem is NP-complete even for graphs with diameter three, we first study the property of being near-bipartite on graphs having a dominating edge, a natural subclass of diameter-three graphs. Concerning graphs having a dominating edge, we present a polynomial-time algorithm for Near-Bipartiteness and prove that Connected Near-Bipartiteness, the variant where the forest must be connected, is NP-complete. In addition, we show that Independent Feedback Vertex Set, the problem of finding a near-bipartition (S, F) minimizing |S|, and Acyclic Vertex Cover, the problem of finding a near-bipartition (S, F) minimizing |F|, are both NP-hard when restricted to such a class of graphs. Extending our polynomial-time approach to deal with Near-Bipartiteness on graphs having bounded dominating sets, we obtain a O(n2 · m) time algorithm to solved Near-Bipartiteness on P5-free graphs, improving the current O(n16)-time state of the art.
Banca examinadora:
Prof. Uéverton dos Santos Souza, UFF – Presidente
Prof. Fábio Protti, UFF
Prof. Raquel de Souza Francisco Bravo, UFF
Prof. Rodolfo Alves de Oliveira, UFF
Prof. Erika Morais Martins Coelho, UFG