Near-bipartiteness 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 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).