9.4. Feedback Vertex Set via Layering*

As a second application of the layering technique, we discuss the feedback vertex set problem. This problem comes in two variants:

Undirected Feedback Vertex Set Problem: Given an undirected graph \(G = (V, E)\) and a weight function \(w : V \rightarrow \mathbb{R}^+\), choose a subset \(F \subseteq V\) of vertices such that the subgraph \(G[V \setminus F]\) is a forest. In other words, \(G[V \setminus F]\) contains no undirected cycles. See Figure 9.11.

For a subset of vertices \(W \subseteq V\), we use \(G[W]\) to denote the subgraph of \(\boldsymbol{G}\) induced by \(\boldsymbol{W}\), which is defined as \(G[W] = (W, E')\) where \(E' = \{(x, y) \in E \mid x, y \in W\}\).

Figure 9.11: Coming soon!

Directed Feedback Vertex Set Problem: Given a directed graph \(G = (V, E)\) and a weight function \(w : V \rightarrow \mathbb{R}^+\), choose a subset \(F \subseteq V\) of vertices such that the subgraph \(G[V \setminus F]\) is a directed acyclic graph (DAG). In other words, \(G[V \setminus F]\) contains no directed cycles. See Figure 9.12.

Figure 9.12: Coming soon!

In this section, we discuss the undirected feedback vertex set problem. In order to apply layering to this problem, we first need to identify a type of weight function that makes finding a feedback vertex set of low weight easy, similar to degree-weighted weight functions for the set cover problem. These weight functions are called cyclomatic weight functions because they reflect the number of cycles in \(G\) that a vertex is part of. Similarly to the set cover problem, we then decompose an arbitrary weight function into cyclomatic weight functions to obtain an approximation algorithm for arbitrary weight functions.