Near-Bipartiteness on graphs having small dominating sets: Structural characterization and algorithms - Cruz, Maria Luíza López da; Souza, Uéverton S.; Bravo, Raquel (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2024: Anais do XXXVII Concurso de Teses e Dissertações, 2024)
The Near-Bipartiteness problem asks for a partition of the vertex set of a graph G = (V,E) into two subsets S and F, where S forms an independent set and F induces a forest. Despite its NP-completeness, even for graphs with a diameter three, we explore this problem on graphs with a dominating edge or small dominating sets. Our work presents a polynomial-time algorithm for Near-Bipartiteness on graphs with a dominating edge, a particular case of graphs with diameter three. In addition, we prove that Connected Near-Bipartiteness, the variant where the forest must be connected, is NP-complete on the same class. Moreover, we also establish the NP-hardness of Independent Feedback Vertex Set and Acyclic Vertex Cover on this class of graphs. In addition, by extending our approach to graphs with bounded dominating sets, we achieve a huge improvement, obtaining an O(n 2 · m)-time algorithm for Near-Bipartiteness on P 5 -free graphs, improving upon the current state-of-the-art time complexity of O(n 16 ).