# 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 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 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 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 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.
Yes, $n$ is the number of vertices, $k$ is the solution size, i.e., at most $n$, but "usually" a lot less, for some definition of "usually". –  Pål GD May 4 at 23:31
@Raphael, if you're thinking about VC-max degree 3, then I don't know its dependence on $n$, i.e., the polynomial dependence on the input. The exponential factor is better in the other problem, but they might be incomparable wrt the "total running time" for some definition of "total running time". A better question is, for every $\epsilon \in (0,1)$ does there exist an NP-hard problem solvable in $O^*( (2-\epsilon)^n)$ time where $O^*$ hides polynomial factors? –  Pål GD May 5 at 15:27