7
$\begingroup$

I have seen some problems that are NP-hard but polynomially solvable in fixed dimension.

Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer Linear Programming with fixed number of variables or constraints by Lenstras result.

Questions:

What are other examples of NP-hard problems that become polynomial time solvable if the dimension is fixed?

Are there problems for which this is not the case?

Is this always the case for problems that admit an FPTAS/pseudo-polynomial time algorithm such as Knapsack?

$\endgroup$
  • $\begingroup$ What you are looking for is FPT. If you can solve a problem in $f(k) \cdot n^{O(1)}$ time for any function $f$, depending only on $k$, the problem is said to be fixed parameter tractable, or in the complexity class FPT. Classical problems that are in FPT are vertex cover parameterized by solution size, SAT parameterized by number of variables, treewidth parameterized by treewidth, etc. See also FPT races for a list of selected problems. $\endgroup$ – Pål GD May 3 '13 at 19:06
  • 1
    $\begingroup$ See also the reference question Dealing with intractability: NP-complete problems. $\endgroup$ – Pål GD May 4 '13 at 9:52
5
$\begingroup$

In parametrized complexity we solve the problem by fixing some parameter (say $k$). If we are able to solve some problem in $f(k) \cdot p(n)$ time, we say the problem is fixed parameter tractable in $k$. Here $f(k)$ is just some computable function. There are lots of NP-hard problems that are FPT, however, there are many problems in NP that are believed to not be fixed parameter tractable.

If by fixing some parameter we can solve a problem in time $O(n^{f(k)})$, this problem is said to be in XP. We believe that XP is not equal to FPT (just as we believe P $\neq$ NP). But there are also lots of problems between these two (FPT and XP), and we have defined a hierarchy (actually several), one of those being the W-hierarchy. In the W hierarchy you have reductions like reduction in NP-complete classes, except, we are not looking for polytime reductions, we just need an FPT reduction. The class W[0] is the class FPT.

These are some samples in different classes of the W hierarchy:

  1. Vertex cover is FPT (so is vertex disjoint paths on undirected graphs)
  2. Independent set and Clique are both W[1]-complete
  3. Dominating set is W[2]-Complete.

These are another level of complexities to classify NP problems in more precise way and if you want more you can look at this paper.

And if you want even more is good to read Grohe and Fomine's book

And finally:

Is this always the case for problems that admit an FPTAS/pseudo-polynomial time algorithm such as Knapsack

Not necessarily, it's known that if the problem has FPTAS then it's also FPT (which is obvious), but there is some works on the relation of PTAS and XP, but there isn't very tight relation between PTAS and W hierarchy (at least I don't know at this moment).

Also in some cases may be we fix some different parameters, e.g: length of a longest path in the graph is bounded and size of a solution is bounded (e.g in feedback vertex set), ...

$\endgroup$
  • $\begingroup$ Vertex Cover is maybe the simplest FPT problem there is and there is an extremely simple branching argument solving the problem in time $2^k n^{O(1)}$. Maybe you meant Independent Set or Clique? Both those problems are W[1]-complete. Also, don't say a problem is "FPT when you fix $k$", as the point is that it is FPT in $k$ (or whatever the parameter). $\endgroup$ – Pål GD May 3 '13 at 17:44
  • $\begingroup$ Also, it is not true that W[1] contains all problems solvable in time $n^k$, it's just not that simple. $\endgroup$ – Pål GD May 3 '13 at 18:04
  • $\begingroup$ @PålGD, You are right, There is a very simple kernel for vertex cover, I wrote the vertex disjoint path for the first one, then I was thinking to say some covering related problem for the second one, I mixed it with the first one, and caused to this mistake, but yes I could say that the complex layer of circuits that we need determines $W$ hierarchy, but I see is not sensible for the newbie and needs more precise definitions, so I referred to the best book that I know for this, for exact definition, and if you see more than one time I said simple definition, sure is not correct in general. $\endgroup$ – user742 May 3 '13 at 20:25
  • $\begingroup$ Anyway, Now I see, Juho, edited my answer and removed that part, but I think it was good to bring some intuition to the reader, to say how hard are they. $\endgroup$ – user742 May 3 '13 at 20:33
  • $\begingroup$ Actually, I edited the answer (you can see revision history by clicking the "edited x y ago"-link. $\endgroup$ – Pål GD May 4 '13 at 9:38

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.