Min Vertex Cover
The Dual of Independent Set
A vertex cover is a set of nodes such that every edge in the tree has at least one endpoint in the set. You want the smallest such set.
Edges: (1,2), (1,3), (2,4), (2,5), (3,6). You need to pick nodes so every edge is "covered."
One valid cover: {2, 3}. Edge (1,2) is covered by 2. Edge (1,3) is covered by 3. Edge (2,4) is covered by 2. Edge (2,5) is covered by 2. Edge (3,6) is covered by 3. That's only 2 nodes — but does it work? Edge (2,4): 2 is in the set. Edge (2,5): 2 is in the set. Yes, {2, 3} covers everything.
But can we do it with fewer? With just {2}? Then edge (1,3) has neither 1 nor 3 selected. No good.
Like max independent set, this is NP-hard on general graphs. On trees, one postorder pass.
The Duality
Here's something that connects this lesson to the last one: on any graph, a set \(S\) is an independent set if and only if \(V \setminus S\) (all other nodes) is a vertex cover.
Think about why. If \(S\) is independent, no edge has both endpoints in \(S\). So every edge has at least one endpoint outside \(S\) — which is exactly what "vertex cover" means for \(V \setminus S\).
This gives us a direct relationship:
You already know how to compute max independent set. So you could just compute \(n - \text{MIS}\) and be done. But it's worth seeing the DP directly — the recurrence is different, and you'll need it for problems where the duality doesn't apply cleanly.
The DP
Two states per node, just like before:
- \(\text{dp}[\text{node}][0]\) = minimum cover size if this node is NOT in the cover
- \(\text{dp}[\text{node}][1]\) = minimum cover size if this node IS in the cover
Not in cover: The edge from this node to each child must still be covered. Since this node isn't in the cover, every child MUST be in the cover. No choice.
In cover: This node covers the edge to each child. So each child is free to be in or out — pick whichever is cheaper.
The answer is \(\min(\text{dp}[\text{root}][0],\ \text{dp}[\text{root}][1])\).
Compare this to independent set. In MIS, "take" forces children to be skipped. In vertex cover, "skip" forces children to be taken. The logic is mirrored — exactly as the duality predicts.
Full Trace
Process bottom-up. At each node, compute (notInCover, inCover).
| Node | Children | dp[child][0], dp[child][1] | notInCover (dp[node][0]) | inCover (dp[node][1]) |
|---|---|---|---|---|
| 4 | none | — | 0 | 1 |
| 5 | none | — | 0 | 1 |
| 6 | none | — | 0 | 1 |
| 2 | 4, 5 | (0,1), (0,1) | 1 + 1 = 2 | 1 + min(0,1) + min(0,1) = 1 |
| 3 | 6 | (0,1) | 1 | 1 + min(0,1) = 1 |
| 1 | 2, 3 | (2,1), (1,1) | 1 + 1 = 2 | 1 + min(2,1) + min(1,1) = 3 |
Answer: \(\min(2, 3) = 2\).
Which nodes? Node 1 is NOT in the cover (we chose dp[1][0] = 2). That forces both children 2 and 3 into the cover. So the cover is {2, 3}.
Verify the duality: The tree has \(n = 6\) nodes. Max independent set on this tree? Nodes {1, 4, 5, 6} — all non-adjacent, size 4. And \(4 + 2 = 6 = n\). The duality holds.
The Code
pair<int, int> solve(TreeNode* root) {
if (!root) return {0, 0};
auto [leftOut, leftIn] = solve(root->left);
auto [rightOut, rightIn] = solve(root->right);
int notInCover = leftIn + rightIn;
int inCover = 1 + min(leftOut, leftIn) + min(rightOut, rightIn);
return {notInCover, inCover};
}
int minVertexCover(TreeNode* root) {
auto [outRoot, inRoot] = solve(root);
return min(outRoot, inRoot);
}
Complexity: \(O(n)\) time, \(O(h)\) space.
When to Use Which
You now have two ways to compute minimum vertex cover:
- Direct DP (this lesson): define states "in cover" / "not in cover," run postorder.
- Via duality: compute max independent set (Lesson 1), return \(n - \text{MIS}\).
Both are \(O(n)\). The direct DP is better when the problem asks for the actual cover (not just the size), because you can reconstruct which nodes are in the cover by tracing the DP decisions.
The include-exclude pattern keeps the same skeleton: two states per node, one postorder pass. Only the recurrence changes between problems.
Try It
The starter code has a minVertexCover function with a TODO.
Predict before running: What's the minimum vertex cover of a path of 4 nodes (1-2-3-4)? You need to cover edges (1,2), (2,3), (3,4). Picking {2, 4} covers all three? No — edge (3,4) needs 3 or 4. {2, 4} covers it via 4. Edge (2,3) needs 2 or 3. {2, 4} covers it via 2. Edge (1,2) via 2. So {2, 4} works — size 2.
Challenge: A star graph has a center node connected to \(k\) leaves. What's the minimum vertex cover? The center alone covers all \(k\) edges. Any cover without the center needs all \(k\) leaves. So the answer is \(\min(1, k) = 1\) for \(k \geq 1\).
Challenge 2: Modify the code to print which nodes are in the minimum cover, not just the size.
Edge Cases to Watch For
- Verify via duality: For any tree,
min_vertex_cover + max_independent_set = n. If your answer doesn't satisfy this, there's a bug. This is a useful sanity check that catches incorrect DP transitions.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| LC 968 — Binary Tree Cameras | leetcode.com/problems/binary-tree-cameras | Hard |
| SPOJ — PT07X Vertex Cover | spoj.com/problems/PT07X | Medium |
| CF 1354E — Graph Coloring (Cover variant) | codeforces.com/problemset/problem/1354/E | Hard |