15.5. A Vertex Cover Kernel via Matching*

In this section, we provide an alternative construction of a problem kernel for the vertex cover problem with at most \(2k\) vertices. This construction does not rely on linear programming and instead uses a purely combinatorial approach based on the relationship between matchings and vertex covers. Before showing how to compute a problem kernel with at most \(2k\) vertices, we need the following result, which shows that a minimum vertex cover of a bipartite graph can be computed in \(O\bigl(\sqrt{n} m\bigr)\) time. In particular, it implies that the vertex cover problem is NP-hard only if the input graph is not bipartite.

Lemma 15.19: A minimum vertex cover of a bipartite graph \(G = (U, W, E)\) can be computed in \(O\bigl(\sqrt{n} m\bigr)\) time.

Proof: By Theorem 7.13, we can compute a maximum-cardinality matching \(M\) of \(G\) in \(O\bigl(\sqrt{n}m\bigr)\) time. As observed before, no vertex in a vertex cover of \(G\) can match more than one edge in \(M\). Thus, every vertex cover of \(G\) has size at least \(|M|\). For most graphs, this inequality is strict. For example, \(K_3\) has a maximum matching of size \(1\) and a minimum vertex cover of size \(2\). A classical result in graph theory is König's theorem, which states that, for bipartite graphs, this inequality is an equality: The minimum vertex cover of a bipartite graph \(G\) has the same size as a maximum matching of \(G\), another classical example of duality. Its proof immediately leads to an efficient algorithm for constructing a vertex cover of size \(|M|\) from a maximum matching \(M\):

Let \(U' \subseteq U\) be the set of all vertices in \(U\) not matched by \(M\). Let \(Z\) be the set of vertices such that every vertex \(z \in Z\) is reachable from a vertex \(u \in U'\) via an alternating path. We discussed in the proof of Lemma 7.11 how to compute this set \(Z\) in \(O(n + m)\) time once \(M\) is given. Let \(C = (U \setminus Z) \cup (W \cap Z)\). We claim that \(C\) is a vertex cover of \(G\) of size \(|M|\). To prove that \(|C| = |M|\), we prove that every vertex in \(C\) is matched and that every edge in \(M\) has exactly one endpoint in \(C\).

