9.4.2. Feedback Vertex Set for Arbitrary Weight Functions

By Lemma 9.10, a \(2\)-approximation of an optimal feedback vertex set can be computed in polynomial time provided that the weight function is cyclomatic. In this section, we show how to apply layering to decompose any arbitrary weight function into a sum of cyclomatic weight functions and then use this decomposition to obtain a \(2\)-approximation of an optimal feedback vertex set for arbitrary weight functions. This proves the following theorem:

Theorem 9.13: There exists a polynomial-time algorithm that computes a feedback vertex set of weight at most \(2 \cdot \textrm{OPT}\).

Similar to the layering algorithm for the set cover problem, our feedback vertex set algorithm is recursive:

If \(G\) is a forest, then \(F = \emptyset\) is clearly an optimal feedback vertex set, so we return it.

If \(G\) is not a forest, then Corollary 9.7 provides us with the means to compute \(\delta_G(v)\) efficiently for every vertex \(v \in G\). We split \(w\) into two weight functions \(w^1\) and \(w^2\) such that \(w^1\) is cyclomatic and \(w^2\) is non-negative: \(w_v = w^1_v + w^2_v\), \(w^1_v = \alpha \cdot \delta_G(v)\) for some \(\alpha > 0\), and \(w^2_v \ge 0\) for all \(v \in G\). The choice of \(\alpha\) that ensures that \(w^2_v \ge 0\) for all \(v \in G\) and that \(w^2_v = 0\) for at least one vertex \(v \in G\) is

\[\alpha = \min_{v \in V} \frac{w_v}{\delta_G(v)}.\]

Now let \(V' \subseteq V(G)\) be the subset of vertices \(v\) with strictly positive weight \(w^2_v\): \(V' = \bigl\{v \in G \mid w^2_v > 0\bigr\}\). Since there is at least one vertex \(v \in G\) with \(w^2_v = 0\), \(V'\) is a proper subset of \(V(G)\). We recursively find a feedback vertex set \(F'\) of \(G' = G[V']\) with respect to the weight function \(w^2\). Then we find a minimal feedback vertex set \(F \supseteq F'\) of \(G\). This is the feedback vertex set we return.

You should immediately be wondering whether there always exists a minimal feedback vertex set \(F \supseteq F'\). By the following lemma, this is the case, so the algorithm is well-defined:

Lemma 9.14: There exists a minimal feedback vertex set \(F \supseteq F'\) of \(G\). Such a set \(F\) can be found in polynomial time.

Proof: Since \(F'\) is a feedback vertex set of \(G'\), every cycle in \(G\) that does not include any vertex in \(F'\) includes at least one vertex in \(V(G) \setminus V'\). Thus, \(F'' = F' \cup (V(G) \setminus V')\) is a feedback vertex set of \(G\). We find a minimal feedback vertex set \(F \subseteq F''\) using the algorithm from Exercise 9.2. The resulting set \(F\) is clearly a minimal feedback vertex set of \(G\) and its construction takes polynomial time.

It remains to prove that \(F' \subseteq F\). Since we found \(F'\) by invoking our algorithm recursively on \(G'\), \(F'\) is a minimal feedback vertex set of \(G'\). Thus, there exists a cycle \(C_v\) in \(G'\) for every vertex \(v \in F'\) such that \(v\) is the only vertex in \(F'\) that belongs to \(C_v\). Since all vertices in \(C_v\) are in \(V'\), \(v\) is thus also the only vertex in \(F' \cup (V(G) \setminus V')\) contained in \(C_v\). Therefore, any subset of \(F' \cup (V(G) \setminus V')\) that does not include \(v\) is not a feedback vertex set of \(G\). Since \(F\) is a feedback vertex set of \(G\), this shows that \(F' \subseteq F\). ▨

By Lemma 9.14, the construction of \(F\) from \(F'\) takes polynomial time. If \(n = |V(G)|\) and \(T(n)\) is the running time of the algorithm on an \(n\)-vertex graph, then \(F'\) can be found in at most \(T(n-1)\) time because \(V'\) is a proper subset of \(V(G)\). Thus, \(T(n) \le T(n-1) + O\bigl(n^c\bigr) = O\bigl(n^{c+1}\bigr)\), that is, the algorithm finds a feedback vertex set \(F\) in polynomial time. The following lemma shows that \(F\) is a \(2\)-approximation of an optimal feedback vertex set of \(G\). This proves Theorem 9.13.

Lemma 9.15: If \(F^*\) is an optimal feedback vertex set of \(G\), then \(w(F) \le 2 \cdot w(F^*) = 2 \cdot \textrm{OPT}\).

Proof: By induction on \(|V(G)|\).

Since different recursive calls have different subgraphs of \(G\) and weight functions \(w\) as arguments, we use \(\textrm{OPT}(G, w)\) to refer to the weight of an optimal feedback vertex set of \(G\) with respect to the weight function \(w\).

If \(|V(G)| = \emptyset\), then \(G = \emptyset\). It is thus a forest and we return the optimal feedback vertex set \(F = \emptyset\).

If \(|V(G)| > 0\) and \(G\) is a forest, then once again, the empty set we return is clearly an optimal feedback vertex set of \(G\). So assume that \(|V(G)| > 0\) and that \(G\) is not a forest. The set \(F\) returned by the algorithm is clearly a feedback vertex set of \(G\). Its cost is \(w(F) = w^1(F) + w^2(F)\).

Since \(w^1\) is a cyclomatic weight function and \(F\) is a minimal feedback vertex set of \(G\), Lemma 9.10 shows that \(w^1(F) \le 2 \cdot \textrm{OPT}\bigl(G, w^1\bigr)\). Since \(F^*\) is a feedback vertex set of \(G\), we have \(w^1(F^*) \ge \textrm{OPT}\bigl(G, w^1\bigr)\), so \(w^1(F) \le 2 w^1(F^*)\).

Since \(V' \subset V(G)\), and \(G' = G[V']\), the inductive hypothesis shows that \(w^2(F') \le 2 \cdot \textrm{OPT}\bigl(G', w^2\bigr)\). Since the restriction of any feedback vertex set of \(G\) to \(G'\) is also a feedback vertex set of \(G'\), we have \(\textrm{OPT}\bigl(G', w^2\bigr) \le \textrm{OPT}\bigl(G, w^2\bigr)\). Once again, since \(F^*\) is a feedback vertex set of \(G\), we have \(w^2(F^*) \ge \textrm{OPT}\bigl(G, w^2\bigr)\), so \(w^2(F') \le 2 w^2(F^*)\). Any vertex \(v \in F \setminus F'\) belongs to \(V(G) \setminus V'\) and thus has weight \(w^2_v = 0\). Thus, \(w^2(F) = w^2(F') \le 2 w^2(F^*)\).

This shows that \(w(F) = w^1(F) + w^2(F) \le 2w^1(F^*) + 2w^2(F^*) = 2w(F^*) \le 2 \cdot \textrm{OPT}(G, w)\). ▨