2
$\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?

$\endgroup$
3
$\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.

$\endgroup$
  • $\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$ – ZeroKnowledge Sep 22 '16 at 18:53
  • 2
    $\begingroup$ No. The function $n^n$ is not a polynomial. $\endgroup$ – Yuval Filmus Sep 22 '16 at 18:54
  • $\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$ – ZeroKnowledge Sep 22 '16 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 Sep 22 '16 at 18:59
  • 4
    $\begingroup$ If you're interested in pursuing this direction further, you should read on parameterized complexity. $\endgroup$ – Yuval Filmus Sep 22 '16 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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