1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ – FelixOuttaSpace Feb 25 at 11:37
  • 2
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Feb 25 at 11:49
  • 1
    $\begingroup$ Apologies for my rude initial response, which I've now deleted. $\endgroup$ – j_random_hacker Feb 25 at 11:51
6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Ok I see this probably destroys polynomial time. $\endgroup$ – FelixOuttaSpace Feb 25 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.