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

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.

• I would just use induction every s-clique consists of s-1 s-1-clique. so having all s-1-clique finding a s-clique is just checking all adjacent nodes of the s-1-clique for a connection to evey node in the s-clique as I stated in the body Feb 25 at 11:37
• Consider the Turán graph $T(n,k-1)$: a $(k-1)$-partite graph in which every pair of vertices in different parts have an edge between them. There are no $k$-cliques in this graph, but a very large number of $(k-1)$-cliques: $(n/(k-1))^{k-1}$ of them (assuming $n$ is divisible by $k-1$). All of these will need to be checked by your algorithm before it (correctly) reports that there are no $k$-cliques. Feb 25 at 11:49
• Apologies for my rude initial response, which I've now deleted. Feb 25 at 11:51

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