1
$\begingroup$

Question

Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 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

  1. 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.

$\endgroup$
4
  • 1
    $\begingroup$ FPT talks about parametrized problems, while NP-hard talks about decision problems. There is a trivial way to parametrize any problem, not just NP-hard ones, such that the resulting parametrized problem is in FPT. Given a language $L$ over the alphabet $\Sigma$, we define $L'\subset \Sigma\times\mathbb{N}$ by $L'=\{(x,n)\in L\times\mathbb{N}\mid n=|x|\}$. On the other extreme, any decision problem that is not in $P$ has a parametrization for which the resulting parametrized problem is not in FPT. Define $L'=\{(x,1)\mid x\in L\}$. $\endgroup$ – plop Sep 3 '20 at 20:14
  • $\begingroup$ @plop I think these trivial examples (where the language has a finite range for the parameter) are usually implicitly ignored in the context of FPT, but it can be good to edit the question to mention whether a non-trivial parameter range is intended. $\endgroup$ – Discrete lizard Sep 3 '20 at 21:29
  • $\begingroup$ @Discretelizard See the comment below about how the condition of the finiteness of the range of the parameter is not what is crucial to choosing a parametrization such that the problem falls out of FPT. My comment above is to note that what is interesting is when the problems come already with a parametrization. $\endgroup$ – plop Sep 3 '20 at 21:46
  • $\begingroup$ @Discretelizard Well, it is also interesting when the problem doesn't come with a parametrization and one finds a parametrization that is both meaningful for the problem (whatever that means in each case) and the instances corresponding for each value of the parameter can be solved efficiently. $\endgroup$ – plop Sep 3 '20 at 21:55
6
$\begingroup$

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 parameter1 to create a "natural"2 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.

$\endgroup$
7
  • 1
    $\begingroup$ When you get to choose the parametrization, there is a trivial parametrization that you can use. Assume that $L$ is a decision problem that is not in $P$, then the parametrized problem $L'=\{(x,1)\mid x\in L\}$ cannot be in FPT. Otherwise it could be decided in $f(1)|x|^{O(1)}$, for some function $f$. But $f(1)$ is a constant. So, this would imply that $L$ can be decided in polynomial time. Now take $L$ any NP-hard problem that is not in P, like the halting problem, for example. In this parametrization the parameter does nothing. $\endgroup$ – plop Sep 3 '20 at 20:55
  • $\begingroup$ @plop Usually, when talking about parametrized problems in the context of FPT, the range of the parameter is (often implicitely) required to be a non-finite subset of $\mathbb{N}$. I can make this explicit here. (I'm not sure when parameterisation over a constant domain is useful, do you have any examples of that?) I think your trivial parametrization example will not work in this case, as we cannot "force" constant time evaluation that easily. $\endgroup$ – Discrete lizard Sep 3 '20 at 21:10
  • 1
    $\begingroup$ Well, of course it is not a useful parametrization. The condition of infinite range for the projection onto $\mathbb{N}$ is not part of the definition and even if added you can still produce equally trivial parametrizations. For example, pick a fixed instance $x_0\in L$ and take the parametrized problem $L'=\{(x,n)\mid n=1\text{ and }x\in L\setminus\{x_0\}\text{ or } x=x_0\}$. Or instead of a single $x_0$ you can use a sequence of instances $x_1,x_2,...$ with $|x_i|<C$, for some constant $C$. $\endgroup$ – plop Sep 3 '20 at 21:40
  • 1
    $\begingroup$ @a.t. Well, currently you have defined a problem and did not tell there is a parameter. So, it seems you cannot be describing a parametrized problem because then you would have told me 1. that there is a parameter and 2. what this parameter is. Of course, if you would tell me that this is a parameterized problem, then $k$ would be my first guess for the parameter you meant. Some people in parametrized complexity would call $k$ the 'natural parameter' of the problem. Still, it is indeed the case that you would have to formally 'declare' which parameter is the one you're measuring. $\endgroup$ – Discrete lizard Sep 5 '20 at 20:23
  • 1
    $\begingroup$ For example, you could also find different parametrizations for the $k$-clique problem. Some of these may be interesting (perhaps the size of the smallest vertex cover for the graph? The treewidth? The size of a minimum feedback vertex set? Who knows.). But in principle no one is stopping you from measuring silly things, such as the number of graphs in your input, for example. As the number of graphs in your input is always $1$, this gives you the silly parametrization @plop gave above. It is not that easy to draw the line between a silly and serious parametrization, though. $\endgroup$ – Discrete lizard Sep 5 '20 at 20:31
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you that is clever! To me it is not clear that we can reduce 3-Coloring to $k$-Coloring. Perhaps that could be substantiated with a reference. This question: cs.stackexchange.com/questions/7671/… discusses that reduction. To verify, whether you mean polynomially reduce 3-Coloring.. or fpt reduce 3-Coloring.. is irrellevant, because polynomial time reductions imply the problems are also fpt reducable, right? $\endgroup$ – a.t. Sep 3 '20 at 19:03
  • $\begingroup$ Essentially yes, having a polynomial-time reduction means we have an FPT reduction. You would also need to show that $k' \leq g(k)$, so this argument gets a little more involved. I think a better/different way to phrase it is that you use the FPT routine with $k = 3$ just as an algorithm that solves the problem. The argument still holds then; the algorithm cannot exist unless P $=$ NP. $\endgroup$ – STanja Sep 3 '20 at 19:16
  • $\begingroup$ You may be unsure, but I believe this is known to be true, see my answer. $\endgroup$ – Discrete lizard Sep 3 '20 at 19:19
  • 1
    $\begingroup$ @a.t. please consider awarding the solution to Discrete lizard's answer. $\endgroup$ – STanja Sep 4 '20 at 9:16
  • $\begingroup$ Note, I initially misunderstood the answer. I thought/read wrong because I thought: we can reduce 3-Coloring to $k$-Coloring meant: 3-coloring is just a special case of $k$-Coloring and that then for the specific parameterization with $k=3$, one could see the parameterization$\neq$fpt, and that we then should use human understanding to see that all other parameterizations also "magically" are not fpt. But instead, you use: If one can reduce parameterization $Q$ to $Q'$ with $Q'\in fpt$ then $Q\in fpt$, to establish a polynomial transformation from the special case with $k=3$ to 3-Coloring. $\endgroup$ – a.t. Sep 5 '20 at 19:17
0
$\begingroup$

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:

enter image description here

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)

