In a search for a vertex cover of size at most k, why does branching on both endpoints of one uncovered edge bound the work at 2^k?
answer
- every edge must be covered somehow
- two candidates, no third case
- each branch spends one unit of budget
- depth at most k, binary tree
- graph size stays out of the exponent
basics
~20 sEvery edge must be covered, so at least one of its two endpoints is in the cover: a forced two-way branch. Each branch spends one unit of the budget k, so the tree is at most k deep and has at most 2^k leaves.
solid answer
~40 sPick any edge whose endpoints are both still unchosen. A cover must contain `u` or `v` - there is no third option, which is what makes the branch **forced** rather than a guess. Recurse twice: once having taken `u` with budget `k - 1`, once having taken `v` with budget `k - 1`. Every step down the tree consumes one unit of budget, so the depth can never exceed `k`, and a binary tree of depth `k` has at most `2^k` leaves. The work at each node is a scan for an uncovered edge, polynomial in the graph. The total is therefore `2^k` times a polynomial in `n`, and the graph's size never touches the exponent - it only changes what each node costs.
code
pseudocode · 13 linesfunction has_cover(G, k):
if G has no edges:
return YES # everything is covered already
if k = 0:
return NO # budget spent, an edge survives
pick any edge (u, v) of G # both endpoints still unchosen
# a cover must contain u or v, so try each; "G - x" deletes x
# together with every edge touching x
if has_cover(G - u, k - 1) = YES:
return YES
return has_cover(G - v, k - 1)go deeper
Remember the forcing step: an edge has to be covered, so one of its two endpoints is in the answer. That one observation is what turns an open search into a two-way decision.
Explain why the recursion depth is the budget and not the graph: each descent commits one vertex and decrements k, so a binary tree of depth k caps the leaves at 2^k, with the graph appearing only in the per-node work.
Show the operational consequence - the search answers negatively with a proof rather than a timeout, and its cost tracks a capped quantity, so a graph that grows tenfold costs tenfold rather than exploding.
Frame it as where the team is allowed to spend exponential effort: on the capped conflict count, never on the catalogue. Then decide what happens if the cap is renegotiated upward, since the base of the exponent is the thing you would then have to buy down.
## The rule that forces the branch A **vertex cover** is a set of vertices touching every edge; the parameterized question is whether one of size at most `k` exists. In a conflict graph where an edge means two entries cannot coexist, a cover of size `k` is a set of at most `k` entries whose removal resolves every conflict. The search rests on a single observation. Take any edge `(u, v)` that no chosen vertex touches yet. Any cover must touch it, so it contains `u`, or `v`, or both. That is an exhaustive two-way case split, not a heuristic: the branch is **complete** (no cover is excluded) and **forced** (there is no third case). Completeness is why the search can answer "no" and be believed, which a greedy rule cannot do. ## Why the depth is capped by the budget and not by the graph 1. Entering a branch means committing one specific vertex to the cover. 2. Committing a vertex spends one unit of the remaining budget, so the child is solved with `k - 1`. 3. When the budget reaches zero and an uncovered edge remains, that branch is a dead end and returns "no". 4. Therefore no root-to-leaf path is longer than `k` steps, whatever the graph looks like. A binary tree of depth at most `k` has at most `2^k` leaves and fewer than `2^(k+1)` nodes. The graph's size enters only through the per-node work - finding an uncovered edge and deleting a vertex with its incident edges - which is polynomial. The total cost is `2^k` times a polynomial in `n`: the fixed-parameter shape, arrived at by construction rather than by analysis. | quantity | bounded by | depends on the graph? | |---|---|---| | branch depth | `k` | no | | branching factor | 2 | no | | leaves explored | `2^k` | no | | work per node | a polynomial in `n` | yes | ## What the search does and does not decide - It answers the **decision** question - does a cover of size at most `k` exist - and, on success, the recursion's own choices spell out one such cover. - It does **not** find the minimum cover directly. The usual route is to run it for increasing budgets until one succeeds; the cost is dominated by the last budget tried, because the budgets before it are geometrically cheaper. - A "no" is a proof, not a timeout: every case was tried. ## Sharpening the base The plain rule gives base 2. Published refinements case-split on the degree of the chosen vertex instead of taking an arbitrary edge - a degree-one vertex can always be resolved in favour of its neighbour, a high-degree vertex gives a very lopsided pair of branches - and these bring the base of the exponent below 1.3 while leaving the shape untouched. The lesson is that `2^k` is the *easy* bound, not a barrier: refining the branching rule attacks the base, refining the pre-processing attacks the value of `k` itself. ## Where the technique generalises, and where it stops Bounded search trees work when the problem offers a **small forced local structure**: a constant-size set of objects, one of which any solution must take. An edge gives two candidates; a hyperedge of size three gives three, and the same argument yields `3^k`. The technique collapses when no such local certificate exists - when knowing that a solution must contain "one of these few" is exactly what you cannot establish. That is the structural reason some parameterized problems resist every attempt at this shape, and it is why an interviewer who likes this question usually follows it with a problem where the trick fails. ## The engineering reading Stated without the vocabulary: *the conflicts are the only thing I have to guess about, and the specification caps them at a dozen; so I make at most a dozen forced yes-or-no decisions, each one halving my remaining freedom, and everything else is a pass over the graph.* Fitting the exponential to the capped quantity, and only to it, is the whole move.
- How does this search report the minimum cover size rather than just testing one budget?Run it for budget 0, 1, 2 and upward until a call succeeds. The failed attempts are geometrically cheaper than the successful one, so the total stays within a constant factor of the last search. That keeps the fixed-parameter shape, with the exponent tied to the answer's own size.
- What changes if the forced choice is among three objects instead of two?The branching factor becomes three and the bound becomes 3^k times a polynomial. The shape survives because the depth is still capped by the budget; only the base of the exponent grows. Any constant-size forced set gives the same argument with that constant as the base.
- Why is a greedy rule that repeatedly takes the highest-degree vertex not a substitute?Greedy commits without a case split, so it can miss every cover of size at most k and cannot justify a negative answer. Branching is exhaustive by construction: each step enumerates all ways a solution could touch that edge, so failure of the whole tree is a proof that no such cover exists.
It is twenty questions with a hard cap: every uncovered edge forces one yes-or-no about two named candidates, and you are allowed only k questions, so the interrogation can never run deeper than k however large the crowd in the room.
saying these in an interview costs you the question
- Says the branch depth grows with the number of vertices or edges
- Picks the higher-degree endpoint only, turning the branch into a guess
- Believes the search finds the minimum cover without repeating for larger budgets
- Thinks a failed search means the budget was wrong rather than proving no cover exists
- Claims the base 2 is a barrier that no refined branching can beat