6
$\begingroup$

I just stumbled upon this question here Why is the clique problem NP-complete? and I am confused by the given answer. The question about about whether $k$-clique is NP-hard for a fixed $k$ and the answer is no. However, we know that clique in general is NP-hard. Also we know that $0 \leq k \leq n$ must hold (for a graph of size $n$).

What is wrong about the following reasoning: Assume I have some algorithm $A_i$ that solves $i$-clique for some fixed $i$ in polynomial time. Now given some general clique problem without a specific $k$ (these problems are supposedly NP-hard), I simply run $A_i$ for $i=1$ to $n$. Now since $n$ is poly and every $A_i$ runs in polynomial time $p_i$, the resulting algorithm also runs in polynomial time $\sum p_i$, but this cannot be the case, since clique is NP-hard.

What is wrong about my reasoning?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

The polynomial depends on the parameter $k$. In particular, the algorithm that people have in mind runs in time $O(n^k)$ (better algorithms might exist, but I believe that we don't know a running time better than $O(n^{O(k)})$. The running time of your proposed algorithm is then big O of $$ \sum_{k=1}^n n^k, $$ which is no longer polynomial.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Why would that not be polynomial. If I add a polynomial amount of polynomials, then I end up with a polynomial not something exponential, no? Basically, in your big-O notation, the addition would only change the hidden constant. $\endgroup$
    – Cryptonaut
    Commented Sep 22, 2016 at 18:53
  • 3
    $\begingroup$ No. The function $n^n$ is not a polynomial. $\endgroup$
    – Yuval Filmus
    Commented Sep 22, 2016 at 18:54
  • 1
    $\begingroup$ Ah I think I understand. So it's tractable, if I fix k independent of the graph size, because then it's just a "constant". If I ask: Is there a clique of size n-1 in a graph of size n, then it's still hard, because k depends on n? Basically I need to make sure that the exponent has some dependency of the size of the graph or what would be a simple way to look at it? $\endgroup$
    – Cryptonaut
    Commented Sep 22, 2016 at 18:57
  • 2
    $\begingroup$ Actually the trivial algorithm (which goes over all potential cliques) runs in time proportional to $\binom{n}{k}$, so the hardest setting is $k = n/2$; when $k = n-1$, the problem becomes easy again. $\endgroup$
    – Yuval Filmus
    Commented Sep 22, 2016 at 18:59
  • 4
    $\begingroup$ If you're interested in pursuing this direction further, you should read on parameterized complexity. $\endgroup$
    – Yuval Filmus
    Commented Sep 22, 2016 at 19:00

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.