Vertex Cover Problem

Hard

Problem

Find a smallest set of vertices such that every edge has at least one endpoint in the set. The problem is NP-hard in general: know the 2-approximation (take both ends of any uncovered edge) and the exact DP for trees.

Example 1

Input:  edges 0–1, 0–2, 1–3, 3–4, 4–5, 5–6
Output: e.g. {0, 3, 5} or {0, 3, 4, 6}

Also asked as: Vertex Cover Problem

Test cases

No automated tests for this problem yet. Use the examples above to check your output.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

This problem has no automated tests. Run executes your code and shows what it logs.

View solutionHide solution1 approach

1. Tree DP (exact) / 2-approximation (general graph)

Time O(n) tree / O(E) approxSpace O(n)

On a tree: dp[node][0/1] = min cover of the subtree when node is / is not in the cover; if a node is excluded, all children must be included. General graph: pick any uncovered edge, add BOTH endpoints to the cover — this is a 2-approximation (exact vertex cover is NP-hard).

function vertexCoverTree(node) {
if (!node) return [0, 0]; // [notInCover, inCover]
const L = vertexCoverTree(node.left);
const R = vertexCoverTree(node.right);
const notIn = L[1] + R[1]; // children must be covered
const inCover = 1 + Math.min(L[0], L[1]) + Math.min(R[0], R[1]);
return [notIn, inCover];
}
// answer: Math.min(...vertexCoverTree(root))
function approxVertexCover(n, edges) {
const used = new Set();
const covered = new Set();
for (const [u, v] of edges) {
if (covered.has(u) || covered.has(v)) continue;
used.add(u); used.add(v);
covered.add(u); covered.add(v);
}
return [...used];
}