16.4.2.1. Case 1: Disconnected Graphs

If \(G\) has \(t \ge 2\) connected components \(G_1, \ldots, G_t\), then note that a subset of vertices \(C\) of \(G\) is a minimum vertex cover of \(G\) if and only if it is the union of minimum vertex covers of \(G_1, \ldots, G_t\). Since we removed all isolated vertices, each connected component \(G_i\) of \(G\) has at least one edge, so a minimum vertex cover of \(G_i\) must contain at least one vertex. Thus, if \(t > k\), then \(G\) has no vertex cover of size at most \(k\), and we return "No".

If \(t \le k\), then we make \(t\) recursive calls on the instances \(\bigl(G_1,k'\bigr), \ldots, \bigl(G_t,k'\bigr)\), where \(k' = k - t + 1 \le k - 1\). If any of these recursive calls on an input \(\bigl(G_i,k'\bigr)\) returns "No", then \(G_i\) has no vertex cover of size at most \(k'\) and, therefore, a minimum vertex cover of \(G\) has size at least \(k' + 1 + (t - 1) = k + 1\). This shows that \((G,k)\) is a no-instance if any recursive call on an input \((G_i,k')\) returns "No". Thus, we return "No" in this case.

If none of the recursive calls returns "No", then let \(C_1, \ldots, C_t\) be the minimum vertex covers of \(G_1, \ldots, G_t\) returned by the recursive calls. As just observed, \(C = C_1 \cup \cdots \cup C_t\) is a minimum vertex cover of \(G\). Thus, we return \(C\) if \(|C| \le k\) or "No" if \(|C| > k\).

We do not analyze the branching number of this case. Instead, we will argue in the final analysis that all applications of this case increase the running time of the algorithm by at most a constant factor, due to the fact that the subgraphs \(G_1, \ldots, G_t\) in the recursive calls are smaller than \(G\) and their total size is exactly the size of \(G\).