17.2.5. Analysis

It remains to analyze the running time of the algorithm. First observe that the algorithm branches only if it applies Rule 1, 4, 7 or 8.

Rule 1 is easily analyzed: If the running time of the algorithm on a connected graph is \(O^*(c^n) = O(c^n n^d)\), then its running time on a disconnected graph \(G\) with components \(G_1, \ldots, G_k\) is \(\sum_{i=1}^k O(c^{n_i} n_i^d) = O(c^n n^d) = O^*(c^n)\), where \(n_i\) is the size of \(G_i\) for all \(1 \le i \le k\).

Next we consider Rules 4, 7, and 8.

To bound the running time of the algorithm resulting from the application of these rules, let \(\alpha\) be a constant to be determined later and define the weight of an instance \((G,F)\) as

\[w(G,F) = |V \setminus F| + \alpha|V \setminus (F \cup N(t))|,\]

where \(t\) is the current active vertex. In other words, every vertex in \(F\) has weight \(0\), every neighbour of the active vertex \(t\) has weight \(1\), and every vertex not in \(F\) that is not a neighbour of \(t\) has weight \(1+\alpha\).

Rule 4

Since \(F = \emptyset\) when this rule is applied, there is no active vertex \(t\). Thus, every vertex \(v \in V \setminus F\) has weight \(1+\alpha\). Therefore, \(w(G-v,F) \le w(G,F) - 1 - \alpha\). In the recursive call on the input \((G, F \cup \{v\})\), observe that \(v\) is the only vertex in \(F \cup \{v\}\) and thus becomes the active vertex. Therefore, \(v\)'s weight drops from \(1+\alpha\) to \(0\) and the weight of each of its neighbours drops from \(1+\alpha\) to \(1\). Since \(\deg(v) \ge 2\), this gives \(w(G, F \cup \{v\}) \le w(G) - 1 - 3\alpha\). Thus, the branching vector of this rule is \((1 + \alpha, 1 + 3\alpha)\).

Rule 7

Since \(v\) is a neighbour of the active vertex when this rule applies, its weight is \(1\). Thus, \(w(G - v, F) \le w(G,F) - 1\). Adding \(v\) to \(F\) in the recursive call on \((G, F \cup \{v\})\) creates a non-trivial component \(T\) of \(G[F \cup \{v\}]\) that is replaced with a single vertex \(v_T\) by Rule 2. Every generalized neighbour of \(v\) of weight \(1\) is also a neighbour of \(t\) and is thus removed by the contraction. Every generalized neighbour of \(v\) of weight \(1+\alpha\) becomes a neighbour of \(v_T\) and thus its weight is reduced to \(1\). Since \(|\tilde N_t(v)| \ge 3\), this shows that \(w(G,F \cup \{v\}) \le w(G) - 1 - 3\alpha\) as long as \(\alpha \le 1\). The branching vector of this rule is thus \((1, 1+3\alpha)\).

Rule 8

Let \(h \in \{0,1,2\}\) be the number of generalized neighbours of \(v\) of weight \(1+\alpha\). By the same argument as for Rule 7, the weight of every generalized neighbour of \(v\) of weight \(1+\alpha\) drops to \(1\) in the recursive call on the input \((G,F \cup \{v\})\) and every generalized neighbour of \(v\) of weight \(1\) is removed. Thus, \(w(G, F \cup \{v\}) \le w(G,F) - 3 + h - \alpha h\). In the instance \((G-v, F \cup \{w_1,w_2\})\), both \(w_1\) and \(w_2\) have weight \(0\). Thus, \(w(G-v, F \cup \{w_1,w_2\}) \le w(G,F) - 3 - \alpha h\). Therefore, this rule has the branching vector \((3 - h + \alpha h, 3 + \alpha h)\).

Overall, we obtain 5 branching vectors, one for Rule 4, one for Rule 7, and one for each of the possible values of \(h\) in Rule 8. Since no vertex has weight greater than \(1+\alpha\), we have \(w(G,F) \le (1+\alpha)n\) and the algorithm has running time \(O^*(c_\alpha^n)\), where \(c_\alpha = d_\alpha^{1+\alpha}\) and \(d_\alpha\) is the maximum branching number of these 5 branching vectors. An exhaustive search to determine the value \(\alpha\) that minimizes \(c_\alpha\) yields \(\alpha = 0.565\) and thus \(d_\alpha = 1.5109\) and \(c_\alpha = 1.89\). Thus, the algorithm takes \(O^*(1.89^n)\) time and we obtain the following result:

Theorem 17.4: The feedback vertex set problem can be solved in \(O^*(1.89^n)\) time.