Groupe d’études et de recherche en analyse des décisions

G-2020-43

Decycling bipartite graphs

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 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.

, 20 pages