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

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.

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).

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.

• 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? Jun 20, 2023 at 22:02
• in the framework where $k$ is a fixed constant
– JimN
Jun 21, 2023 at 15:27