Near-bipartiteness on graphs having small dominating sets

Maria Luiza L. da Cruz (), Raquel Bravo (), Rodolfo A. Oliveira () and Ueverton S. Souza ()
Additional contact information
Maria Luiza L. da Cruz: Fluminense Federal University
Raquel Bravo: Fluminense Federal University
Rodolfo A. Oliveira: Fluminense Federal University
Ueverton S. Souza: Fluminense Federal University

Journal of Combinatorial Optimization, 2025, vol. 50, issue 5, No 1, 17 pages

Abstract: Abstract 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).

Keywords: Near-bipartite; Independent feedback vertex set; Acyclic vertex cover; Dominating set (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01375-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:50:y:2025:i:5:d:10.1007_s10878-025-01375-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01375-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().