# Which NP-Complete problem has the fastest known algorithm?

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)$?

• What algorithm has running time $O(n^2 \cdot 2^n)$? EDIT: I assume you mean the Held–Karp algorithm for Traveling Salesman. – Guildenstern May 4 '14 at 21:29
• You can take a look at the answers to the question Are there subexponential-time algorithms for NP-complete problems?. – Pål GD May 4 '14 at 22:05
• "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(\_)$?" – Raphael May 5 '14 at 6:53
• 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"... – Wuschelbeutel Kartoffelhuhn May 5 '14 at 13:19

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.
• @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. – Pål GD Apr 26 '15 at 3:52