Is there an NP-hard problem for which no Fixed-Parameter Tractable algorithm exists?

Question

Question

Is there an NP-hard problem for which we can add a parameter¹ to create a "natural"² parametrised problem for which no FPT algorithm exists?

1. The adding a parameter is needed because a NP-hard problem is normally just a question with a yes or no answer, if you want to limit some parameter you need to specify which one (even though something like $k$-Coloring might have an obvious one already), so with "specifying which parameter" one is limiting, one is "adding a parameter" to the problem. A more detailed description is included in the answer by Discrete Lizard.
2. I think Natural tries to exclude "trivial" parameterizations as I discuss in my first doubt in this question. Again a more detailed description is included in the answer by Discrete Lizard.

Doubt

0. It might be a trivial question as it perhaps is possible to always "stuff" the entire problem within the $f(k_1,k_2,..,k_m)$ part of the $f(k_1,k_2,..,k_m)n^c$ algorithm whilst setting $n=c'$ where $c'$ is an arbitrary constant. But perhaps the exact definition of FPT prevents such (ab)use of the concept of FPT.

Based on the comment of plop there indeed exists a trivial way to parameterize "any" (I assume any properly well-posed problem) problem, such that its parameterization is fpt. Those parameterizations use languages, which I assume to be what is described here. Such a "trivial" (in light of the question, not in light of difficulty) parameterization is intended to be ignored. So in the "words" of Discrete lizard: non-trivial parameter range(s) is(are) intended.

Answer 1

You have to be a bit careful with your question here. Note that an NP-hard problem is a decision problem, while FPT algorithms solve parametrized decision or search problems. So the question is a bit poorly formed. However, I think the question you probably intended to ask is:

Is there an NP-hard problem for which we can add a parameter¹ to create a "natural"² parametrised problem for which no FPT algorithm exists?

To which the answer is (unconditionally!) yes.

First of all, note that FPT, the class of problems that are solvable via a fixed parameter tractable algorithm, is a proper subset of XP, the class of "slice-wise polynomial" parameterized problems that can be solved by a polynomial-time algorithm if the parameter is fixed. In other words: $\mathrm{FPT} \subsetneq \mathrm{XP}$. (I must confess I'm not able to provide the proof by "standard diagonalization" which my source offers as the only justification. Perhaps a complexity theorist can help me out here)

Next, note that since at least one problem in XP cannot be solved by an FPT-algorithm, any XP-hard (in the sense of FPT-reductions) problem cannot be solved by an FPT-algorithm.

In the chapter "Provable Intractability: The Class XP" in Downey and Fellows' Fundamentals of Parameterized Complexity, they complete the argument by showing that what they call the PEBBLE GAME PROBLEM is XP-hard by "reinterpreting" a problem that is known to be at least PSPACE-hard (after "removing the parameter"), so certainly NP-hard. See there book chapter for more details.

---

Let me add that this result was very surprising to me as well, because for most practical problems, we require al sorts of conjectures ($P\neq NP$, ETH, SETH, 3-SUM, etc.), but this result is an actual fact that is independent of any conjecture.

---

_{1: To clarify, by "adding a parameter", I mean given an NP-hard problem $L\subseteq \Sigma^*$, define a parametrized problem $L'\subseteq \Sigma^* \times \mathbb{N}$ as $L':= \{\langle x, k\rangle \mid f(x)=k\}$ for some function $f : \Sigma^* \rightarrow \mathbb{N}$. This captures the intuitive idea that the additional parameter measures a property of the input.
2: The definition in 1 still allows all sorts of strange parameterizations with functions such as $f(x)\equiv 1$. Ideally, we'd require $f$ to measure something meaningful about the instance, but that seems hard to formalize. I couldn't think of any other formalisation that removes all "unnatural" parameterizations, either. So, I will instead copy the informal notion of "natural parameterized problems" from Downey and Fellows' book.}

Answer 2

I would say yes, but you need to accept the condition that P $\neq$ NP. Take $k$-Coloring, where we want to determine whether a graph can be colored with $k$ colors such that any two connected vertices do not have the same color. Clearly, we can reduce 3-Coloring to $k$-coloring.

Suppose $k$-Coloring is in FPT, then there exists an algorithm that solves this problem in $f(k) \cdot n^{O(1)}$. If we set $k = 3$, then we obtain a polynomial-time algorithm, and thus 3-Coloring can be solved in polynomial-time unless P $\neq$ NP. Obviously, if P $\neq$ NP, then there is no FPT algorithm for $k$-Coloring.

If you are looking for something more strictly in the sense that it absolutely cannot exist, then I am not sure whether such a problem has been found.

Answer 3

Perhaps another option, significantly weaker than STanja's solution and Discrete lizards solution, is assuming the exponential time hypothesis (ETH). ETH assumes $FPT \neq W[1]$ (Or just assume FPT $\neq$ W[1] directly).

So with FPT $\neq$ W[1] one assumes no (non-trivial) parameterization $K-D$ of a W[1]-hard problem is FPT. An example of a w[1] hard problem that is NP-hard* is $k-clique$, so there exists a w[1]-hard problem that is an NP-hard problem. Since (non-trivial) parameterization $K-D$ w[1]-hard problems are not (in) fpt with assumption FPT $\neq$ W[1], this means, any (non-trivial) parameterization $K-D$ of NP-hard problem $k-Clique$ is not FPT. That means, if FPT $\neq$ W[1], there exists a NP-hard problem that is not FPT.

• The decision problem ($k$)-clique is NP-complete, therefore, it is also NP-hard as the picture below shows:

Disclaimer

I did not come up with this argument, it is basically the comment of Discrete lizard, and it is almost like answering the question: "does $a$ exist?" with: "I assume that $b$ exists, oh there happens to be an $a$ that is in set $b$, and since I assumed $b$ exists, then there must also exist an $a$, so yes there exists an $a$. (as is also explained by Discrete lizard in the comments)