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 study the property of being near-bipartite on graphs having a bounded dominating set. In particular, we consider the case where the input graphs have dominating edges, since it is a natural subclass of diameter-three graphs. Concerning graphs having a dominating edge, we prove that Connected Near-Bipartiteness, the variant where the forest \({\mathcal {F}}\) 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. On the other hand, we show that given a graph G and a dominating set D of G with size k, one can determine whether G is near-bipartite in \({\mathcal {O}}(2^k\cdot n^{2k})\) time, which implies that Near-Bipartiteness can be solved in polynomial time whenever the input graph G has a dominating set with size bounded by a constant. As a byproduct of our algorithm, we can solve Near-Bipartiteness on \(P_5\) -free graphs in \({\mathcal {O}}(n^2\cdot m)\) -time, improving the current \({\mathcal {O}}(n^{16})\) -time state of the art due to Bonamy et al. (Algorithmica 81:1342–1369, 2019).
