9.4.1.2. Cyclomatic Weight Functions

The greedy strategy a feedback vertex set algorithm should follow can be expressed intuitively as follows: Pick vertices that are cheap and whose removal from \(G\) destroys as many cycles as possible. For example, in Figure 9.13, \(x\) is a cheap vertex but destroys only the leftmost cycle. \(y\) is only slightly more expensive and its removal destroys all cycles in \(G\).

Figure 9.13: Coming soon!

In this example, it was easy to see that it is better to include \(y\) in a feedback vertex set than \(x\). In general, it may be hard to count how many cycles get destroyed by removing a vertex from \(G\). We start the discussion in this section by introducing the right measure of the number of cycles destroyed by removing a vertex, using the terminology from linear algebra introduced in the previous section.

Let \(G = (V, E)\) be the graph for which we want to compute a feedback vertex set. Let \(e_1, \ldots, e_m\) be the edges of \(G\), arranged in an arbitrary but fixed order.

Every subset \(E' \subseteq E\) can be represented as an \(m\)-dimensional characteristic vector \(\chi(E') = (x_1, \ldots, x_n)\) over \(\textrm{GF}[2]\), where \(E' = \{e_i \in E \mid x_i = 1\}\).

The cycle space \(\boldsymbol{\textbf{CYC}(G)}\) of \(G\) is the subspace of \(\textrm{GF}[2]^m\) spanned by the characteristic vectors of all simple cycles in \(G\).

Since addition in \(\textrm{GF}[2]\) is equivalent to the Boolean exclusive-or operation, it is not hard to see that the vectors in \(\mathrm{CYC}(G)\) represent all subsets of edges of \(G\) that form collections of edge-disjoint simple cycles in \(G\). See Figure 9.14.

Figure 9.14: Coming soon!

The cyclomatic number of \(G\), denoted \(\mathrm{cyc}(G)\) is the dimension \(\dim(\mathrm{CYC}(G))\) of \(\mathrm{CYC}(G)\).

In particular, \(\mathrm{cyc}(G) = 0\) if and only if \(G\) is acyclic, that is, if and only if \(G\) is a forest. Since a feedback vertex set \(F\) has the property that \(G - F\) is acyclic, it seems reasonable to include those vertices in \(F\) that are cheap and whose removal from \(G\) decreases \(\mathrm{cyc}(G)\) as much as possible.

Let \(\delta_G(v) = \textrm{cyc}(G) - \textrm{cyc}(G - v)\) be the the reduction in the cyclomatic number of \(G\) achieved by removing \(v\) and its incident edges from \(G\).

We call a weight function \(w : V \rightarrow \mathbb{R}\) cyclomatic if \(w_v = \alpha \cdot \delta_G(v)\) for every vertex \(v \in V\) and some constant \(\alpha > 0\).

A minimal feedback vertex set is a feedback vertex set \(F\) such that no proper subset of \(F\) is a feedback vertex set.

By the following exercise, a minimal feedback vertex set can be found in polynomial time.

Exercise 9.2: Show that a minimal feedback vertex set can be found in \(O(nm)\) time. (Hint: Start with the trivial feedback vertex set \(F = V\) and then shrink it at most \(n\) times to obtain a minimal feedback vertex set.)

The central claim, which we prove in Lemma 9.10 in the next subsection, is that a minimal feedback vertex set is a \(2\)-approximation of an optimal feedback vertex set if the weight function is cyclomatic. Thus, we obtain the following result:

Lemma 9.5: A \(2\)-approximation of an optimal feedback vertex set with respect to a cyclomatic weight function can be computed in polynomial time.