In terms of worst-case asymptotic runtime, which NP-complete problem has the fastest-known (exact) algorithm and what is the algorithm? Is there something known that is faster than $O(n^2*2^n)$?

  • $\begingroup$ What algorithm has running time $O(n^2 \cdot 2^n)$? EDIT: I assume you mean the Held–Karp algorithm for Traveling Salesman. $\endgroup$ Commented May 4, 2014 at 21:29
  • 3
    $\begingroup$ You can take a look at the answers to the question Are there subexponential-time algorithms for NP-complete problems?. $\endgroup$
    – Pål GD
    Commented May 4, 2014 at 22:05
  • $\begingroup$ "Faster than $O(\_)$" does not make sense. You mean $\Theta$? Or is the question, "Is there an algorithm with a better proven upper runtime bound than $O(\_)$?" $\endgroup$
    – Raphael
    Commented May 5, 2014 at 6:53
  • $\begingroup$ The latter. It's valid point; there could be an algorithm A that's faster than B in practice but not with a tighter upper bound. I'm not sure why it doesn't make sense to say "faster than an upper bound" rather than "faster than a lower AND upper bound"... $\endgroup$ Commented May 5, 2014 at 13:19

1 Answer 1


Vertex Cover has an algorithm running in time $1.2738^k + nk$, and is thus faster than $2^n n^2$, even with $k=n$. You can check out Table of FPT races for a short list of FPT running times of different problems. Here, $n$ is the number of vertices and $k$ is the solution size.

Also, the question Are there subexponential-time algorithms for NP-complete problems? addresses similar questions.

  • $\begingroup$ The questions asks for fastest known algorithms and the table you link to does have "faster" algorithms than the VC one (in particular subexponential ones), so it's probably not the best to cite. $\endgroup$
    – Raphael
    Commented May 5, 2014 at 15:18
  • 2
    $\begingroup$ See also this similar question and David Eppstein's answer Best-case Running-time to solve an NP-Complete problem on mathoverflow. $\endgroup$
    – Pål GD
    Commented May 5, 2014 at 15:35
  • $\begingroup$ @Raphael Yes, for instance Minimum Fill-In has an algorithm which for every $\epsilon > 0$, runs in $O( (1+\epsilon)^k + \text{poly}(n))$ time. $\endgroup$
    – Pål GD
    Commented Apr 26, 2015 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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