16.1.3. Maximum Independent Set

As another example, consider the independent set problem:

Given a graph \(G = (V, E)\), and independent set is a subset of vertices \(I \subseteq V\) such that no two vertices in \(I\) are adjacent.

Maximum Independent Set Problem: Given a graph \(G = (V, E)\), find an independent set of \(G\) of maximum size.

To construct an independent set \(I\), we once again have to decide for each vertex \(v \in V\) whether it belongs to \(I\). If \(G\) has no edges, then \(V\) is an independent set and clearly there is no larger independent set of \(G\). Otherwise, consider an arbitrary vertex \(v \in V\). Once again, for any independent set \(I\), \(I \setminus \{v\}\) is an independent set of \(G - v\) and \(I \setminus N[v]\) is an independent set of \(G - N[v]\). Conversely, any independent set of \(G - v\) is also an independent set of \(G\) and, for any independent set \(I_v\) of \(G - N[v]\), \(I_v \cup \{v\}\) is an independent set of \(G\) because no vertex in \(I_v \subseteq V \setminus N[v]\) is adjacent to \(v\). This suggests the following branching algorithm for finding a maximum independent set of a graph \(G\) that differs from the algorithm for the vertex cover problem only in some small details: If \(G\) has no edges, we return the whole vertex set of \(G\). Otherwise, we recursively compute a maximum independent set \(I_v\) of \(G - v\) and a maximum independent set \(I_{N(v)}\) of \(G - N[v]\) and output the larger of \(I_v\) and \(I_{N(v)} \cup \{v\}\). The next lemma shows that this algorithm takes \(O^*(2^n)\) time and computes a maximum independent set of \(G\).

Lemma 16.4: A maximum independent set of a graph \(G\) can be computed in \(O^*(2^n)\) time.

Proof: Since each invocation is easily implemented in \(O(n + m)\) time and every invocation that makes any recursive calls makes two recursive calls on \(G - v\) and \(G - N[v]\), exactly the same as for the vertex cover algorithm in the previous subsection, the same analysis as in the proof of Corollary 16.3 shows that the algorithm takes \(O^*(2^n)\) time.

To prove that the algorithm computes a maximum independent set, observe that, if \(G\) has no edges, then \(V(G)\) is a maximum subset of \(V(G)\) and is independent, so it is a maximum independent set. If \(G\) has an edge \((v,w)\), we need to show that the larger of \(I_v\) and \(I_{N(v)} \cup \{v\}\) is a maximum independent set of \(G\).

First observe that both \(I_v\) and \(I_{N(v)} \cup \{v\}\) are independent sets of \(G\). For \(I_v\), this is obvious because it is an independent set of \(G - v\). For \(I_{N(v)} \cup \{v\}\), observe that \(I_{N(v)}\) is an independent set of \(G - N[v]\) and \(v\) is not adjacent to any vertex in \(V \setminus N[v]\) and, thus, in particular not to any vertex in \(I_{N(v)} \subseteq V \setminus N[v]\). Thus, it remains to prove that one of \(I_v\) and \(I_{N(v)} \cup \{v\}\) is a maximum independent set of \(G\).

Assume the contrary, that is, that there exists an independent set \(I'\) of \(G\) of size \(|I'| > \max(|I_v|, |I_{N(v)}| + 1)\). Then \(I'_v = I' \setminus \{v\}\) is an independent set of \(G - v\) and \(I_{N(v)}' = I' \setminus N[v]\) is an independent set of \(G - N[v]\). If \(v \notin I'\), then \(|I'_v| = |I'| > |I_v|\), a contradiction because \(I_v\) is a maximum independent set of \(G - v\). If \(v \in C\), then \(|I_{N(v)}'| = |I'| - 1 > |I_{N(v)}|\), a contradiction because \(I_{N(v)}\) is a maximum independent set of \(G - N[v]\). This finishes the proof. ▨