Decycling bipartite graphs - Hertz, Alain (Journal of Graph Algorithms and Applications, 2021)
Let G=(V,E) be a graph and let SV be a subset of its vertices. If the subgraph of G induced by VS 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.