To see that all vertices in \(C\) are matched by \(M\), observe that \(Z \supseteq U'\), so all vertices in \(U \setminus Z\) are matched. Every vertex \(w \in W \cap Z\) is reachable from some vertex \(u' \in U'\) via an alternating path \(P\) because \(w \in Z\). If \(w\) is unmatched, then \(P\) is an alternating path between two unmatched vertices because \(u' \in U'\) is unmatched by definition. Thus, \(P\) is an augmenting path with respect to \(M\), a contradiction because \(M\) is a maximum matching.

Next observe that if \(w \in W \cap Z\), then the other endpoint \(u \in U\) of the edge \((u, w) \in M\) also belongs to \(Z\). Indeed, since the path \(P\) from a vertex \(u' \in U'\) to \(w\) must have an odd number of edges and its first edge is unmatched, its last edge is also unmatched. Thus, appending the edge \((u, w)\) to the end of \(P\) produces an alternating path from \(u'\) to \(u\). This shows that an edge \((u, w) \in M\) whose endpoint \(w \in W\) is in \(C\) has its other endpoint \(u\) in \(Z\). Since \((U \cap Z) \cap C = \emptyset\), this shows that \(u \notin C\). In other words, every edge in \(M\) has at most one of its endpoints in \(C\). Since every vertex in \(C\) is an endpoint of an edge in \(M\), this shows that \(|C| \le |M|\). Next we show that \(C\) is a vertex cover of \(G\), which implies that \(|C| \ge |M|\). Thus, \(|C| = |M|\).

To show that \(C\) is a vertex cover of \(G\), consider an arbitrary edge \((u, w)\) with \(u \in U\) and \(w \in W\). This edge is covered by \(C\) unless \(w \notin Z\) and \(u \in Z\). So assume that \(u \in Z\). Then there exists an alternating path \(P\) from some vertex \(u' \in U'\) to \(u\). Since \(u, u' \in U\), this path has even length.

If \(P\) has no edge at all, then \(u = u'\) and thus every neighbour of \(u\) is reachable from \(U'\) via an alternating path. This shows that \(w \in Z\). If \(P\) has at least two edges, then observe that \(u' \in U'\) implies that the first edge in \(P\) is unmatched and, thus, the last edge in \(P\) is matched. Thus, if \((u, w) \in M\), then \((u, w)\) is the last edge of \(P\) and \(w \in Z\). If \((u, w) \notin M\), then we obtain an alternating path from \(u'\) to \(w\) by appending the edge \((u, w)\) to \(P\). Thus, once again, \(w \in Z\). This shows that every vertex \(u \in U \cap Z\) has all its neighbours in \(W \cap Z\), that is, every edge \((u, w)\) in \(G\) is covered by \(C\). ▨

Using Lemma 15.19, we can construct a problem kernel of size at most \(2k\) for any vertex cover instance \((G, k)\). We start by constructing an auxiliary bipartite graph \(B\) with vertex set \(V \cup V'\), where \(V'\) contains a vertex \(v'\) corresponding to each vertex \(v \in V\). The edge set of \(B\) is \(E_B = \bigl\{ \bigl(x, y'\bigr), \bigl(y, x'\bigr) \mid (x, y) \in E \bigr\}\). This construction is illustrated in Figure 15.6.

Figure 15.6: Coming soon!

Using Lemma 15.19, we compute a minimum vertex cover \(C_B\) of \(B\). We now partition the vertex set \(V\) of \(G\) into three subsets \(V_0\), \(V_1\), and \(V_2\) where

\[V_i = \bigl\{ v \in V \mid \bigl|C_B \cap \bigl\{v, v'\bigr\}\bigr| = i \bigr\}.\]

The following lemma now shows that \((G[V_1], k - |V_2|)\) is a problem kernel of size at most \(2k\).

Lemma 15.20: A graph \(G\) has a vertex cover of size at most \(k\) if and only if \(|V_1| \le 2k\) and \(G[V_1]\) has a vertex cover of size at most \(k - |V_2|\).

Proof: First consider any vertex cover \(C\) of \(G\) of size at most \(k\). Then the set \(C_B' = \{ v, v' \mid v \in C \}\) is a vertex cover of \(B\) of size at most \(2k\) because for every edge \((x, y') \in B\) corresponding to an edge \((x, y) \in G\), at least one of \(x\) and \(y\) belongs to \(C\) and thus \(x\) or \(y'\) belongs to \(C_B'\). Thus, since \(C_B\) is a minimum vertex cover of \(B\), we have \(|C_B| \le |C_B'| \le 2k\). Since every vertex \(v \in V_1\) satisfies \(v \in C_B\) or \(v' \in C_B\), this shows that \(|V_1| \le 2k\).

Next assume that \(G[V_1]\) has a vertex cover \(C'\) of size at most \(k - |V_2|\). Then note that the set \(C = C' \cup V_2\) has size \(|C'| + |V_2| \le k - |V_2| + |V_2| = k\). Thus, we need to prove that \(C\) is a vertex cover of \(G\). Consider an edge \((u, v) \in G\). If \(u, v \in V_1\), then \((u, v)\) is an edge of \(G[V_1]\) and is thus covered by \(C' \subseteq C\). If w.l.o.g. \(u \in V_2\), then \((u, v)\) is covered by \(V_2 \subseteq C\). If neither of these two cases applies, then w.l.o.g. \(u \in V_0\) and \(v \in V_0 \cup V_1\). Since \(u \in V_0\), we have \(u, u' \notin C_B\). Since \(v \notin V_2\), we have \(v \notin C_B\) or \(v' \notin C_B\). If \(v \notin C_B\), then \(C_B\) does not cover the edge \((u', v) \in E_B\). If \(v' \notin C_B\), then \(C_B\) does not cover the edge \((u, v') \in E_B\). In both cases, we obtain a contradiction. Thus, \(C = C' \cup V_2\) is a vertex cover of \(G\).

To prove that \(G[V_1]\) has a vertex cover of size at most \(k - |V_2|\) if \(G\) has a vertex cover of size at most \(k\), it suffices to prove that \(G\) has a vertex cover \(C\) of size at most \(k\) such that \(V_2 \subseteq C\). Indeed, since \(C\) is a vertex cover of \(G\), \(C \cap V_1\) is a vertex cover of \(G[V_1]\). If \(V_2 \subseteq C\), then its size is \(|C \cap V_1| \le |C| - |V_2| \le k - |V_2|\).

So consider an arbitrary vertex cover \(C\) of \(G\) of size at most \(k\). We use \(C\) to construct a vertex cover \(C' \supseteq V_2\) of \(G\) of size \(|C'| \le |C| \le k\). For \(i \in \{0, 1, 2\}\), let \(C_i = V_i \cap C\) and \(\bar C_i = V_i \setminus C\). Then \(C' = C_1 \cup V_2\). Since \(C\) is a vertex cover of \(G\) and \(C_1 = C \cap V_1\), \(C_1\) is a vertex cover of \(G[V_1]\). As shown above, this implies that \(C' = C_1 \cup V_2\) is indeed a vertex cover of \(G\). It remains to show that \(|C'| \le |C|\).

Let \(V_2' = \{ v' \in V' \mid v \in V_2\}\), \(C_2' = \{ v' \in V' \mid v \in C_2 \}\), and \(C'_B = \bigl(V \setminus \bar C_0\bigr) \cup C_2'\). \(C'_B\) is a vertex cover of \(B\). Indeed, for any edge \((u, v') \in E_B\), if \(u \notin \bar C_0\), then \(u \in V \setminus \bar C_0 \subseteq C'_B\). If \(u \in \bar C_0\), then \(u \in V_0\), that is, \(u, u' \notin C_B\). Thus, \(v, v' \in C_B\) because \(C_B\) covers the two edges \((u, v')\) and \((u', v)\). This shows that \(v \in V_2\). Similarly, \(u \in \bar C_0\) implies that \(u \notin C\). Thus, since \(C\) covers the edge \((u, v)\), \(v \in C\), that is, \(v \in C_2 = C \cap V_2\). By the definition of \(C_2'\), this shows that \(v' \in C_2' \subseteq C'_B\).

Since \(C_B'\) is a vertex cover of \(B\) and \(C_B\) is a minimum vertex cover of \(B\), we have \(|C_B| \le |C_B'|\). We are now ready to prove that \(|C'| \le |C|\):

\[\begin{aligned} |V_1| + 2|V_2| &= |V_1 \cup V_2 \cup V_2'|\\ &= |C_B|\\ &\le |C_B'|\\ &= |V \setminus \bar C_0| + |C_2'|\\ &= |V_2 \cup V_1 \cup V_0 \setminus (V_0 \setminus C_0)| + |C_2|\\ &= |V_1| + |V_2| + |C_0| + |C_2|\\ |V_2| &\le |C_0| + |C_2|\\ &= |C_0| + |C_2| + |C_1| - |C_1|\\ &= |C| - |C_1|\\ |C_1| + |V_2| &\le |C|. \end{aligned}\]

Since \(C' = C_1 \cup V_2\), its size is \(|C'| = |C_1| + |V_2| \le |C|\). ▨