9.4.1.3. A Minimal Feedback Vertex Set is a 2-Approximation

To prove that a minimal feedback vertex set is a \(2\)-approximation of an optimal feedback vertex set, we need to understand the structure of the cycle space of a graph and, correspondingly, the properties of the cyclomatic number of a graph a little better.

Let \(\gamma(G)\) denote the number of connected components of \(G\). Then the following theorem provides a straightforward method to calculate the cyclomatic number of a graph \(G\):

Theorem 9.6: \(\mathrm{cyc}(G) = |E| - |V| + \gamma(G)\).

Proof: It suffices to prove that the theorem holds if \(G\) is connected, that is, that

\[\mathrm{cyc}(G) = |E| - |V| + 1\]

in this case. If \(G\) is not connected, then

\[\mathrm{CYC}(G) = \mathrm{CYC}(G_1) \times \cdots \times \mathrm{CYC}(G_{\gamma(G)}),\]

where \(G_1 = (V_1, E_1), \ldots, G_{\gamma(G)} = (V_{\gamma(G)}, E_{\gamma(G)})\) are the connected components of \(G\). Thus,

\[\begin{aligned} \mathrm{cyc}(G) &= \dim(\mathrm{CYC}(G))\\ &= \sum_{i=1}^{\gamma(G)} \dim(\mathrm{CYC}(G_i))\\ &= \sum_{i=1}^{\gamma(G)} \mathrm{cyc}(G_i)\\ &= \sum_{i=1}^{\gamma(G)} (|E_i| - |V_i| + 1)\\ &= |E| - |V| + \gamma(G). \end{aligned}\]

Let \(T\) be a spanning tree of \(G\). Every non-tree edge \(e\) (edge of \(G\) that is not in \(T\)) defines a fundamental cycle formed by \(e\) and the path between \(e\)'s endpoints in \(T\). See Figure 9.15.

Figure 9.15: Coming soon!

The characteristic vectors of these fundamental cycles are linearly independent because each fundamental cycle contains a non-tree edge that is not in any other fundamental cycle. Thus, since there are \(|E| - |V| + 1\) fundamental cycles, one per non-tree edge, we have \(\mathrm{cyc}(G) \ge |E| - |V| + 1\).

Every edge \(e \in T\) defines a fundamental cut \(S\), where \(S\) is the vertex set of one of the connected components of \(T - e\). See Figure 9.16.

Figure 9.16: Coming soon!

The characteristic vector \(\chi(S) = (y_1, \ldots, y_m)\) of \(S\) satisfies \(y_i = 1\) if and only if the edge \(e_i\) has exactly one endpoint in \(S\). In other words, \(\chi(S)\) is the characteristic vector of the subset of all edges in \(G\) that cross the cut \(S\).

Again, these vectors span a subspace of \(\textrm{GF}[2]\), which we call the cut space \(\textrm{CUT}(T)\) of \(T\). This space has dimension \(\dim(\textrm{CUT}(T)) \ge |V| - 1\) because the characteristic vectors of all fundamental cuts are linearly independent: Each fundamental cut is crossed by a tree edge that does not cross any other fundamental cut.

Next consider any cycle \(C\) in \(G\) and any (fundamental) cut \(S\) in \(G\). We can view \(C\) as starting at some vertex \(u \in S\), visiting a number of vertices, and eventually returning to \(u\). Every time \(C\) follows an edge that crosses \(S\), it either moves from a vertex \(v \in S\) to a vertex \(w \notin S\) or vice versa. Thus, since \(C\) starts and ends in \(S\), it needs to cross \(S\) an even number of times. This implies that the characteristic vectors \(\chi(C)\) and \(\chi(S)\) satisfy \(\chi(C) \cdot \chi(S) = 0\). Since this is true for every cycle in \(G\) and every fundamental cut of \(T\), this shows that the cycle space of \(G\) and the cut space of \(T\) are orthogonal. Therefore, since both are subspaces of \(\textrm{GF}[2]^m\), we have

\[\begin{aligned} |E| = m &= \dim(\textrm{GF}[2]^m)\\ &\ge \dim(\mathrm{CYC}(G)) + \dim(\textrm{CUT}(T))\\ &\ge \dim(\mathrm{CYC}(G)) + |V| - 1 \end{aligned}\]

