16.4.2. Vertex Cover*

We finish this chapter by returning to the vertex cover problem and describing an algorithm whose running time is \(O^*\bigl(1.33^k\bigr)\). This is very close to the currently best algorithm for this problem, whose running time is \(O^*\bigl(1.29^k\bigr)\) but achieves this using a significantly more complicated case analysis than the one we present here.

On an instance \((G,k)\), the algorithm discussed in this section exits if \(k < 0\) and answers "No" because there cannot exist any vertex cover of \(G\) of negative size.

If \(k \ge 0\) and \(G\) has no edges, then the algorithm exits and reports \(C = \emptyset\) as a minimum vertex cover of \(G\). As in previous vertex cover algorithms, this correct because there are no edges to be covered.

If \(k \ge 0\) and \(G\) has at least one edge, we remove all isolated vertices (because they cannot cover any edges) and distinguish 6 cases, applying the first case whose conditions are satisfied by the input instance \((G,k)\):

• Case 1: \(G\) is disconnected.
• Case 2: \(G\) has a degree-\(1\) vertex.
• Case 3: \(G\) has a vertex of degree at least \(5\).
• Case 4: \(G\) has a degree-\(2\) vertex.
• Case 5: \(G\) is a \(3\)-regular or \(4\)-regular graph. A graph is \(d\)-regular if every vertex has degree \(d\).
• Case 6: \(G\) has a degree-\(3\) vertex adjacent to a degree-\(4\) vertex.

Note that after removing all isolated vertices, all vertices in \(G\) have degree at least \(1\). If Cases 2, 3, and 4 do not apply, then all vertices in \(G\) have degree 3 or 4. If Case 5 does not apply either, this implies that \(G\) has at least one vertex of degree \(3\) and at least one vertex of degree \(4\). If Case 1 does not apply, then \(G\) is connected. Thus, if we choose an arbitrary degree-\(3\) vertex, an arbitrary degree-\(4\) vertex, and a path between these two vertices, then there must exist an edge on this path with a degree-\(3\) endpoint and a degree-\(4\) endpoints. This shows that if Cases 1–5 do not apply, then Case 6 must apply, that is, one of these six cases is applicable to any input instance \((G,k)\).