15.3.1. Vertex Cover

In Section 15.2.1, we proved that a kernel for the vertex cover problem with at most \(k(k+1)\) vertices and at most \(k^2\) edges can be obtained using simple reduction rules. Such a kernel is unsatisfactory. We observed before that the vertex cover problem can be solved in \(O^*\bigl(2^n\bigr)\) time. On a kernel with \(k^2\) vertices, this gives a running time of \(O^*\Bigl(2^{k^2}\Bigr)\), which is super-exponential. A kernel of size at most \(ak\), for some constant \(a\), on the other hand, gives a solution to the vertex cover problem with running time \(O^*\bigl(2^{ak}\bigr) = O^*\bigl(c^k\bigr)\), where \(c = 2^a\). In this section, we show how to obtain a kernel of size at most \(3k\), that is, we can solve the vertex cover problem in \(O^*\bigl(8^k\bigr)\) time. In Section 15.4, we show how to obtain a kernel of size at most \(2k\) using linear programming. This results in an algorithm with running time \(O^*\bigl(4^k\bigr)\). A kernel of size \(2k\) can also be obtained using slightly less heavy-handed tools, which we discuss in Section 15.5.

The kernelization algorithm for vertex cover based on crown reduction applies a single reduction rule, once! We compute a maximal matching \(M_1\) of \(G\) and partition \(V\) into two subsets \(V_0\) and \(V_1\), where \(V_0\) contains all vertices unmatched by \(M_1\) and \(V_1\) contains all vertices matched by \(M_1\). Then we compute a matching \(M_2\) of \(G[V_0, V_1] = (V_0, V_1, \{(u,v) \in E \mid u \in V_0, v \in V_1\})\) that matches every vertex in \(V_0\) or a crown \((I, H)\) of \(G[V_0, V_1]\) using Lemma 15.11. If the algorithm returns a matching \(M_2\), we return \((G, k)\) as the problem kernel. If it returns a crown \((I, H)\) of \(G[V_0, V_1]\) and \(|H| > k\), we report that \((G, k)\) is a no-instance. If \(|H| \le k\), we return \((G[V \setminus (I \cup H)], k - |H|)\) as the problem kernel. This is illustrated in Figure 15.4.

Figure 15.4:

Lemma 15.12: The above crown reduction is a sound reduction rule for the vertex cover problem.

Proof: We can assume that we fail to find a matching \(M_2\) of \(G[V_0, V_1]\) that matches every vertex in \(V_0\) because otherwise the returned problem kernel is \((G, k)\) and is thus a yes-instance if and only if \((G, k)\) is.

Thus, let \((I, H)\) be the crown returned by the algorithm from Lemma 15.11. If \(|H| > k\), then \(G[I, H] \subseteq G\) has a matching of size \(|H| > k\). Thus, \(G\) has no vertex cover of size at most \(k\) and \((G, k)\) is a no-instance. If \(|H| \le k\), it remains to prove that \((G, k)\) is a yes-instance if and only if \((G[V \setminus (I \cup H)], k - |H|)\) is a yes-instance. For notational convenience, let \(G' = G[V \setminus (I \cup H)]\) and \(k' = k - |H|\).

First assume that \((G', k')\) is a yes-instance. Then there exists a vertex cover \(C'\) of \(G'\) of size at most \(k'\). The set \(C = C' \cup H\) is a vertex cover of \(G\). Indeed, since \((I, H)\) is a crown, every edge of \(G\) that is not in \(G'\) is incident to a vertex in \(H\) and is thus covered by \(H \subseteq C\). Since the size of \(C\) is \(|C| = |C'| + |H| \le k - |H| + |H| = k\), this shows that \((G, k)\) is a yes-instance.