and, therefore,

\[\mathrm{cyc}(G) = \dim(\mathrm{CYC}(G)) \le |E| - |V| + 1.\]

Since we already proved that \(\mathrm{cyc}(G) \ge |E| - |V| + 1\), the theorem follows. ▨

Corollary 9.7: If \(G\) is a connected graph, then \(\delta_G(v) = \deg_G(v) - \gamma(G - v)\) for all \(v \in G\).

Proof: Since \(G\) is connected, we have

\[\mathrm{cyc}(G) = |E(G)| - |V(G)| + 1,\]

by Theorem 9.6.

The graph \(G - v\) has \(|E(G)| - \deg_G(v)\) edges, \(|V(G)| - 1\) vertices, and some number \(\gamma(G - v)\) of connected components. Thus,

\[\mathrm{cyc}(G - v) = |E(G)| - \deg_G(v) - |V(G)| + 1 + \gamma(G - v),\]

again by Theorem 9.6.

Thus,

\[\begin{aligned} \delta_G(v) &= \mathrm{cyc}(G) - \mathrm{cyc}(G - v)\\ &= (|E(G)| - |V(G)| + 1) - (|E(G)| - \deg_G(v) - |V(G)| + 1 + \gamma(G - v))\\ &= \deg_G(v) - \gamma(G - v).\ \text{▨} \end{aligned}\]

If \(H \subseteq G\) is a subgraph of \(G\), then it seems intuitively obvious that removing some vertex \(v\) from \(H\) cannot destroy more cycles in \(H\) than the number of cycles in \(G\) destroyed by removing \(v\) from \(G\). After all, every cycle in \(H\) is also a cycle in \(G\). The next lemma essentially shows that \(\delta_G(v)\) is the "right" measure of the number of cycles in \(G\) destroyed by removing the vertex \(v\) from \(G\), in the sense that \(\delta_H(v) \le \delta_G(v)\) for every subgraph \(H \subseteq G\):

Lemma 9.8: Let \(H \subseteq G\) be any subgraph of \(G\). Then \(\delta_H(v) \le \delta_G(v)\) for every vertex \(v \in H\).

Proof: It suffices to prove the claim for the case when \(G\) and \(H\) are connected. Indeed, if the claim holds for connected graphs, \(G_0, \ldots, G_k\) are the connected components of \(G\), \(H_0, \ldots, H_\ell\) are the conneced components of \(H\), and w.l.o.g.\ \(v \in G_0\) and \(v \in H_0\), then

\[\begin{aligned} \delta_H(v) &= \mathrm{cyc}(H) - \mathrm{cyc}(H - v)\\ &= \left[ \mathrm{cyc}(H_0) + \sum_{i=1}^\ell \mathrm{cyc}(H_i) \right] - \left[ \mathrm{cyc}(H_0 - v) + \sum_{i=1}^\ell \mathrm{cyc}(H_i) \right]\\ &= \mathrm{cyc}(H_0) - \mathrm{cyc}(H_0 - v)\\ &= \delta_{H_0}(v)\\ &\le \delta_{G_0}(v)\\ &= \mathrm{cyc}(G_0) - \mathrm{cyc}(G_0 - v)\\ &= \left[ \mathrm{cyc}(G_0) + \sum_{i=1}^k \mathrm{cyc}(G_i) \right] - \left[ \mathrm{cyc}(G_0 - v) + \sum_{i=1}^k \mathrm{cyc}(G_i) \right]\\ &= \mathrm{cyc}(G) - \mathrm{cyc}(G - v)\\ &= \delta_G(v). \end{aligned}\]

