16.3.1. Vertex Cover and Independent Set

Our analysis of the two algorithms for minimum vertex cover and independent set in Section 16.1 was based on the observation that each invocation makes recursive calls on two subgraphs \(G-v\) and \(G - N[v]\) of \(G\), each with at most \(n-1\) vertices. However, if \(|N[v]| \ge 2\), then the second graph has at most \(n-2\) vertices, that is, our analysis is overly pessimistic. Under which circumstances can we have \(|N[v]| = 1\)? Clearly, \(v\) cannot have any neighbours in this case. However, this case can be dealt with without branching. If \(v\) has no neighbours, then any vertex cover of \(G-v\) is also a vertex cover of \(G\) and vice versa, that is, we find a minimum vertex cover of \(G\) by recursing only on \(G-v\). This is exactly the idea of the singleton reduction in Section 15.2.1. Similarly, \(v\) belongs to every maximum independent set \(I\) of \(G\) and \(I \setminus \{v\}\) is a maximum independent set of \(G-v\). Thus, we can once again find a maximum independent set without branching by computing a maximum independent set \(I'\) of \(G-v\) and then adding \(v\) to this set.

As a result of this strategy, we branch only if \(|N[v]| \ge 2\), so the algorithm now has branching vector \((1, 2)\). This gives a branching number of \(c\), where \(c\) is the smallest real root of the polynomial

\[x^2 = x + 1,\]

which is \(c = 1 + \sqrt{2} \approx 1.62\).

Can we do even better? Degree-1 reduction to the rescue. If \(u\) is a degree-\(1\) vertex with neighbour \(v\), then Observation 15.3 shows that a minimum vertex cover of \(G\) can be obtained by computing a minimum vertex cover \(C\) of \(G-\{u, v\}\) and then adding \(v\) to \(C\). Thus, the algorithm does not even need to branch on degree-\(1\) vertices. The following observation establishes an analogous result for the maximum independent set problem.

Observation 16.8: If \(u\) is a degree-\(1\) vertex of a graph \(G\), \(v\) is \(u\)'s neighbour, and \(I\) is a maximum independent set of \(G - \{u, v\}\), then \(I \cup \{u\}\) is a maximum independent set of \(G\).

Proof: First observe that \(I \cup \{u\}\) is an independent set of \(G\) because \(I\) is an independent set of \(G - \{u, v\}\) and \(u\) is not adjacent to any vertex in \(V \setminus \{u, v\}\).

Now let \(I'\) be a maximum independent set of \(G\) and assume for the sake of contradiction that \(|I'| > |I| + 1\). Since \(u\) and \(v\) are adjacent, we have \(|I' \cap \{u, v\}| \le 1\). Thus, \(|I' \setminus \{u, v\}| \ge |I'| - 1 > |I|\). Since \(I' \setminus \{u, v\}\) is an independent set of \(G - \{u, v\}\), this is a contradiction. ▨

Based on these observations, the vertex cover and maximum independent set algorithms can avoid branching unless the chosen vertex \(v\) has degree at least \(2\). In this case, \(|N[v]| \ge 3\) and the branching vector of the algorithm becomes \((1, 3)\). This gives a branching number of \(c\), where \(c\) is the smallest real root of the polynomial

\[x^3 = x^2 + 1,\]

which is \(c \approx 1.47\). This proves the following result:

Lemma 16.9: The minimum vertex cover problem and the maximum independent set problem can be solved in \(O^*(1.47^n)\) time.

In Chapter 17, we will improve on this result further, but doing so requires measure-and-conquer, an advanced technique that allows us to obtain even tighter analyses of the running times of branching algorithms.

Returning to the parameterized version of vertex cover, we observe that the above strategy can be used to improve this algorithm as well. We observed that \((G, k)\) is a yes-instance of the vertex cover problem if and only if \((G-v, k-1)\) or \((G-N[v], k - |N(v)|)\) is a yes-instance. If \(v\) has degree at most \(1\), then Observations 15.2 and 15.3 show that \((G, k)\) is a yes-instance if and only if \((G-N[v], k - |N(v)|)\) is. Thus, we can avoid making any recursive calls in this case and simply remove the vertices in \(N[v]\) from \(G\) and decrease \(k\) by \(|N(v)|\). If \(v\) has degree at least \(2\), then the two recursive calls on the inputs \((G-v, k-1)\) and \((G-N[v], k - |N(v)|)\) have parameters \(k-1\) and at most \(k-2\), respectively. Thus, the algorithm achieves a branching vector of \((1,2)\) with respect to the parameter \(k\) and the running time of the algorithm is \(O^*\bigl(1.62^k\bigr)\).

Lemma 16.10: It takes \(O^*\bigl(1.62^k\bigr)\) time to decide whether a graph \(G\) has a vertex cover of size at most \(k\) and, if so, compute a minimum vertex cover of \(G\).