402. Vertex Cover Problem

Given an undirected graph with n vertices (0-indexed) and m edges, find the size of the smallest vertex cover - the smallest set of vertices such that every edge has at least one endpoint in the set.

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges. Each of the next m lines contains two space-separated integers u and v, an undirected edge. Output: Print a single integer - the size of the smallest vertex cover.

1 <= n <= 20

Vertex Cover is NP-hard in general graphs - the small constraint here (n<=20) is precisely why brute-force bitmask enumeration is both expected and entirely feasible, rather than a compromise; for larger n, only approximation algorithms (like a simple greedy 2-approximation) would be practical.

Find the smallest set of vertices such that every edge has at least one endpoint in that set. Brute force: This problem's very nature (n<=20) invites trying every one of the 2^n subsets directly - there isn't really a meaningfully 'slower' alternative distinct from this, since Vertex Cover is NP-hard in general and exact solutions at this scale rely on exhaustive (but still efficient-enough) search. Optimised: Since finding the true minimum vertex cover is NP-hard in general, and n is capped at a small 20, directly checking all 2^n subsets (with an O(m) edge-covering check each) is both CORRECT and computationally FEASIBLE at this scale - no cleverer polynomial algorithm exists for this NP-hard problem in general.

Recursively look for any edge (u, v) that isn't yet covered by the vertices chosen so far; if none remain, the current selection is a valid cover. Otherwise branch into two cases - include u in the cover, or include v in the cover - and recurse on each with the budget (remaining allowed cover size) reduced by one, pruning immediately whenever the budget hits zero before all edges are covered. Because this only ever branches on vertices touching an actually-uncovered edge (using bitmask adjacency for O(1) coverage checks) rather than blindly enumerating all subsets, it explores a much smaller search tree in practice - the classic fixed-parameter-tractable algorithm for vertex cover, bounded by 2^k rather than 2^n once the answer size k is small. Time: O(2^k * (n + m)) Space: O(n + m)

Instead of checking all 2^n subsets in arbitrary order, iterate the target cover size k = 0, 1, 2, ... and, for each k, generate only the C(n, k) subsets of exactly that size (checking each with a precomputed per-vertex adjacency bitmask so an edge-coverage check is a fast bitwise OR), stopping as soon as any size-k subset is found to be a valid cover - that k is the answer. Because the true minimum vertex cover is usually much smaller than n/2, this typically terminates after examining far fewer subsets than the full 2^n brute-force sweep, even though its worst case is the same order. Time: O(sum_{i=0}^{k} C(n,i) * m) in practice Space: O(n)

Enumerate every one of the 2^n possible subsets of vertices (e.g. via bitmasking), and for each subset check all m edges to verify that every edge has at least one endpoint in the subset; among all subsets that qualify as a valid vertex cover, keep the smallest size found. This checks every possibility so it's guaranteed correct, but examining all 2^n subsets and re-validating all m edges for each is very expensive even for n as small as 20. Time: O(2^n * m) Space: O(n)

1. With n this small (<=20), try every possible SUBSET of vertices, represented as a bitmask from 0 to 2^n - 1. 2. A subset COVERS every edge if, for each edge (u,v), AT LEAST ONE of u or v is set in the subset's bitmask - check every edge for every candidate subset. 3. Track the SMALLEST covering subset's size found across all 2^n candidates.

Time: O(2^n * m) - checking all 2^n subsets, each requiring an O(m) pass over the edges to verify coverage. Space: O(1) extra space beyond a single bitmask variable per candidate subset checked.

a graph with no edges (m = 0, answer 0), a complete graph, and n at its maximum of 20 to confirm the 2^n subset search stays feasible.

Be ready to mention the well-known relationship between vertex cover and independent set: a vertex cover's COMPLEMENT is always an independent set, so minimum vertex cover size = n minus MAXIMUM independent set size - useful for cross-verification, though it doesn't change the fundamentally exponential nature of finding either one exactly.