16.2.1. Vertex Cover and (Not) Independent Set

Since we want to obtain an FPT algorithm for the vertex cover problem, we once again consider the parameterized version of the problem, which asks whether a given graph \(G\) has a vertex cover of size at most \(k\). All the parameterized branching algorithms we discuss do more than decide whether a given input \((G,k)\) is a yes-instance. If \((G,k)\) is a no-instance, the algorithm returns "No". Otherwise, it returns an optimal solution, a minimum vertex cover in the case of the vertex cover problem.

The key idea behind the branching algorithms discussed so far was to ensure that every recursive call made by the algorithm has a strictly smaller input than the current invocation. This led to a branching vector \((b_1, \ldots, b_t)\) where \(b_i > 0\) for all \(1 \le i \le t\) and, hence, to a running time of the form \(O^*(c^n)\), where \(c\) is the corresponding branching number. In order to achieve a running time of the form \(O^*\bigl(c^k\bigr)\), we need to ensure that the algorithm has a branching vector \((b_1, \ldots, b_t)\) with \(b_i > 0\) for all \(1 \le i \le t\) but not in terms of the input size but in terms of the problem parameter \(k\). In other words, if the current problem instance is \((G, k)\), then we need to ensure that each recursive call has as its input a problem instance \((G_i, k_i)\) with \(k_i = k - b_i\) for some \(b_i > 0\). This technique is called depth-bounded search—the recursion depth is bounded by the parameter \(k\)—and is exactly what the vertex cover algorithm discussed already in Section 8.4 does. Here it is again:

\(\boldsymbol{\textbf{VC}(G, k)}\):

• If \(k < 0\), then answer "No": There clearly is no vertex cover of negative size for any graph.

• If \(k \ge 0\) and \(G\) has no edges, then return \(\emptyset\): To cover no edges, we do not need any vertices in the vertex cover.

• If \(k \ge 0\) and \(G\)'s edge set is non-empty, then choose an arbitrary vertex \(v\) of degree at least \(1\). Make two recursive calls \(\boldsymbol{\textbf{VC}(G - v, k-1)}\) and \(\boldsymbol{\textbf{VC}(G - N[v], k-|N(v)|)}\).

  • If both recursive calls return "No", then return "No".

  • If the first recursive call returns a minimum vertex cover \(C_v\) of \(G-v\) and the second recursive call returns "No" or a minimum vertex cover \(C_{N(v)}\) of \(G - N[v]\) of size \(|C_{N(v)}| > |C_v| - |N(v)|\), then return \(C_v \cup \{v\}\).

  • If the second recursive call returns a minimum vertex cover \(C_{N(v)}\) of \(G-N[v]\) and the first recursive call returns "No" or a minimum vertex cover \(C_v\) of \(G-v\) of size \(|C_v| \ge |C_{N(v)}| + |N(v)|\), then return \(C_{N(v)} \cup N(v)\).

The following consequence of Lemma 16.1 shows that this algorithm is correct:

Lemma 16.5: For an arbitrary vertex \(v \in G\), \((G, k)\) is a yes-instance if and only if either \((G - v, k - 1)\) or \((G - N[v], k - |N(v)|)\) is a yes-instance.

Proof: Let \(C\) be a minimum vertex cover of \(G\), let \(C_v\) be a minimum vertex cover of \(G - v\), and let \(C_{N(v)}\) be a minimum vertex cover of \(G - N[v]\). By Lemma 16.1, \(|C| = \min(|C_v| + 1, |C_{N(v)}| - |N(v)|)\).

If \((G,k)\) is a yes-instance, then \(|C| \le k\) and, therefore, \(|C_v| \le k - 1\) or \(|C_{N(v)}| \le k - |N(v)|\). Thus, \((G - k, k - 1)\) or \((G - N[v], k - |N(v)|)\) is a yes-instance.

If \((G-v,k-1)\) is a yes-instance, then \(|C_v| \le k-1\), so \(|C| \le |C_v| + 1 \le k\), that is, \((G,k)\) is a yes-instance.

If \((G-N[v], k-|N(v)|)\) is a yes-instance, then \(|C_{N(v)]}| \le k - |N(v)|\), so \(|C| \le |C_{N(v)}| + |N(v)| \le k\), that is, \((G,k)\) is a yes-instance once again. ▨

Since \(v\) has degree at least \(1\), \(|N(v)| \ge 1\). Thus, \(k - |N(v)| \le k - 1\). This shows that the parameters of the instances in both recursive calls of the algorithm are at most \(k - 1\). Therefore, the algorithm has branching vector \((1,1)\), but this time in terms of the parameter, not in terms of the input size. Its running time is thus \(O^*\bigl(2^k\bigr)\).

Does the same strategy work to obtain an FPT algorithm for the independent set problem? Based on what we said before—independent set is \(W[1]\)-hard—the answer should be no, but why? As far as the input size is concerned, the maximum independent set algorithm from Section 16.1 has branching vector \((1, 1)\) and is essentially the same as the vertex cover algorithm. However, in the case of independent set, our analysis from Section 16.1 shows that \(G\) has an independent set of size at least \(k\) if and only if \(G-v\) has an independent set of size at least \(k\) or \(G-N[v]\) has an independent set of size at least \(k-1\). Thus, the branching vector with respect to the size of the independent set, the parameter, is \((0, 1)\). This is insufficient to prove any bound on the number of recursive calls that depends only on the problem parameter \(k\). Remember, we need a branching vector where all components are strictly positive.