Decycling bipartite graphs
Vol. 25, no. 1, pp. 461-480, 2021. Regular paper.
Abstract Let $G=(V,E)$ be a graph and let $S\subseteq V$ be a subset of its vertices. If the subgraph of $G$ induced by $V\setminus S$ is acyclic, then $S$ is said to be a decycling set of $G$. The size of a smallest decycling set of $G$ is called the decycling number of $G$. Determining the decycling number of a graph $G$ is NP-hard, even if $G$ is bipartite. We describe a tabu search procedure that generates decycling sets of small size for arbitrary bipartite graphs. Tests on challenging families of graphs show that the proposed algorithm improves many best-known solutions, thus closing or narrowing the gap to the best-known lower bounds.

 This work is licensed under the terms of the CC-BY license.
Submitted: September 2020.
Reviewed: May 2021.
Revised: May 2021.
Accepted: August 2021.
Final: August 2021.
Published: September 2021.
Communicated by Anna Lubiw
article (PDF)