Vertex Cover Problem
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.
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];}