Near-Bipartiteness Problem on Graphs with Small Dominant Sets

The problem of partitioning the set of vertices of a graph into an independent set and a forest, known as the Near-Bipartiteness problem, is NP-complete even in graphs with diameter three. We study the behavior of this problem and its variants in graphs with a dominant edge or small dominant sets. For the first class of graphs, we present: (i) a polynomial algorithm for Near-Bipartiteness; (ii) the NP-completeness of the Connected Near-Bipartiteness; (iii) the NP-hard of Independent Feedback Vertex Set and Acyclic Vertex Cover, which are natural optimization versions for Near-Bipartiteness. By expanding our approach to graphs with bounded dominant sets, we obtain a polynomial-time algorithm whenever the input graph has a dominated set of size bounded by a constant. As a by-product, we significantly improved the state-of-the-art of Near-Bipartiteness in P_5-free graphs, achieving an O(n^2 .m) time algorithm surpassing the current O(n^16)