15.2.1. Vertex Cover

We show how to compute a problem kernel of size \(O\bigl(k^2\bigr)\) for the vertex cover problem using the following set of reduction rules:

Singleton reduction: If there exists a degree-\(0\) vertex, remove it.

Degree-1 reduction: If there exists a degree-\(1\) vertex \(u\) with neighbour \(v\), remove \(u\), \(v\), and all edges incident to \(v\) from \(G\) and decrease \(k\) by one.

High-degree reduction: If there exists a vertex \(u\) of degree at least \(k+1\), remove \(u\) and all edges incident to \(u\) from \(G\) and decrease \(k\) by one.

To prove that these are valid reduction rules, we need to prove that they are sound: Given a vertex cover instance \((G,k)\), the reduced instance \((G',k')\) produced by any of these rules if a yes-instance if and only if \((G,k)\) is a yes-instance.

Observation 15.2: Singleton reduction is sound: If \(u\) is a degree-\(0\) vertex in \(G\), then \(G\) has a vertex cover of size at most \(k\) if and only if \(G - u\) has a vertex cover of size at most \(k\).

Proof: Since \(G\) and \(G - u\) have the same edge set, any vertex cover \(C\) of \(G\) gives a vertex cover \(C \setminus \{u\}\) of \(G - u\) and any vertex cover \(C'\) of \(G - u\) is also a vertex cover of \(G\). Thus, \(G\) has a vertex cover of size at most \(k\) if and only if \(G - u\) does. ▨

Observation 15.3: Degree-1 reduction is sound: If \(u\) is a degree-\(1\) vertex in \(G\) with neighbour \(v\), then \(G\) has a vertex cover of size at most \(k\) if and only if \(G - \{u,v\}\) has a vertex cover of size at most \(k-1\).

Proof: For any vertex cover \(C\) of \(G\), \(C \cap (V \setminus \{u, v\}) = C \setminus \{u, v\}\) is a vertex cover of \(G - \{u,v\}\). Since \(C\) must cover the edge \((u, v)\), we have \(C \cap \{u, v\} \ne \emptyset\) and, thus, \(|C \setminus \{u, v\}| < |C|\). Thus, if \(C\) is a vertex cover of \(G\) of size at most \(k\), then \(C \setminus \{u, v\}\) is a vertex cover of \(G - \{u,v\}\) of size at most \(k - 1\).

For the reverse direction, consider any vertex cover \(C'\) of \(G - \{u,v\}\). Then \(C' \cup \{v\}\) is a vertex cover of \(G\). Indeed, every edge in \(G - \{u,v\}\) is covered by \(C'\). Every edge of \(G\) that is not in \(G - \{u,v\}\) is incident to \(v\) and is thus covered by \(v\). Thus, if \(C'\) is a vertex cover of \(G - \{u,v\}\) of size at most \(k-1\), then \(C' \cup \{v\}\) is a vertex cover of \(G\) of size at most \(k\). ▨

Observation 15.4: High-degree reduction is sound: If \(u\) has degree at least \(k+1\) in \(G\), then \(G\) has a vertex cover of size at most \(k\) if and only if \(G - u\) has a vertex cover of size at most \(k-1\).

Proof: Every edge of \(G\) that is not in \(G - u\) is incident to \(u\). Thus, if \(C'\) is a vertex cover of \(G - u\) of size at most \(k-1\), then \(C' \cup \{u\}\) is a vertex cover of \(G\) of size at most \(k\).

For a vertex cover \(C\) of \(G\), \(C \setminus \{u\}\) is a vertex cover of \(G - u\) because \(G - u\) is the subgraph of \(G\) induced by the vertex set \(V \setminus \{u\}\) and \(C \setminus \{u\} = C \cap (V \setminus \{u\})\). If \(|C| \le k\), then \(u\) has a neighbour \(v \notin C\) because \(u\) has at least \(k+1 > |C|\) neighbours. Since the edge \((u, v)\) must be covered by \(C\), this shows that \(u \in C\) and, thus, that \(|C \setminus {u}| \le k - 1\). Thus, \(G - u\) has a vertex cover of size at most \(k - 1\). ▨

To prove that these three reduction rules produce a problem kernel of size \(O\bigl(k^2\bigr)\), we prove that any fully reduced instance \((G,k)\) where \(G\) has more than \((k+1)k\) vertices or more than \(k^2\) edges is a no-instance.

Lemma 15.5: If \((G, k)\) is fully reduced with respect to the singleton reduction, the degree-\(1\) reduction, and the high-degree reduction and \(G\) has a vertex cover of size at most \(k\), then \(G\) has at most \(k(k+1)\) vertices and at most \(k^2\) edges.

Proof: Let \(C\) be a vertex cover of \(G\). Since \((G, k)\) is fully reduced with respect to the high-degree reduction, every vertex has degree at most \(k\) and thus every vertex in \(C\) covers at most \(k\) edges. Thus, \(|E| \le k|C| \le k^2\).

Since \(|C| \le k\), the bound \(|V| \le k(k+1)\) follows if \(|V \setminus C| \le k|C| \le k^2\). Since \((G, k)\) is fully reduced with respect to the singleton reduction, there are no isolated vertices, that is, every vertex \(u \in V \setminus C\) has an incident edge. We choose an arbitrary edge \((u, v)\) incident to \(u\) and place a pebble on this edge. After doing this for every vertex \(u \in V \setminus C\), the number of pebbles placed on edges equals the number of vertices in \(V \setminus C\). How many pebbles may an edge receive? Clearly no more than two, one for each endpoint. However, observe that, if \(u\) is a vertex in \(V \setminus C\) that places a pebble on the edge \((u, v)\), then \(u \notin C\) and thus \(v \in C\) because \(C\) is a vertex cover. Thus, \(v\) does not place any pebble on \((u, v)\) and every edge receives at most one pebble. Since the total number of pebbles equals the number of vertices in \(V \setminus C\) and we proved above that \(G\) has at most \(k|C| \le k^2\) edges, this shows that \(|V \setminus C| \le k^2\). ▨

Note that the proof of Lemma 15.5 does not use that there are no degree-\(1\) vertices. Thus, an algorithm that uses only the singleton reduction and the high-degree reduction suffices to obtain a quadratic kernel for the vertex cover problem. However, the degree-\(1\) reduction may further reduce the size of the kernel, and the parameter, in practice. Reducing the parameter may enable further applications of the high-degree reduction because more vertices may be considered to have high degree with respect to this reduced parameter than with respect to the original parameter.