$\endgroup$
3
  • 1
    $\begingroup$ I'm not sure why you're involving ETH here. Yes, it implies FPT$\neq$W[1], but as that is what you need, why not assume it directly? A consequence of FPT$\neq$W[1] is that any W[1]-hard problem is not in FPT. Since we know plenty of W[1]-hard problems, this conjecture gives you problems outside of FPT. I don't quite get the final part of your answer, is what I mentioned here what you're trying to show? $\endgroup$ – Discrete lizard Sep 5 '20 at 20:40
  • 1
    $\begingroup$ I think assuming FPT$\neq$W[1] is almost assuming what you want to prove. While W[1]-hard problems don't necessarily have to have an "unparametrized" NP-hard problem, most interesting ones do. This means your argument seems to boil down to: we know there are some W[1]-hard problems, that also correspond to some NP-hard problem. Assume FPT$\neq$W[1], so no W[1]-hard problem is in FPT. Hence, there are some problems not in FPT. Or more direct, by assuming FPT$\neq$W[1], you already assume there exists some problem in W[1] but not in FPT (although you don't know which). $\endgroup$ – Discrete lizard Sep 5 '20 at 20:49
  • $\begingroup$ On your first comment: because I did not have authority nor argumentation to substantiate why it FTP$\neq$ W[1], so re-allocated the responsibility for substantiation to a known hypothesis. On your second comment: I think I mixed two argumentations, and failed to realize the classification of parameterisation $K-D$ as W[1]-hard immediatly implies a $K-D \notin$ FTP. That is why I thought the fpt reductions were still required to show $K'-D' \notin$ FTP. But that is not needed as you explain in your comment (or a different weak strategy to find not FPT parameterizations if it is valid). $\endgroup$ – a.t. Sep 6 '20 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.