So assume that \(G\) and \(H\) are connected and let \(E'\) be the set of edges that are in \(G\) but not in \(H\). We can transform \(H\) into \(G\) by adding these edges one at a time, producing a sequence of graphs \(H = H^{(0)} \subseteq \cdots \subseteq H^{(t)} = G\). Adding an edge also adds its endpoints to the vertex set if they are not already present in the current vertex set. We order the edges so that the edge \(e_i\) that is in \(H^{(i)}\) and not in \(H^{(i-1)}\) has at least one endpoint in \(H^{(i-1)}\). This ensures that each graph \(H^{(i)}\) is connected.

Now it suffices to prove that \(\delta_{H^{(i)}}(v) \ge \delta_{H^{(i-1)}}(v)\) for all \(1 \le i \le t\). This immediately implies that \(\delta_H(v) = \delta_{H^{(0)}}(v) \le \cdots \le \delta_{H^{(t)}}(v) = \delta_G(v)\).

If \(v\) is an endpoint of \(e_i\), then \(\deg_{H^{(i)}}(v) = \deg_{H^{(i-1)}}(v) + 1\) and \(\gamma\bigl(H^{(i)} - v\bigr) \le \gamma\bigl(H^{(i-1)} - v\bigr) + 1\) because \(H^{(i)} - v\) and \(H^{(i-1)} - v\) have the same edge set and \(H^{(i)}\) has at most one more vertex than \(H^{(i-1)} - v\). Thus, using Corollary 9.7,

\[\begin{aligned} \delta_{H^{(i)}}(v) &= \deg_{H^{(i)}}(v) - \gamma\bigl(H^{(i)} - v\bigr)\\ &\ge (\deg_{H^{(i-1)}}(v) + 1) - (\gamma(H^{(i-1)} - v) + 1)\\ &= \deg_{H^{(i-1)}}(v) - \gamma(H^{(i-1)} - v)\\ &= \delta_{H^{(i-1)}}(v). \end{aligned}\]

If \(v\) is not an endpoint of \(e_i\), then \(\deg_{H^{(i)}}(v) = \deg_{H^{(i-1)}}(v)\) and \(\gamma\bigl(H^{(i)} - v\bigr) \le \gamma\bigl(H^{(i-1)} - v\bigr)\) because \(H^{(i)} - v\) can be obtained by adding the edge \(e_i\) to \(H^{(i-1)} - v\), which cannot increase the number of connected components because one endpoint of \(e_i\) is in \(H^{(i-1)}\) and, thus, since \(v\) is not an endpoint of \(e_i\), in \(H^{(i-1)} - v\). Thus,

\[\begin{aligned} \delta_{H^{(i)}}(v) &= \deg_{H^{(i)}}(v) - \gamma\bigl(H^{(i)} - v\bigr)\\ &\ge \deg_{H^{(i-1)}}(v) - \gamma\bigl(H^{(i-1)} - v\bigr)\\ &= \delta_{H^{(i-1)}}(v).\ \text{▨} \end{aligned}\]

The next lemma provides a lower bound on \(\textrm{OPT}\) when \(w\) is a cyclomatic weight function. This is the lower bound to which we compare the weight of any minimal feedback vertex set to prove that every minimal feedback vertex set has a weight no greater than \(2 \cdot \textrm{OPT}\).

Lemma 9.9: For a cyclomatic weight function, \(\textrm{OPT} \ge \alpha \cdot \mathrm{cyc}(G)\).

Proof: Consider an optimal feedback vertex set \(F = \{v_1, \ldots, v_k\}\) and consider the sequence of graphs \(G = G^{(0)} \supseteq \cdots \supseteq G^{(k)} = G - F\), where \(G^{(i)} = G^{(i-1)} - v_i\) for all \(1 \le i \le k\). Since \(G - F\) is acyclic, we have \(\mathrm{cyc}\bigl(G^{(k)}\bigr) = 0\). Thus,

\[\begin{aligned} \mathrm{cyc}(G) &= \sum_{i=1}^k \Bigl(\mathrm{cyc}\bigl(G^{(i-1)}\bigr) - \mathrm{cyc}\bigl(G^{(i)}\bigr)\Bigr)\\ &= \sum_{i=1}^k \Bigl(\mathrm{cyc}\bigl(G^{(i-1)}\bigr) - \mathrm{cyc}\bigl(G^{(i-1)} - v_i\bigr)\Bigr)\\ &= \sum_{i=1}^k \delta_{G^{(i-1)}}(v_i), \end{aligned}\]

by Corollary 9.7. Since \(G^{(i-1)} \subseteq G\) for all \(1 \le i \le k\), we have \(\delta_{G^{(i-1)}}(v_i) \le \delta_G(v_i)\), by Lemma 9.8, so

\[\mathrm{cyc}(G) \le \sum_{i=1}^k \delta_G(v_i).\]

Thus,

\[\alpha \cdot \mathrm{cyc}(G) \le \sum_{i=1}^k (\alpha \cdot \delta_G(v_i)) = \sum_{i=1}^k w_{v_i} = \textrm{OPT}.\ \text{▨}\]

Lemma 9.10: If \(w\) is a cyclomatic weight function, then every minimal feedback vertex set \(F\) satisfies \(w(F) \le 2 \cdot \textrm{OPT}\).

Proof: Since \(\textrm{OPT} \ge \alpha \cdot \mathrm{cyc}(G) = \alpha \cdot (|E| - |V| + \gamma(G))\), by Theorem 9.6 and Lemma 9.9, it suffices to prove that

\[\sum_{v \in F} \delta_G(v) \le 2(|E| - |V| + \gamma(G))\]

because this implies that

\[w(F) = \sum_{v \in F} w_v = \sum_{v \in F} \alpha \cdot \delta_G(v) \le 2\alpha \cdot (|E| - |V| + \gamma(G)) \le 2 \cdot \textrm{OPT}.\]

Furthermore, it suffices to prove this claim for connected graphs: If the claim holds for connected graphs, \(G_1 = (V_1, E_1), \ldots, G_k = (V_k, E_k)\) are the connected components of \(G\), and \(F_i = F \cap V_i\) for all \(1 \le i \le k\), then

\[\mathrm{CYC}(G) = \mathrm{CYC}(G_1) \times \cdots \times \mathrm{CYC}(G_k),\]

\[\begin{multline} \mathrm{CYC}(G - v) =\\ \mathrm{CYC}(G_1) \times \cdots \times \mathrm{CYC}(G_{i-1}) \times \mathrm{CYC}(G_i - v) \times \mathrm{CYC}(G_{i+1}) \times \cdots \times \mathrm{CYC}(G_k) \end{multline}\]

for all \(v \in F_i\), and \(F_i\) is easily verified to be a minimal feedback vertex set of \(G_i\). Thus,

\[\mathrm{cyc}(G) = \sum_{j=1}^k \mathrm{cyc}(G_j)\]

and

\[\mathrm{cyc}(G - v) = \sum_{j=1}^{i-1} \mathrm{cyc}(G_j) + \mathrm{cyc}(G_i - v) + \sum_{j=i+1}^k \mathrm{cyc}(G_j),\]

that is,

\[\delta_G(v) = \mathrm{cyc}(G) - \mathrm{cyc}(G - v) = \mathrm{cyc}(G_i) - \mathrm{cyc}(G_i - v) = \delta_{G_i}(v).\]

Thus,

\[\begin{aligned} \sum_{v \in F} \delta_G(v) &= \sum_{i=1}^k \sum_{v \in F_i} \delta_{G_i}(v)\\ &\le \sum_{i=1}^k 2(|E_i| - |V_i| + 1)\\ &= 2(|E| - |V| + k)\\ &= 2(|E| - |V| + \gamma(G)). \end{aligned}\]

So assume from here on that \(G\) is connected and that \(F\) is a minimal feedback vertex set of \(G\). Let \(H_1, \ldots, H_k\) be the connected components of \(G - F\) and assume that each of the first \(t\) components \(H_1, \ldots, H_t\) is adjacent to exactly one vertex in \(F\) and each of the remaining \(k - t\) components \(H_{t+1}, \ldots, H_k\) is adjacent to at least two vertices in \(F\). See Figure 9.17.

Figure 9.17: Coming soon!

We prove two claims:

Claim 9.11: \(\sum_{v \in F} \gamma(G - v) \ge |F| + t - 1\).

Claim 9.12: \(\sum_{v \in F} \deg_G(v) \le 2(|E| - |V|) + |F| + t\).

Together, these two claims imply that

\[\begin{aligned} \sum_{v \in F} \delta_G(v) &= \sum_{v \in F} (\deg_G(v) - \gamma(G - v))\\ &\le 2(|E| - |V|) + |F| + t - (|F| + t - 1)\\ &< 2(|E| - |V| + 1), \end{aligned}\]

which is what we want to prove.

Proof of Claim 9.11: For every vertex \(v \in F\), let \(S_v\) be the set of components \(H_i\) with \(1 \le i \le t\) that are adjacent to \(v\). Note that every component in \(S_v\) is a component of \(G - v\) (because every component \(H_i\) with \(1 \le i \le t\) is adjacent to exactly one vertex in \(F\)), so

\[\gamma(G - v) \ge |S_v|.\]

If \(\gamma(G - v) = |S_v|\) for some vertex \(v \in F\), then \(S_v\) is the set of components of \(G - v\). Thus, \(F = \{v\}\) and \(S_v = \{H_1, \ldots, H_t\}\), which implies that

\[\sum_{v \in F} \gamma(G - v) = |S_v| = t = |F| + t - 1.\]

If \(\gamma(G - v) > |S_v|\) for all \(v \in F\), then

\[\sum_{v \in F} \gamma(G - v) \ge \sum_{v \in F} (|S_v| + 1) = |F| + \sum_{v \in F} |S_v|.\]

Since every component \(H_i\) with \(1 \le i \le t\) is adjacent to exactly one vertex in \(F\), we have \(\sum_{v \in F} |S_v| = t\). Thus,

\[\sum_{v \in F} \gamma(G - v) \ge |F| + t.\ \text{▣}\]

Proof of Claim 9.12: We divide the edge set of \(G\) into three subsets \(E_F\), \(E_{\bar F}\), and \(E_X\). \(E_F\) is the set of edges with both endpoints in \(F\), \(E_{\bar F}\) is the set of edges with both endpoints in \(V \setminus F\), and \(E_X = E \setminus (E_F \cup E_{\bar F})\) is the set of edges with exactly one endpoint in \(F\). Then

\[\sum_{v \in F} \deg_G(v) = 2|E_F| + |E_X|.\]

For \(1 \le i \le k\), let \(V_i\) and \(E_i\) be the vertex and edge sets of \(H_i\). Since \(F\) is a feedback vertex set, every component \(H_i\) of \(G - F\) is a tree, so \(|E_i| = |V_i| - 1\). This gives

\[|E_{\bar F}| = \sum_{i=1}^k |E_i| = \sum_{i=1}^k (|V_i| - 1) = |V \setminus F| - k = |V| - |F| - k.\]

Since \(|E| = |E_F| + |E_{\bar F}| + |E_X|\), we conclude that

\[\begin{aligned} \sum_{v \in F} \deg_G(v) &= 2(|E_F| + |E_X|) - |E_X|\\ &= 2(|E| - |E_{\bar F}|) - |E_X|\\ &= 2(|E| - |V| + |F| + k) - |E_X|\\ &= 2(|E| - |V|) + 2|F| + 2k - |E_X|. \end{aligned}\]

Thus, it suffices to prove that

\[2|F| + 2k - |E_X| \le |F| + t,\]

that is,

\[|E_X| \ge |F| + 2k - t.\]

Since \(F\) is a minimal feedback vertex set, there exists some cycle \(C_v\) in \(G\) for each vertex \(v \in F\) such that \(v\) is the only vertex in \(F\) that belongs to \(C_v\).

Since each such cycle \(C_v\) contains no vertices in \(F \setminus \{v\}\), all vertices in \(C_v - v\) belong to the same component \(H_i\) of \(G - F\). Thus, \(v\) has at least two edges connecting \(v\) to \(H_i\), the two edges in \(C_v\) incident to \(v\). Removing one of these edges from \(E\) does not alter the number of vertices in \(F\) that are adjacent to \(H_i\). Let \(E_X' \subseteq E_X\) be the set of these removed edges for all cycles \(C_v\). See Figure 9.18.

Figure 9.18: Coming soon!

Since every component of \(G - F\) is adjacent to the same vertices in \(F\) in \(G\) and in \(G - E_X'\), each of the components \(H_1, \ldots, H_t\) has at least one incident edge in \(E_X \setminus E_X'\) and each of the components \(H_{t+1}, \ldots, H_k\) has at least two incident edges in \(E_X \setminus E_X'\). Thus,

\[|E_X \setminus E_X'| \ge 2(k - t) + t = 2k - t.\]

Since \(|E_X'| = |F|\), this proves that

\[|E_X| = |E_X \setminus E_X'| + |E_X'| \ge |F| + 2k - t.\ \text{▨}\]