Next assume that \((G, k)\) is a yes-instance and let \(C\) be a vertex cover of \(G\) of size at most \(k\). Then \(C \setminus (I \cup H) = C \cap (V \setminus (I \cup H))\) is a vertex cover of \(G' = G[V \setminus (I \cup H)]\). If \(H \subseteq C\), then \(|C \setminus (I \cup H)| \le |C| - |H| \le k - |H|\), that is, \((G', k')\) is a yes-instance. Thus, it remains to prove that there exists a minimum vertex cover of \(G\) that includes \(H\).

Let \(C\) be an arbitrary minimum vertex cover of \(G\) and let \(C' = C \setminus I \cup H\). Then \(C'\) is a vertex cover of \(G\). To prove this, consider an arbitrary edge \((u, v)\) of \(G\). If \(u, v \notin I\), then \(\{u, v\} \cap C' \supseteq \{u, v\} \cap C \ne \emptyset\), that is, \(C'\) covers \((u, v)\). If w.l.o.g., \(u \in I\), then \(v \in H\), by the definition of a crown. Thus, \(H \subseteq C'\) covers \((u, v)\).

To prove that \(C'\) is a minimum vertex cover of \(G\), observe that the bipartite graph \(G[I, H]\) has a matching \(M\) of size \(|H|\) because \((I, H)\) is a crown. Since \(C\) must cover every edge in \(M\) and no two edges in \(M\) can be covered by the same vertex, we have \(|C \cap (I \cup H)| \ge |M| = |H|\). Thus, \(|C'| = |C \setminus I \cup H| = |C| - |C \cap (I \cup H)| + |H| \le |C| - |H| + |H| = |C|\), that is, \(C'\) is also a minimum vertex cover. Since \(H \subseteq C'\), this finishes the proof. ▨

To prove that the crown reduction rule produces a kernel with at most \(3k\) vertices, we need to prove that \((G, k)\) is a no-instance unless \(|V \setminus (I \cup H)| \le 3k\).

Lemma 15.13: If \((G, k)\) is a yes-instance, then \(|V \setminus (I \cup H)| \le 3k\).

Proof: Let \(M_1\) be the matching used by the crown reduction rule to construct the two vertex sets \(V_0\) and \(V_1\) and let \(M_2\) be the maximum matching of \(G[V_0, V_1]\) used by the algorithm in the proof of Lemma 15.11. Note that the algorithm either returns \(M_2\) as a matching that matches all vertices in \(V_0\) or it uses \(M_2\) to construct the crown \((I, H)\) it returns. Since no two edges in a matching can be covered by the same vertex, any vertex cover of \(G\) has to have size at least \(\max(|M_1|, |M_2|)\). Thus, if \(G\) has a vertex cover of size at most \(k\), we have \(|M_1| \le k\) and \(|M_2| \le k\).

\(V_0\) contains all vertices of \(G\) not matched by \(M_1\). If the algorithm in the proof of Lemma 15.11 returns \(M_2\), then every vertex in \(V_0\) is matched by \(M_2\), that is, every vertex in \(V\) is matched by the edges in \(M_1 \cup M_2\). If the algorithm returns a crown \((I, H)\), then \(I\) contains all vertices in \(V_0\) not matched by \(M_2\). Thus, every vertex in \(V \setminus (I \cup H)\) is matched by an edge in \(M_1 \cup M_2\). In both cases, all vertices in the problem kernel returned by the reduction rule are matched by \(M_1 \cup M_2\).

Since \(|M_1 \cup M_2| \le 2k\) and every edge in \(|M_1 \cup M_2|\) matches two vertices, this implies that the problem kernel has at most \(4k\) vertices. To obtain the tighter bound of at most \(3k\) vertices, we need to argue that this overcounts the number of vertices in the problem kernel by \(|M_2|\). Observe that every edge in \(M_2\) has exactly one endpoint in \(V_0\); the other endpoint is in \(V_1\) and is thus matched by \(M_1\). Thus, there are \(2|M_1|\) vertices matched by \(M_1\) and only \(|M_2|\) vertices matched by \(M_2\) but not by \(M_1\). The total number of vertices matched by \(M_1\) or \(M_2\) is thus at most \(2|M_1| + |M_2| \le 3k\). ▨