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

# Decycling bipartite graphs

## Alain Hertz

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