Why does a solver costing 2^k times n stay workable as the graph grows, when n^k with the same conflict count k does not?
answer
- exponential in what, exactly
- the parameter, not the input
- f(k) multiplied by a fixed power
- the degree must not grow with k
- FPT inside XP, strictly
basics
~20 sThe exponent's home decides it. In 2^k times n only the small conflict count k sits in an exponent, so a bigger graph costs a linear factor more. In n^k the graph itself is raised to k, so growth is fatal.
solid answer
~40 sBoth costs are exponential in something, but not in the same thing. `f(k) * n^c`, with `c` a constant that does not depend on `k`, is exactly what **fixed-parameter tractable** means: the explosion is quarantined inside a factor only the parameter controls, so doubling the graph doubles the work. `n^k` is merely **XP** - polynomial for each fixed `k`, but the *degree* of that polynomial grows with `k`, so every extra conflicting entry multiplies the whole graph back in. With `k = 12` and `n = 100,000`, `2^k * n` is about `4.1 * 10^8` steps and `n^k` is about `10^60`. So the useful interview question is never "is it exponential?" but "exponential in what, and does the specification bound that thing?"
go deeper
Take away that "exponential" is not one thing. Ask what sits in the exponent: the whole input, or a small count that some rule caps. That question alone separates a workable cost from a hopeless one.
Be able to state the shape: a function of the parameter multiplied by the input raised to a constant power, the constant independent of the parameter. Then contrast it with an input raised to the parameter, where growth attacks the exponent.
Show that you check what bounds the parameter in the real system before trusting the cost model, and that you know an FPT factor can still be too large to run when the function of the parameter is left unnamed.
Own which parameter the architecture is allowed to depend on, and write down what the system does on the day an input pushes that parameter past its assumed cap. That contingency, not the asymptotic, is the decision a lead is accountable for.
## What a parameterized cost claims A **parameterized problem** is an ordinary yes-or-no problem plus a declared **parameter** `k`: a number attached to the input that is expected to stay small even when the input does not. Take a dependency graph whose vertices are entries and whose edges are pairwise conflicts. The graph may grow without limit, but a configuration limit caps the conflicting entries at, say, a dozen. Here `n` is the size of the graph and `k` is that cap. A parameterized problem is **fixed-parameter tractable (FPT)** when some algorithm decides it in `f(k) * n^c` where: - `n` is the input size and `f` is *any* computable function of `k` alone, however brutal it is; - `c` is a **constant that does not depend on `k`** - this is the load-bearing clause, not a technicality; - the two factors *multiply*, so the parameter and the input size never meet inside one exponent. A cost of `n^k` meets none of that. Fix `k` and it is a polynomial, so it is not exponential in the usual sense; but the degree of that polynomial is `k`. Problems solvable in `n^f(k)` form the class **XP**, and `FPT` sits strictly inside `XP` - that separation is proven, unlike most questions in this area. ## Why the home of the exponent decides everything | | `2^k * n` (FPT shape) | `n^k` (XP shape) | |---|---|---| | input grows 10x | cost grows 10x | cost grows by a factor of `10^k` | | parameter rises by 1 | cost doubles | cost multiplies by the whole of `n` | | `k = 12`, `n = 100,000` | about `4.1 * 10^8` steps | about `10^60` steps | | what must stay small | only `k` | `k` and `n` together | The bottom row is the point. An FPT cost lets you scale the system: the graph can grow by orders of magnitude and the bill grows linearly, because the expensive factor never learned about `n`. An XP cost couples the two, so the only way to stay inside budget is to keep the input small as well - and if you could do that, the problem was not really hard. ## The arithmetic, once With `k = 12`, `2^k` is `4096`. Against a graph of `100,000` edges that is roughly `4.1 * 10^8` elementary steps: heavy, but a machine finishes it. The same instance under `n^k` is `(10^5)^12 = 10^60`, a number with no operational meaning. Grow the graph tenfold and the first figure becomes `4.1 * 10^9` while the second becomes `10^72`. Nothing about `k` changed in either case; only the exponent's tenant differs. ## What may serve as the parameter The parameter is a modelling decision, not a property handed to you. 1. **The size of the answer** - the number of entries you are allowed to pin or remove. This is the usual first choice. 2. **A structural measure of the input**, such as **treewidth**: how far the graph is from being a tree. Many graph problems that are hard in general run in `f(w) * n` on graphs of width at most `w`. 3. **A cap the specification already enforces** - a maximum number of conflicting entries, of distinct categories, of nesting levels. 4. **A quantity the domain bounds physically**, such as the number of dimensions or the number of replicas. A parameter is only useful if something outside the algorithm keeps it small. "`k` is usually small in our data" is an observation; "`k` cannot exceed twelve because the format forbids a thirteenth" is a guarantee. ## Three traps - **`f(k)` can be monstrous and the result still counts as FPT.** Meta-theorems that cover whole families of problems sometimes produce towers of exponentials. FPT is a statement about *shape*, not about speed; always ask for the actual `f`. - **A constant-degree polynomial can still hurt.** `f(k) * n^3` is FPT, and on a large graph the cubic term, not the exponential one, is what times out. - **"Exponential" as a verdict is lazy.** Many shipped systems run happily on a `2^k` factor; many stall on a quadratic one. Name what is in the exponent before you reject a design. ## Saying it out loud A good answer converts the cost into a sentence about the system: *the hard part of this is capped by a limit in the spec, so I pay a fixed multiplier for that limit and then walk the graph once; if the limit is ever raised, the multiplier doubles per unit and the walk does not change.* That sentence is FPT, stated without the vocabulary, and it is what the question is really testing.
- Is the gap between FPT and XP an open question, like P versus NP?No. FPT is contained in XP and the containment is known to be strict, by a diagonalisation argument of the same family as the time hierarchy theorem. What is open is whether FPT equals W[1], the class that captures clique-like parameterized problems. Mixing those two up is a common slip: one separation is settled, the other is not.
- Does the parameter have to be the size of the solution?No. Any measurable feature of the input can be the parameter: a structural width such as treewidth, the maximum degree, the number of distinct values, the nesting depth of a document. Choosing a parameter that something real keeps small is most of the skill; the algorithm design follows the choice.
- If f(k) is a tower of exponentials, is the problem still fixed-parameter tractable?By the definition, yes - the classification only requires `f` to be computable and the polynomial's degree to be constant. Practically, no: such results are usually classification statements rather than runnable algorithms. Always separate "this problem is FPT" from "here is an algorithm I would deploy".
saying these in an interview costs you the question
- Calls any cost with 2^k in it exponential and therefore unusable
- Treats n^k as fixed-parameter tractable because k is fixed
- Thinks FPT removes the exponential rather than confining it to the parameter
- Assumes the parameter must always be the size of the answer
- Claims the parameter is small without naming what bounds it
- Assumes a small f(k) is implied once a problem is called FPT