How does shrinking a size-k vertex cover instance to an equivalent one whose size is bounded by k alone pay off?
answer
- shrink first, search afterwards
- same answer, smaller instance
- degree above the budget forces a choice
- at most k times k edges survive
- polynomial plus f(k), not multiplied
basics
~20 sIt moves the whole graph out of the expensive factor. Polynomial-time reduction rules return an equivalent instance of size bounded by k, so the exponential search afterwards runs on something the size of k squared, not on the graph.
solid answer
~50 s**Kernelization** is a polynomial-time pre-processing step that returns an *equivalent* instance - same yes-or-no answer - whose size is bounded by a function of `k` alone. For vertex cover, two rules do it: drop every vertex with no edges, and take any vertex of degree above `k` into the cover, decrementing `k`, because leaving it out would force all its neighbours in and blow the budget. When neither rule fires, every remaining vertex has degree at most `k`, so `k` chosen vertices can cover at most `k * k` edges; more edges than that and the answer is "no" without any search. What follows is the payoff: the exponential search runs on an instance of size about `k^2` rather than on `n`, so the cost becomes a polynomial in `n` plus a function of `k` alone.
code
pseudocode · 11 linesfunction kernelize(G, k):
repeat until no rule fires:
remove every vertex with no incident edge # covers nothing
if some vertex v has degree > k:
G <- G - v # v is in every
k <- k - 1 # cover of size <= k
if k < 0 or G has more than k * k edges:
return NO_INSTANCE # decided without search
return (G, k) # <= k*k edges remaingo deeper
The idea to hold on to is order of operations: clean the instance with cheap rules that cannot change the answer, and only then pay for the expensive search on what is left.
Explain why a vertex with more neighbours than the budget must be in the cover, and how that plus removing isolated vertices leaves at most the budget squared in edges.
Argue the payoff in cost terms: the shape moves from a function of the parameter multiplied by the input to one added to it, which makes the expensive stage's runtime independent of how large production data grows.
Treat reduction rules as contract, not optimisation: each needs a soundness argument, and together they should bound the instance by something the specification caps, so the exponential stage has a budgetable worst case.
## What a kernel is, precisely A **kernelization** for a parameterized problem is a polynomial-time algorithm that maps an instance `(G, k)` to an instance `(G', k')` such that: - `(G', k')` is a **yes** exactly when `(G, k)` is - equivalence, not approximation; - `|G'|` and `k'` are bounded by a function of `k` alone, with no reference to `n`; - the mapping itself runs in polynomial time in `n`. The second clause is the surprising one. Whatever the size of the conflict graph, the reduced instance is small in a way that only the configuration limit controls. The first clause is what makes it sound: the rules may *decide* parts of the answer, but they may never change it. ## The two rules, and why each is safe 1. **Isolated vertices go.** A vertex with no incident edge covers nothing, so no minimum cover needs it, and deleting it changes no answer. The budget is untouched. 2. **A vertex of degree above `k` goes into the cover.** Suppose a solution of size at most `k` omits it. Then every one of its more-than-`k` neighbours must be in the cover to handle the edges at that vertex, which already exceeds the budget. So *every* cover of size at most `k` contains it. Delete it with its incident edges and set the budget to `k - 1`. Note the asymmetry: rule 1 removes something no solution wanted; rule 2 removes something every solution wanted, and pays for it out of the budget. Both preserve the answer, which is the only property required. ## Why the leftover is quadratic Apply the rules until neither fires, and reason about what survives: 1. No vertex has degree above the current budget `k'`, or rule 2 would fire. 2. In a yes-instance the cover has at most `k'` vertices, and every edge is touched by one of them. 3. Each of those vertices touches at most `k'` edges, by step 1. 4. So a yes-instance has at most `k' * k'` edges. If more remain, answer "no" immediately. 5. Every surviving vertex has an edge, so at most `2 * k'^2` vertices remain. That is the **quadratic kernel**: an instance of `O(k^2)` edges obtained by a linear-ish pass over the graph. A sharper route through a linear-programming relaxation bounds the *vertex* count at `2k`, which is a refinement of the same idea rather than a contradiction of it - the edge count can still be quadratic in `k`. There is evidence that the quadratic bound on the kernel's encoded size cannot be pushed below `k^(2-e)` without an unlikely collapse in complexity theory, so this is close to the end of the road for this problem. ## What it buys | stage | before kernelization | after kernelization | |---|---|---| | what the search walks | the whole graph | about `k^2` edges | | cost of the search | `2^k` times a polynomial in `n` | `2^k` times a polynomial in `k` | | total shape | `f(k) * n^c` | `n^c + f(k)` | | effect of growing `n` | multiplies the exponential factor | changes only the pre-processing pass | The last row is the engineering payoff. Additively separating the polynomial and the exponential means a graph that grows tenfold costs tenfold *in the cheap part only*. It also makes the expensive part predictable: its cost depends on a number the specification caps, so it can be budgeted, timed out, or run on a fixed allocation. ## The general fact worth knowing For decidable parameterized problems, having a kernel and being fixed-parameter tractable are the **same property**: a kernel plus brute force on the kernel gives an FPT algorithm, and conversely an FPT algorithm can be turned into a kernel by running it for a bounded number of steps and, if it has not finished, emitting a small trivially-equivalent instance. The equivalence is a classification result; what distinguishes problems in practice is whether the kernel is *small* - linear, quadratic, or merely exponential in the parameter. ## How this shows up at work Reduction rules are exactly the "obvious simplifications" a careful engineer writes anyway: drop the entries that conflict with nothing; force in the entry that conflicts with everything. Kernelization is the discipline of proving that such a rule preserves the answer and that the rules together leave something provably small. The proof is what upgrades a pile of heuristics into a cost guarantee.
- Why can a reduction rule take a vertex into the cover rather than only deleting useless ones?Because soundness only requires the answer to be preserved. A vertex of degree above the budget is in every cover of size at most k, so committing it and decrementing the budget produces an instance with the same yes-or-no answer. A rule that merely looked plausible, without that argument, would not be a kernelization.
- What does it mean that having a kernel and being fixed-parameter tractable coincide?For decidable parameterized problems the two are equivalent: kernelize then brute-force the small instance gives an FPT algorithm, and an FPT algorithm can be truncated into a kernelization. The classification therefore says nothing about kernel size, which is where the practical difference lies - linear, quadratic, or exponential in the parameter.
- If more than k squared edges survive the rules, why can you answer immediately?Because every surviving vertex has degree at most k, so any k chosen vertices touch at most k times k edges. An instance with more edges than that cannot be covered within the budget, so it is a no-instance, established by counting rather than by search.
saying these in an interview costs you the question
- Thinks the pre-processing may change the answer if it helps the search
- Believes reduction only deletes things, never commits a vertex
- Says the reduced instance is bounded by a fraction of the input size
- Treats kernelization as an approximation or a heuristic prune
- Assumes any fixed-parameter tractable problem has a small kernel