Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
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
3  
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

1 Answer 1

up vote 17 down vote accepted

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.

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

share|improve this answer
    
What is n? The number of vertices? And what is k? –  Wuschelbeutel Kartoffelhuhn May 4 at 23:10
1  
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
    
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. –  Raphael May 5 at 15:18
    
@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
2  
See also this similar question and David Eppstein's answer Best-case Running-time to solve an NP-Complete problem on mathoverflow. –  Pål GD May 5 at 15:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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