17.1. Maximum Independent Set

Recall the maximum independent set algorithm from Section 16.3.1. The following algorithm is a faster version of this algorithm:

• If \(G\) has an isolated vertex \(v\), then compute a maximum independent set \(I\) of \(G - v\) and then return \(I \cup \{v\}\).

• If \(G\) has a vertex \(u\) of degree \(1\), then compute a maximum independent set \(I\) of \(G - \{u, v\}\), where \(v\) is \(u\)'s neighbour, and return \(I \cup \{u\}\).

• If \(G\) has a vertex of degree at least \(3\), then choose a maximum-degree vertex \(v\), recursively compute maximum independent sets \(I_1\) and \(I_2\) of \(G - v\) and \(G - N[v]\), respectively, and return the larger of \(I_1\) and \(I_2 \cup \{v\}\).

• If none of the previous three cases applies, then every vertex in \(G\) has degree \(2\). Thus, \(G\) is a collection of simple cycles. By the following exercise, a maximum independent set of \(G\) can be computed in linear time in this case. Thus, the algorithm does not make any recursive calls in this case.

Exercise 17.1: Consider any graph \(G\) whose vertices have degree at most \(2\). Prove that a maximum independent set of \(G\) can be computed in linear time.

The only case where the algorithm branches is the third case and this case has the branching vector \((1,4)\) because \(|N[v]| \ge 4\) if \(v\) has degree at least \(3\). Thus, the bound on the running time of the algorithm that we can prove by considering only the input size of each recursive call is \(O^*(1.39^n)\) since \(1.39\) is the unique real root of the polynomial \(x^4 - x^3 - 1\). As an introduction to the Measure and Conquer technique, we will use it to prove that this algorithm in fact achieves a running time of \(O^*(1.30^n)\).

Recall the main idea: We want to give weights to the vertices of the graph that capture how much they contribute to the running time of the algorithm. Here, it is the degree of each vertex that determines its impact on the running time of the algorithm. We will assign weight \(w_0\) to degree-\(0\) vertices, weight \(w_1\) to degree-\(1\) vertices, weight \(w_2\) to degree-\(2\) vertices, and weight \(w_{\ge 3}\) to vertices of degree at least \(3\).

Degree-0 and degree-1 vertices are removed by each invocation before making recursive calls. Thus, they do not cause the algorithm to branch at all and should have weight \(0\): \(w_0 = w_1 = 0\). Vertices of degree at least \(3\) are the ones the algorithm branches on, so we give them weight \(1\): \(w_{\ge 3} = 1\). The degree-\(2\) vertices are the interesting ones. Let us inspect some intuitive choices of their weight \(w_2\).

First, since we never branch on degree-\(2\) vertices, we may be tempted to set \(w_2 = 0\). If \(n_0\), \(n_1\), \(n_2\), and \(n_{\ge 3}\) are the numbers of vertices of degree \(0\), \(1\), \(2\), and at least \(3\) in \(G\), respectively, then

\[w(G) = w_0n_0 + w_1n_1 + w_2n_2 + w_{\ge 3}n_{\ge 3} = n_{\ge 3}.\]

When the algorithm branches on a vertex \(v\) of degree at least \(3\), both recursive calls made by the algorithm remove \(v\) from \(G\). Since \(v\) has degree at least \(3\), we have \(w(G - v) \le w(G) - 1\) and \(w(G - N[v]) \le w(G) - 1\). Indeed, we cannot offer a stronger guarantee than \(w(G - N[v]) \le w(G) - 1\) even though \(|N(v) \ge 3|\) because all neighbours of \(v\) may be degree-\(2\) vertices and thus may not contribute to \(G\)'s weight. Therefore, this algorithm has the branching vector \((1,1)\) with respect to \(w(G)\) and achieves the running time \(O^*\bigl(2^{w(G)}\bigr)\). Since \(w(G) = n_{\ge 3} \le n\), this proves that the algorithm runs in \(O^*(2^n)\) time, a pretty poor bound that falls short of the \(O^*(1.39^n)\) bound we can prove using much more elementary means.

What this analysis shows us is that we should count degree-\(2\) vertices because they may be part of the neighbourhood of a degree-\(3\) vertex and thus lead to a weight reduction in the second recursive call when the algorithm branches.

So, let us try to set \(w_2 = 1\), that is,

\[w(G) = n_2 + n_{\ge 3}.\]

