Vertex Cover on a Tree

Problem

Given an undirected unweighted graph $G = (V,E)$ , a vertex cover is defined as a set of nodes $C$ where every edge is adjacent to at least one node in $C$.

A minimum vertex cover is a vertex cover with the minimum possible number of nodes.

In general, Minimum vertex cover is an NP-complete problem, i.e., there is no polynomial time algorithm unless $P = NP$.

However, there is an easy 2-approximation algorithm via matching (A 2-approximation means that your solution will be at most 2 times worse than the optimal solution).

We are solving an easier problem in this case: given an undirected unweighted tree, and a root of the tree $r$, we need to find the minimum vertex cover of the tree.

DP Solution

As always, let us follow our DP recipe:

1. Define subproblems (and base cases)

2. Identify optimal substructure

3. Solve problem using sub-problems

4. Write (pseudo)code

An initial attempt might try to store the size of the vertex cover of the subtree rooted at the node and use it to solve larger subproblems. But that alone is not sufficient because we wouldn’t know whether we are forced to include its parent or not unless we know whether the child is in the vertex cover or not - so this leads to 2 cases: node in vertex cover and node not in vertex cover. This is sufficient information to compute the vertex cover of the parent too.

Note that it is not sufficient alone to store merely the size of the vertex cover of the subtree rooted at that node for each node. We need to know whether that node itself is included or not. In particular, if the child is not included in the vertex cover of its subtree, the parent must be included (only then the edge connecting them can be adjacent to a node in the vertex cover). Moreover, even if a child is included in its vertex cover for the subtree, it may be reasonable to include the parent in case the parent has other children who are not included in their respective sub-vertex covers.

Define $S[v,0] =$ size of a vertex cover in subtree rooted at node $v$, if $v$ is NOT covered. Similarly, define $S[v,1] =$ size of a vertex cover in subtree rooted at node $v$, if $v$ IS covered. For example,

So, for each node you need to consider whether it is in the cover or not. Hence, there are $2V$ subproblems that we need to solve. (Note that the number of subproblems is NOT $2^V$- We are not considering it like “for each node, we can either include or not include. So, check all possible ways and pick the minimum that satisfies vertex cover property”. We are just looking at two possibilities for each node (INDEPENDENT of other nodes in the tree! we are not chaining the results so there’s no need to multiply the subproblems of all nodes together)

The base case is in case of leaves: $S[leaf, 0] = 0$ and $S[leaf, 1] = 1$.

After a bit of observation, you should realise that the recurrence relation is as follows:

1. $S[v,0] = S[w_1,1] + S[w_2,1] + S[w_3,1] + \dots + S[w_n, 1]$ where $v.children() = \{w_1, w_2, \dots, w_n\}$. In other words, if you don’t cover the node, you better make sure to cover all the children so that each edge between $v$ and its children is covered.

2. $S[v,1] = 1 + min(S[w_1,0],S[w_1,1]) + min(S[w_2,0],S[w_2,1]) + \dots + min(S[w_n,0], S[w_n,1])$. That is, if you are covering the parent, then it is not mandatory to cover its children but often it is optimal to cover some of the children too (depending on the lower subtrees). So, you take the minimum of the two to decide whether to cover each child or not.

Then our final answer is $min(S[root,0],S[root,1])$ - whether to cover the root or not.

Look how elegantly we realised that using subtrees as subproblems is the right way to go - the importance of identifying this overlapping subproblem cannot be overstated.

Pseudocode

int treeVertexCover(V){ // Assume tree is ordered from root-to-leaf
	int[][] S = new int[V.length][2]; // create memo table S
	for (int v=V.length-1; v>=0; v--){ // From the leaf to the root
		if (v.childList().size()==0) { // If v is a leaf...
	    S[v][0] = 0;
      S[v][1] = 1;
		}
		else{ // Calculate S from v’s children.
			int S[v][0] = 0; // not including node v
			int S[v][1] = 1; // including node v
			for (int w : V[v].childList()) {
				S[v][0] += S[w][1]; // you're forced to take the vertex cover that includes the child since you are not including v
				S[v][1] += Math.min(S[w][0], S[w][1]); // no constraint that you cannot include both adjacent nodes.
			}
		}
	}

	return Math.min(S[0][0], S[0][1]); // returns min at root
}

Running Time analysis

You’re looking at each edge exactly once and each node exactly twice (once when determining its own $S$ values, and once when trying to determine it’s parents $S$ value - except the root). So, the running time is $O(V+E)$. But observe that our input is a tree and hence, $E = V - 1$. Thus, running time is $O(V)$.

Alternatively, you can think like this.

There are $2V$ subproblems:

1. Each edge is explored once since each subproblem involves exploring children edges.

2. Hence, $\sum_{v \in V} degree(v) = O(E)$