\(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 procedure that generates an upper bound on the decycling number of arbitrary bipartite graphs. Tests on challenging families of graphs show that the proposed algorithm improves many best-known upper bounds, thus closing or narrowing the gap to the best-known lower bounds.
Paru en juillet 2020 , 20 pages