20.1. Vertex Cover

As just explained, we consider the subgraphs \(G_1, \ldots, G_n\), where \(V = \{v_1, \ldots, v_n\}\), \(V_i = \{v_1, \ldots, v_i\}\), and \(G_i = G[V_i]\). Since \(G_1\) has no edges, an optimal vertex cover \(C_1\) of \(G_1\) is easily found: \(C_1 = \emptyset\). For \(k \ge 0\) (the only interesting case), this vertex cover has size at most \(k\).

Given a vertex cover \(C_i\) of \(G_i\) of size at most \(k\), \(C_{i+1}' = C_i \cup \{v_{i+1}\}\) is a vertex cover of \(G_{i+1}\) of size at most \(k+1\). Indeed, every edge in \(G_{i+1}\) that is not an edge of \(G_i\), and thus may not be covered by \(C_i\), is incident to \(v_{i+1}\). The following lemma provides the key to compressing \(C_{i+1}'\) into an optimal vertex cover \(C_{i+1}\) of \(G_{i+1}\).

Lemma 20.1: Let \(\emptyset \subseteq I \subseteq C_{i+1}'\) and let \(D = C_{i+1}' \setminus I\), that is, \(\{I, D\}\) is a partition of \(C_{i+1}'\). \(I \cup N(D)\) is a vertex cover of \(G_{i+1}\) if and only if \(D\) is an independent set. Moreover, there exists such a partition \(\{I, D\}\) of \(C_{i+1}'\) such that \(I \cup N(D)\) is a minimum vertex cover of \(G_{i+1}\).

Proof: If \(D\) is not an independent set, then \(I \cup N(D)\) cannot be a vertex cover because \((I \cup N(D)) \cap D = \emptyset\), so any edge with both its endpoints in \(D\) is not covered by \(I \cup N(D)\).

Now assume that \(D\) is an independent set and consider any edge \((u, v) \in G_{i+1}\). Since \(C_{i+1}'\) is a vertex cover of \(G_{i+1}\), we have, \(C_{i+1}' \cap \{u, v\} \ne \emptyset\), that is, w.l.o.g., \(u \in C_{i+1}'\). If \(u \in I\), then the edge \((u, v)\) is covered by \(I \cup N(D)\). If \(u \in D\), then \(v \notin D\) because \(D\) is an independent set. Thus, \(v \in N(D)\) and, once again, \(I \cup N(D)\) covers the edge \((u, v)\).

To prove that there exists a partition \(\{I, D\}\) such that \(I \cup N(D)\) is a minimum vertex cover, let \(C\) be a minimum vertex cover of \(G_{i+1}\), let \(I = C \cap C_{i+1}'\) and \(D = C_{i+1}' \setminus C\). Since \(C \cap D = \emptyset\) and \(C\) is a vertex cover of \(G_{i+1}\), \(D\) must be an independent set. Thus, as just shown, \(I \cup N(D)\) is a vertex cover of \(G_{i+1}\). To see that it is a minimum vertex cover, it suffices to prove that \(I \cup N(D) \subseteq C\).

Clearly, \(I = C \cap C_{i+1}' \subseteq C\). If \(N(D) \not\subseteq C\), then there exists a vertex \(u \in N(D) \setminus C\). Since \(u \in N(D)\), there exists an edge \((u, v) \in G_{i+1}\) such that \(v \in D = C_{i+1}' \setminus C\), that is, \(v \notin C\). Since \(u, v \notin C\), this is a contradiction because \(C\) must cover the edge \((u, v)\). ▨

By Lemma 20.1, the smallest set \(C_{i+1}\) in the following set \(\mathcal{C}_{i+1}\) is a minimum vertex cover of \(G_{i+1}\):

\[\mathcal{C}_{i+1} = \{ I \cup N(D) \mid I \cap D = \emptyset \text{ and } I \cup D = C'_{i+1} \text{ and } \text{\(D\) is an independent set} \}\]

There are \(2^{|C_{i+1}'|} \le 2^{k+1}\) partitions of \(C_{i+1}'\) into disjoint subsets \(I\) and \(D\). For each partition, it takes linear time to test whether \(D\) is an independent set of \(G_{i+1}\), so \(\mathcal{C}_{i+1}\) can be constructed in \(O^*\bigl(2^k\bigr)\) time. Choosing the smallest set in \(\mathcal{C}_{i+1}\) then takes \(O(|\mathcal{C}_{i+1}|) = O\bigl(2^k\bigr)\) time. Thus, we can construct a minimum vertex cover \(C_{i+1}\) of \(G_{i+1}\) from \(C'_{i+1}\) in \(O^*\bigl(2^k\bigr)\) time.

Since we apply this compression step once for each of the graphs \(G_2, \ldots, G_n\), we obtain the following result:

Theorem 20.2: Using iterative compression, it takes \(O^*\bigl(2^k\bigr)\) time to decide whether a graph \(G\) has a vertex cover of size at most \(k\) and, if so, find a minimum vertex cover of \(G\).

For completeness, here is the pseudo-code of the algorithm:

PROCEDURE \(\boldsymbol{\textbf{IterativeCompressionVC}(G,k)}\):

---

INPUT:

• An undirected \(G = (V,E)\)
• A non-negative integer \(k\)

OUTPUT:

• A minimum vertex cover of \(G\) if there is such a vertex cover of size at most \(k\); None otherwise

---

Let \(\langle v_1, \ldots, v_n \rangle\) be the sequence of vertices in \(G\), in an arbitrary order.
Let \(C_1 = \emptyset\)
FOR \(i = 1\) TO \(n - 1\) DO
    Let \(V_i = \{ v_1, \ldots, v_i \}\) and \(G_i = G[V_i]\)
    \(C_{i+1}' = C_i \cup \{v_{i+1}\}\)
    \(C_{i+1} = \boldsymbol{\textbf{CompressVertexCover}(G_{i+1}, C_{i+1}', k)}\)
    IF \(C_{i+1} = \textbf{None}\) THEN
        RETURN None
RETURN \(C_n\)

PROCEDURE \(\boldsymbol{\textbf{CompressVertexCover}(G_{i+1}, C_{i+1}', k)}\):

---

INPUT:

• A subgraph \(G_{i+1} \subseteq G\)
• A vertex cover \(C_{i+1}'\) of \(G_{i+1}\) of size at most \(k + 1\)
• A parameter \(k\)

OUTPUT:

• A minimum vertex cover of \(G_{i+1}\) if there is such a vertex cover of size at most \(k\); None otherwise

---

\(C_{i+1} = C_{i+1}'\)
FOR ALL \(\emptyset \subseteq I \subseteq C_{i+1}'\) DO
    \(D = C_{i+1}' \setminus I\)
IF \(D\) is an independent set of \(G_{i+1}\) and \(|I \cup N(D)| < |C_{i+1}|\) THEN
        \(C_{i+1} = I \cup N(D)\)
IF \(|C_{i+1}| \le k\) THEN
    RETURN \(C_{i+1}\)
ELSE     RETURN None