Questions: Parameterized Complexity and Fixed-Parameter Tractability

Question 1

Vertex Cover is NP-hard in general. A researcher presents an FPT algorithm running in O(2^k · n). A colleague objects: 'It's NP-hard — you can't have an efficient algorithm for it.' What is the error in the colleague's objection?

• A. Vertex Cover is not actually NP-hard; the colleague is misinformed about its complexity
• B. FPT algorithms are polynomial-time; 2^k counts as polynomial when k is treated as a constant
• C. The FPT algorithm is not polynomial-time — it is polynomial in n but exponential in k. For small fixed k, it runs efficiently; for large k, it remains exponential. This does not contradict NP-hardness
• D. NP-hardness only applies to optimization problems; the decision version of Vertex Cover is easy

Answer: (C)

NP-hardness says no polynomial-time algorithm handles all instances. An FPT algorithm is not polynomial-time — it is f(k)·poly(n), where the superpolynomial factor is isolated in k. When k=15, for instance, 2^15 = 32,768 is a fixed constant and the algorithm runs essentially in O(n) — very practical even for million-node graphs. When k is unbounded (allowed to grow with n), the algorithm is no longer efficient. P=NP is not violated: FPT algorithms are efficient only when the parameter is small, not in general.

Question 2

A researcher proves that a parameterized problem is W[1]-hard for its natural parameter k. What does this imply under standard assumptions?

• A. The problem is undecidable — it has no algorithm at all
• B. No FPT algorithm exists; the problem cannot be solved in f(k)·poly(n) time
• C. The problem is easy when k is small, since W[1]-hardness only applies when k is large
• D. The problem can still be kernelized to an equivalent instance of size depending only on k

Answer: (B)

W[1]-hardness is the parameterized analog of NP-hardness. Under the standard assumption FPT ≠ W[1], no algorithm of the form f(k)·poly(n) exists. The problem is decidable (it has algorithms), but fixing k does not make it tractable — the exponent on n also grows with k. This separates problems like Vertex Cover (FPT) from k-Clique (W[1]-complete), where no FPT algorithm is believed to exist even though the problem itself is solvable.

Question 3

A problem that is NP-hard cannot be FPT, because an FPT algorithm would imply P = NP.

• T. True
• F. False

Answer: False

This is a common and important misconception. FPT means f(k)·poly(n), where f(k) can be exponential or worse. This is not a polynomial-time algorithm in the classical sense, which requires poly(n + k) without any separate parameter-dependent factor. P=NP would require polynomial time for all instances; an FPT algorithm is only efficient when k is small. Vertex Cover is both NP-hard and FPT — it has an O(2^k · n) algorithm. There is no contradiction.

Question 4

Kernelization can reduce any parameterized problem instance (x, k) to an equivalent instance (x', k') whose size is bounded by a function of k alone, making the original input size irrelevant for the subsequent computation.

• T. True
• F. False

Answer: True

This is exactly the definition of a kernel: a polynomial-time reduction of any instance (x, k) to an equivalent instance (x', k') where |x'| ≤ g(k) for some function g that depends only on k. After kernelization, the problem on the kernel can be solved by any algorithm — even brute force — since the kernel's size is bounded independently of the original n. For Vertex Cover, the classic kernel has at most 2k vertices, so any instance with k ≤ 50 reduces to a graph with at most 100 vertices before any exponential search begins.

Question 5

Explain why an FPT algorithm for an NP-hard problem does not imply P = NP.

Model answer: FPT means f(k)·poly(n), where f(k) can be exponential, factorial, or any computable function of k. This is not a polynomial-time algorithm: polynomial time in the classical sense means poly(|x|) with no additional parameter-dependent factor — equivalently, the running time must be bounded by a polynomial in the total input size alone. An FPT algorithm is efficient only when the parameter k is small. For instances with large k (say k grows with n), the FPT algorithm remains exponential and provides no polynomial-time guarantee. NP-hardness rules out poly(n) algorithms for all instances; FPT does not provide one — it shows that a specific structured subset of instances (those with small k) can be solved efficiently. No contradiction arises.

The parameterized complexity framework is useful precisely because NP-hardness is a worst-case result that hides enormous variation. FPT identifies the structured, tractable sub-cases without overturning the general hardness. This is why asking 'what is a natural small parameter?' is often the most practical response to an NP-hard problem in applications.