16.1.1. A Simple Branching Algorithm for the Vertex Cover Problem

Branching algorithms are based on a very simple principle: For many problems, we can find a solution by making a sequence of elementary choices. For the vertex cover problem, for example, we make an elementary choice for every vertex: Do we include it in the vertex cover or not? The problem is that we do not know which combination of these choices leads to an optimal solution. Thus, naïve branching algorithms just try all combinations, one choice at a time. The advantage of constructing a solution one choice at a time is that earlier choices may influence choices made later and may allow us to ignore some combinations of choices if we can argue that we do not miss all optimal solutions as a result. This is exactly the strategy we use to obtain faster branching algorithms.

As the basis for obtaining faster branching algorithms for the vertex cover problem later in this section, let us discuss a slightly different branching algorithm from the one discussed in Section 8.3. Given a graph \(G\), a minimum vertex cover of \(G\) is easily found if \(G\) has no edges: The empty set is a valid vertex cover and a smaller vertex cover obviously does not exist. Otherwise, let \(v\) be an arbitrary vertex and let \(C\) be a vertex cover of \(G\). \(C\) must contain \(v\) or all of \(v\)'s neighbours: If \(v \notin C\), then the only way to cover all edges incident to \(v\) is to include all neighbours of \(v\) in \(C\). By the following lemma, an optimal vertex cover of \(G\) is the smaller of \(C_v \cup \{v\}\) and \(C_{N(v)} \cup N(v)\), where \(C_v\) is a minimum vertex cover of the graph \(G - v\) and \(C_{N(v)}\) is a minimum vertex cover of the graph \(G - N[v]\), where \(G - S = G[V \setminus S]\) for any subset \(S \subseteq V\) and \(G - v = G - \{v\}\). As usual, \(N(v)\) denotes the open neighbourhood of \(v\), that is, the set of all neighbours of \(v\). \(N[v] = N(v) \cup \{v\}\) is the closed neighbourhood of \(v\), which includes \(v\) and all its neighbours. This suggests the following strategy for finding a minimum vertex cover of \(G\): Recursively compute a minimum vertex cover \(C_v\) of \(G - v\) and a minimum vertex cover \(C_{N(v)}\) of \(G - N[v]\). Then output the smaller of the two sets \(C_v \cup \{v\}\) and \(C_{N(v)} \cup N(v)\) as a vertex cover of \(G\).

Lemma 16.1: Let \(v\) be any vertex of \(G\), let \(C_v\) be a minimum vertex cover of \(G - v\), and let \(C_{N(v)}\) be a minimum vertex cover of \(G - N[v]\). Then the smaller of \(C_v \cup \{v\}\) and \(C_{N(v)} \cup N(v)\) is a minimum vertex cover of \(G\).

Proof: Since \(C_v\) is a minimum vertex cover of \(G - v\), the only edges in \(G\) that it leaves uncovered are the edges incident to \(v\). Thus, the set \(C_v \cup \{v\}\) covers all edges in \(G\), that is, it is a vertex cover of \(G\). Similarly, since \(C_{N(v)}\) is a vertex cover of \(G - N[v]\), the only edges in \(G\) that it leaves uncovered are the edges incident to vertices in \(N[v]\). Each such edge is incident to a vertex in \(N(v)\), so \(C_{N(v)} \cup N(v)\) covers all edges in \(G\); it is a vertex cover of \(G\). This shows that the smaller of \(C_v \cup \{v\}\) and \(C_{N(v)} \cup N(v)\) is a vertex cover of \(G\). It remains to prove that there is no smaller vertex cover of \(G\).

Assume for the sake of contradiction that there exists a vertex cover \(C\) of \(G\) of size less than \(\min(|C_v \cup \{v\}|, |C_{N(v)} \cup N(v)|) = \min(|C_v| + 1, |C_{N(v)}| + |N(v)|)\).

If \(v \in C\), then observe that \(|C \setminus v| = |C| - 1 < |C_v|\). Moreover, \(C \setminus v\) is the restriction of \(C\) to the graph \(G - v\) and is thus a vertex cover of \(G - v\). This is a contradiction because \(C_v\) is a minimum vertex cover of \(G - v\).

If \(v \notin C\), then observe that all neighbours of \(v\) must be in \(C\). Thus, \(|C \setminus N[v]| = |C| - |N(v)| < |C_{N(v)}|\). Moreover, \(C \setminus N[v]\) is the restriction of \(C\) to the graph \(G - N[v]\) and is thus a vertex cover of \(G - N[v]\). This is a contradiction because \(C_{N(v)}\) is a minimum vertex cover of \(G - N[v]\). ▨