Near-Bipartiteness, Connected Near-Bipartiteness, Independent Feedback Vertex Set and Acyclic Vertex Cover on Graphs Having Small Dominating Sets

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 \(\mathcal {S}\) and \(\mathcal {F}\) such that \(\mathcal {S}\) is a stable set and \(\mathcal {F}\) induces a forest. Alternatively, Near-Bipartiteness can be seen as the problem of determining whether G admits an independent feedback vertex set \(\mathcal {S}\) or an acyclic vertex cover \(\mathcal {F}\) . Since such a problem is \(\textsf {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 \(\textsf {NP}\) -complete. In addition, we show that Independent Feedback Vertex Set, the problem of finding a near-bipartition ( \(\mathcal {S},\mathcal {F}\) ) minimizing \(|\mathcal {S}|\) , and Acyclic Vertex Cover, the problem of finding a near-bipartition ( \(\mathcal {S},\mathcal {F}\) ) minimizing \(|\mathcal {F}|\) , are both \(\textsf {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(n^2\cdot m)\) -time algorithm to solved Near-Bipartiteness on \(P_5\) -free graphs, improving the current \(O(n^{16})\) -time state of the art due to Bonamy, Dabrowski, Feghali, Johnson, and Paulusma [Algorithmica, 2019].