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.