Questions: Fixed-Parameter Tractability (FPT)

Question 1

An algorithm solves a problem in time O(n^k), where k is the size of the solution being sought. Is this algorithm FPT with respect to parameter k?

• A. Yes — the running time is polynomial in n for any fixed value of k, which is exactly what FPT means
• B. No — FPT requires the exponent of n to be a constant independent of k; in O(n^k) the polynomial degree grows with k, so this is not FPT
• C. Yes — n^k is always faster than exponential time 2^n, so it qualifies as tractable for large inputs
• D. It depends on the specific problem — O(n^k) is FPT for some problems and not others

Answer: (B)

FPT requires time f(k) · n^c where c is a constant that does NOT depend on k. In O(n^k), the exponent of n is k itself — so the polynomial degree grows without bound as k increases. For k=20, this gives O(n^20), which is computationally infeasible for any realistic n. A genuine FPT algorithm isolates the dependency on k into a multiplicative factor — like O(2^k · n) — while keeping the n-dependence at a fixed polynomial degree. The confusion between 'polynomial in n for fixed k' and 'FPT' is one of the most common errors in parameterized complexity.

Question 2

Why does the branching algorithm for vertex cover (branching on any uncovered edge (u,v) and recursing with k−1) achieve FPT complexity?

• A. Because the graph has at most n vertices, limiting the total number of recursive calls to n regardless of k
• B. Because at each step we branch into two subproblems each with k decremented by 1, producing a search tree of depth k with at most 2^k leaves, each checkable in O(n) time — giving total cost O(2^k · n)
• C. Because vertex cover uses dynamic programming that avoids redundant subproblems, reducing the search space from exponential to polynomial
• D. Because vertex cover is actually easier than NP-complete in practice, and the branching algorithm simply exploits this hidden structure

Answer: (B)

The key insight: any valid vertex cover must include u or v (or both) from every uncovered edge. Branching into two subproblems — include u, or include v — each with k decremented by 1 gives a binary search tree of depth at most k (you can make at most k inclusion decisions). With branching factor 2 and depth k, there are at most 2^k leaves. Each leaf requires O(n) work to verify. Total: O(2^k · n) = f(k) · n^1. This is FPT because the exponent of n is the constant 1, independent of k.

Question 3

A problem that is NP-hard in general can still be FPT with respect to a carefully chosen parameter k, allowing efficient solutions when k is small.

• T. True
• F. False

Answer: True

True. This is the fundamental insight of parameterized complexity theory. NP-hardness is a worst-case statement over all possible inputs — it does not mean every instance is hard. FPT identifies structural parameters that, when small, make the problem tractable. Vertex cover is NP-complete in general (no polynomial algorithm in n alone is known) but FPT parameterized by solution size k, with an algorithm running in O(2^k · n) that is practical for small k. The difficulty is isolated in the parameter; the dependence on n remains polynomial.

Question 4

A problem is FPT with respect to parameter k if it can be solved in time O(n^k), because this running time is polynomial in n for any fixed value of k.

• T. True
• F. False

Answer: False

False. This is the most important distinction in FPT theory. FPT requires f(k) · n^c where c is a constant independent of k. In O(n^k), the exponent of n grows with k, so for k=50, you need O(n^50) — infeasible even for modest n. True FPT puts the k-dependence in a multiplicative factor (e.g., 2^k, k!, anything computable) while keeping n's exponent fixed. O(2^k · n) is FPT; O(n^k) is not. The class XP contains problems solvable in O(n^k) for fixed k, and XP properly contains FPT — they are distinct complexity classes.

Question 5

Explain the conceptual difference between an algorithm running in O(n^k) and one running in O(2^k · n), and why only the second is considered FPT.

Model answer: In O(n^k), the polynomial degree of n grows with k: for k=10 you need O(n^10), for k=20 you need O(n^20) — computationally infeasible for large n at any k beyond a handful. In O(2^k · n), the exponent of n is always 1 (a fixed constant), so the n-dependence is always linear; only the multiplicative factor 2^k grows with k. For k=20, this is about 10^6 · n — perfectly tractable for large n. FPT requires f(k) · n^c where c is a constant: O(2^k · n) satisfies this with c=1, f(k)=2^k, while O(n^k) fails because c=k grows with the parameter. The essential point is that FPT isolates the combinatorial hardness entirely into the parameter k, keeping the input-size dependence polynomial with a fixed, small degree.

This distinction matters practically: when inputs have k ≤ 20 or k ≤ 50, even a large constant 2^50 ≈ 10^15 is bounded and fixed, while n-polynomial with fixed exponent scales gracefully. O(n^k) provides no such benefit — as k grows, the algorithm becomes worse on large inputs in a way that cannot be bounded by fixing k 'once and for all'.