Exact search, limits and unresolved answers
What this concept is
Exhaustive search over vertex subsets in increasing size returns an exact minimum once it finds a cover: all smaller subsets were tested. It uses exponential work; a teaching limit controls admissible input sizes rather than changing the theorem.
Why it matters here
“Not solved within budget” is a different outcome from infeasible. Production interfaces need to preserve that distinction when resource limits interrupt a search.
Concrete example
The lab exact solver accepts at most 12 vertices and rejects larger inputs. It never silently substitutes a heuristic. There are at most 2^n subsets; straightforward verification costs O(n+m) per candidate. This yields a conservative O(2^n(n+m)) bound, plus normalization. For any valid graph, all vertices form a cover, so failure to find one indicates an implementation defect.
Common confusion / misconception
The size guard is a local teaching choice, not a universal safe threshold or complexity lower bound. Observed fast runs on stars do not establish polynomial-time behavior.
How to use it
A parameterized alternative branches on an uncovered edge (u,v): any size-k cover must contain u or v. Delete the chosen vertex’s incident edges and decrement k in each branch. This gives a search tree of depth at most k with at most 2^k leaves and polynomial work per node. It can help when k is small, but is not polynomial in unrestricted k. Implementing this optimization is optional; proving its branching rule is required.
Check yourself
Why must at least one endpoint of an uncovered edge belong to every cover? Why is decrementing k essential to termination?
Mini drill or application
Distinguish three claims: a size-3 cover was found; exhaustive search proved none of size≤3 exists; search stopped before finishing. Describe the evidence each result needs.
Read this only if stuck
Use Erickson’s Algorithms and lecture notes for reductions and hardness, and the selective reading guide for the matching approximation. Full-book reading is not required.