Branching Algorithms for Vertex Cover

Branching on an Uncovered Edge

A vertex cover is a set of vertices that meets every edge. The decision question is whether a graph has a vertex cover of size at most a specified nonnegative integer \(k\). A useful recursive strategy is to select an uncovered edge \(uv\). Any vertex cover must contain \(u\), \(v\), or both, so the algorithm can explore two cases: include \(u\), or include \(v\). Each choice uses one unit of the available budget.

All graphs in this tutorial are finite and simple. For a graph \(G=(V,E)\), a vertex cover is a set \(C\subseteq V\) such that every edge has at least one endpoint in \(C\). A cover is not required to be minimum unless that is stated. The algorithm decides whether there is a cover \(C\) with \(|C|\le k\); it does not need to list every such cover.

In an implementation, each successful sequence of choices gives a cover: add each chosen endpoint to the selected set. Deleting that endpoint from the residual graph removes exactly the edges it covers. If the recursion reaches an edgeless residual graph without exceeding the budget, the selected vertices cover every original edge. It is important to test for a negative budget before accepting an edgeless graph: a sequence that has already selected \(k+1\) vertices is not a cover of size at most \(k\), even if its last choice happened to cover the final edge.

The order of the two branches does not affect whether the answer is correct. Choosing an edge is essential: branching on an arbitrary vertex without a reason that every valid cover must include it could omit valid covers from the search.

Why the Recursion Is Correct

Proof. We prove the claim by induction on \(|V(H)|+|E(H)|+\max(b,0)\), using the algorithm's recursive definition. If \(b<0\), no set has size at most \(b\), so returning “no” is correct. Suppose \(b\ge0\). If \(E(H)=\varnothing\), the empty set is a vertex cover of size \(0\le b\), so returning “yes” is correct.

Now suppose \(b\ge0\) and \(H\) has an edge \(uv\). If either recursive call returns “yes,” then, by the induction hypothesis, the corresponding smaller graph has a cover \(D\) of size at most \(b-1\). In the call on \(H-u\), the set \(D\cup\{u\}\) covers \(H\): every edge incident with \(u\) is covered by \(u\), and all other edges are present in \(H-u\) and covered by \(D\). Its size is at most \((b-1)+1=b\). The same argument applies to the call on \(H-v\). Thus a “yes” from either branch implies that \(H\) has a cover of size at most \(b\).

Conversely, suppose \(H\) has a cover \(C\) with \(|C|\le b\). Since \(uv\) is an edge, \(C\) contains \(u\) or \(v\). If \(u\in C\), then \(C\setminus\{u\}\) covers \(H-u\) and has size at most \(b-1\), so the induction hypothesis makes the \(u\)-branch return “yes.” If \(u\notin C\), then \(v\in C\); deleting \(v\) from \(C\) gives a cover of \(H-v\) of size at most \(b-1\), so the \(v\)-branch returns “yes.” Hence the algorithm returns “yes” whenever such a cover exists, proving both directions. \(\square\)

The induction applies to the recursive calls because deleting a vertex strictly reduces the number of vertices, and the budget also falls by one. In particular, every nonterminal call has smaller induction measure than its parent.

Bounding the Search Tree

Represent the recursion as a rooted tree of calls. Every call that branches has at most two children. If a call is at depth \(d\), where the root is at depth \(0\), its budget is \(k-d\): each step from parent to child has selected exactly one additional vertex and reduced the budget by one. A call at depth \(k+1\) has budget \(-1\), so it returns “no” without branching. A call at depth \(k\) has budget \(0\), but it may still have an uncovered edge and branch, creating calls at depth \(k+1\).

Proof. A call can branch only at depths \(0,1,\ldots,k\). Therefore the tree has height at most \(k+1\), since children of calls at depth \(k\) are at depth \(k+1\) and cannot branch. At depth \(i\), a binary tree has at most \(2^i\) calls. Summing this bound from depth \(0\) through depth \(k+1\) gives at most \(\sum_{i=0}^{k+1}2^i=2^{k+2}-1\) calls. A binary tree of height at most \(k+1\) has at most \(2^{k+1}\) leaves: extending any early-ending leaf down to depth \(k+1\) assigns it a distinct descendant position among the at most \(2^{k+1}\) positions at that depth. Thus the leaf bound also holds.

For the running time, a direct implementation can find an uncovered edge, construct the two smaller residual graphs and maintain the selected vertices using \(O(n+m)\) work per call. Multiplying by the call bound gives \(O((2^{k+2}-1)(n+m))\), which is \(O(2^k(n+m))\), since \(2^{k+2}=4\cdot2^k\). This is a bound on the decision algorithm; it does not assert that every input reaches the maximum-sized tree. \(\square\)

The depth-\(k+1\) calls matter even though none of them branches. For \(k=0\) and a graph consisting of one edge, the root branches into two calls with budget \(-1\). There are two leaves and three calls altogether. The general bounds give \(2^{0+1}=2\) leaves and \(2^{0+2}-1=3\) calls, matching this example.

Worked Traces and Practical Interpretation

The branch-and-bound argument is useful when the budget \(k\) is the parameter of interest. The graph may be large, but the search has at most \(2^{k+2}-1\) calls, multiplied by the work per call. In particular, for fixed \(k\), the direct running-time bound grows linearly with \(n+m\). This bound does not make the method practical for every large \(k\), because the exponential factor increases with the budget.

The earlier material on matching lower bounds gives a quick optional rejection test: if a graph contains more than \(k\) pairwise disjoint edges, no cover of size at most \(k\) can exist, since each of those edges requires a distinct selected endpoint. Such a test can be applied before branching, but it is not needed for the correctness or the stated worst-case bound of the basic algorithm.

Common Pitfall: Counting Only Through Depth \(k\)

A frequent counting error is to include calls only at depths \(0\) through \(k\), obtaining \(2^{k+1}-1\) calls and \(2^k\) leaves. This omits children created by calls at depth \(k\). Those children are at depth \(k+1\), have negative budget, and are terminal calls—but they still count. For \(k=0\) with one edge, the incorrect calculation would predict \(1\) call and \(1\) leaf, while the actual recursion makes the root call and two negative-budget children: \(3\) calls and \(2\) leaves. Summing through depth \(k+1\) gives the correct general bounds \(2^{k+2}-1\) calls and \(2^{k+1}\) leaves. The asymptotic running-time conclusion remains \(O(2^k(n+m))\); the exact count, however, must include those final calls.