Not surprisingly, we now obtain the branching vector \((1,|N[v]|)\) because, after removing vertices of degree at most \(1\), \(n_2 + n_{\ge 3}\) is simply the number of vertices in \(G\). Since \(|N[v]| \ge 4\), we obtain a running time bound of \(O^*\bigl(1.39^{w(G)}\bigr) = O^*(1.39^n)\) as when simply considering the input size.

The "right" choice of \(w_2\) captures that degree-\(2\) vertices are "less expensive" than vertices of degree at least \(3\) because they never cause the algorithm to branch but "more expensive" than degree-0 and degree-1 vertices because they may not be removed immediately and thus may contribute to the neighbourhoods of vertices of degree at least \(3\), which do cause the algorithm to branch.

So let us try to choose \(w_2 = \frac{1}{2}\), that is,

\[w(G) = \frac{n_2}{2} + n_{\ge 3}.\]

Now we consider two cases:

• If the vertex \(v\) the algorithm branches on has degree \(d \ge 4\), then let \(d_2\) be the number of degree-\(2\) neighbours of \(v\) and let \(d_{\ge 3} = d - d_2\) be the number of neighbours of degree at least \(3\). Every degree-\(2\) neighbour of \(v\) has degree \(1\) in \(G - v\). Thus, its weight is \(1/2\) in \(G\) but \(0\) in \(G-v\). Since \(v\) contributes \(1\) to the weight of \(G\), we have \(w(G-v) \le w(G) - 1 - \frac{d_2}{2}\). \(G - N[v]\) does not contain any of the vertices in \(N[v]\). Since \(v\) and its neighbours of degree at least \(3\) each contribute \(1\) to \(w(G)\) and each degree-\(2\) neighbour contributes \(\frac{1}{2}\) to \(w(G)\), we have \(w(G - N[v]) \le w(G) - 1 - \frac{d_2}{2} - d_{\ge 3}\). Overall, the branching vector is \(\bigl(1 + \frac{d_2}{2}, 1 + \frac{d_2}{2} + d_{\ge 3}\bigr)\). In other words, the branching vector is \((b_1, b_2)\) such that \(b_1, b_2 \ge 1\) and \(b_1 + b_2 = d + 2\). Elementary calculus shows that the worst such branching vector is \((1, d+1)\). Since \(d \ge 4\), the branching vector is no worse than \((1,5)\), which gives a branching number of \(1.33\).

• If \(v\) has degree \(3\), then every vertex in \(G\) has degree \(2\) or \(3\) because we always branch on a vertex of maximum degree and vertices of degree at most \(1\) have been removed. In \(G - v\), every degree-\(2\) neighbour of \(v\) becomes a degree-\(1\) vertex, so its weight drops from \(\frac{1}{2}\) to \(0\). every degree-\(3\) neighbour becomes a degree-\(2\) neighbour, so its weight drops from \(1\) to \(\frac{1}{2}\). Thus, \(w(G - v) \le w(G) - 1 - \frac{3}{2}\). \(G - N[v]\) does not contain \(v\) nor any of its \(3\) neighbours. The weight of \(G - N[v]\) is maximized if all neighbours of \(v\) have degree \(2\), which gives \(w(G - N[v]) \le w(G) - 1 - \frac{3}{2}\) again. Thus, the algorithm has the branching vector \((2.5, 2.5)\) in this case. This gives a branching number of 1.32. Since this is better than the branching number in the previous case, the algorithm has running time \(O^*\bigl(1.33^{w(G)}\bigr)\), which is \(O^*\bigl(1.33^n\bigr)\) because \(w(G) \le n\).

This proves the following result:

Theorem 17.1: The maximum independent set problem can be solved in \(O^*(1.33^n)\) time.

Is this indeed the worst-case running time of the algorithm or can the analysis be improved? By refining the analysis so it distinguishes between degree-\(3\) vertices and vertices of degree at least \(4\) and choosing \(w_2 = 0.5966\), \(w_3 = 0.9286\), and \(w_{\ge 4} = 1\), we can prove that the algorithm's running time is \(O^*(1.30^n)\). Determining the optimal weights is generally infeasible to do manually, especially as the number of weights to be determined increases. Thus, the optimal weights are usually determined using a computer-aided exhaustive search.

It is important to emphasize once more that all these "improvements" are not improvements of the algorithm. We only succeed in proving tighter upper bounds on the running time of the same algorithm.