1
$\begingroup$

Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k? Is it correct to say that it doesn't exist because clique is NP-Complete?

$\endgroup$

3 Answers 3

1
$\begingroup$

Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k?

We do not know the answer to this question.

Is it correct to say that it doesn't exist because clique is NP-Complete?

No, that would not be correct. Since we currently do not know whether P=NP, it could be that Clique is polynomial time solvable.

However, if we assume that P != NP, there is no polynomial time algorithm for Clique.


Ps: Your problem is in fact co-NP-complete.

$\endgroup$
0
$\begingroup$

If there exists such a polynomial algorithm, then we can run this algorithm for each $k=1,2,...n$ thus a polynomial algorithm with an additional factor $n$ for clique problem is generated. This is a contradiction to the fact that clique is NP-Complete (a direct reduction from independent set can proof the hardness).

$\endgroup$
0
$\begingroup$

It depends on what you consider a polynomial-time algorithm in this case.

Given a graph and an integer $k$ you can determine if there all the cliques are of size at most $k$ by looking at all sets of $(k+1)$ vertices and determining if they form a clique. If there is any clique of size larger than $k$, then choosing any $(k+1)$ of those nodes will form a clique.

So you can answer your question in $O(n^{k+1})$ time. Is that polynomial? Depends on your framework.

$\endgroup$
2
  • $\begingroup$ This is quite a stretch. If your algorithm, $A(G,k)$ is polynomial, and I create an algorithm $B(G)$ which simply calls $A$ with $k = n/100$, in which framework is $B$ a polytime algorithm? $\endgroup$
    – Pål GD
    Jun 20, 2023 at 22:02
  • $\begingroup$ in the framework where $k$ is a fixed constant $\endgroup$
    – JimN
    Jun 21, 2023 at 15:27

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.