Is this clique algorithm in polynomial time correct or might it have another time complexity?

Question

I came up with the idea finding a k-clique through starting at a small s-clique (like 1-,2- or 3-clique) and use it to find every s+1 Clique iterative. I had some trouble finding the Time Complexity and I am not sure where I might have went wrong.

First I will show the algorithm, argue about its correctness and then what I tried on finding the time complexity.

So given a Graph $G = (V,E) $ and $n = |V|$ and $m = |V|$ and the case of k > 3 we would use the following algorithm:

• Find every 3-Clique first in $O(n^3)$ (using three for loops for checking every possible triangle) and using hashing whether a triangle was already added or not.
• Now we have the set $M := \{(i,j,k) | i,j,k \in V \land (i,j), (i,k), (j,k) \in E \}$ of triples of all disting 3-cliques.
• Next we use the list of 3-Clique to search for 4-Clique through looking at every adjacent node $l$ of of every triple $(i,j,k)$. If one the the adjacent nodes is connected to all $(i,j,k)$ so that $(l,i),(l,j),(l,k) \in E$ we have found a 4-Clique.
• We proceed this process for every s-Clique with $s \in \{4,...,k \} $ usingal found $s-1$ clique

For the correctness of the algorithm it should be enough to show by induction that every s-clique consists of s-1 possible (s-1)-cliques. So once we have all s-1-clique it is easy to find every s-clqiue, since we just have to check every adjacent node of the s-1-clique for a connection with every node in the s-1-clique.

I tried to estimate the time complexity the following way:

• Worst Case Complexity is finding a n-Clique in $G$. So this means we have $ m = n(n-1) $

• We would have to do $(n - 3)$-Loops for finding every s-clique in the sth loop.

• In every loop we have less n s-clique where every s-clique might have maximum $s(n-1)$ adjacent nodes to look at.

• Since we have less then n s-clique this would mean looking at $n*s(n-1)$ possible edges for finding a new s-clique.

This would sum up to $O(n^5)$ using gauss sum for every s-clique, but this would mean clique is in P and this seems a little bit to easy to be true.

Answer 1

Your analysis of the time complexity is wrong. Specifically this statement:

In every loop we have less n s-clique where every s-clique might have maximum s(n−1) adjacent nodes to look at.

In fact you can have up to $\binom{n}{s}$ $s$-cliques.

You approach is essentially enumerating all cliques of size up to $k-1$. So you cannot hope to have a running time better than $\Omega\left( \sum_{s=1}^{k-1} \binom{n}{s} \right)$.