17.2. Feedback Vertex Set

Recall the feedback vertex set (FVS) problem: Given a graph \(G\), our goal is to remove as few vertices as possible (and their incident edges) from \(G\) so that the remaining graph is acyclic. Since we consider the undirected FVS problem here, this means that the graph we obtain by removing these vertices must be a forest.

To compute a minimum feedback vertex set \(S\), we solve its dual problem:

Maximum Induced Forest Problem: Given a graph \(G\), find a subset of its vertices \(F\) of maximum size such that \(G[F]\) is a forest.

By definition, if \(S\) is a feedback vertex set, then \(G[V \setminus S]\) is a forest and minimizing \(|S|\) maximizes \(|V \setminus S|\).

We solve a generalization of the maximum induced forest problem: Given a subset \(F \subseteq V\) such that \(G[F]\) is a forest, let \(\mathcal{M}_G(F)\) be the set of all maximum supersets \(F^* \supseteq F\) such that \(G[F^*]\) is a forest. Since \(G[F]\) is a forest, \(\mathcal{M}_G(F) \ne \emptyset\). Our goal is to find an element of \(\mathcal{M}_G(F)\). Finding a maximum induced forest of \(G\) is the same as finding an element in \(\mathcal{M}_G(\emptyset)\).