I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this:

What is the minimum size of the largest clique in any graph with N nodes and M edges?

The hints suggest using Turan's theorem, but it's not clear to me how to get from that to a solution.

How can I solve this problem, either with or without Turan's theorem?

The full questions is here.

  • 1
    $\begingroup$ Did you look up Turán's theorem? That's a good thing to do if the theorem is given as a hint. $\endgroup$ – Yuval Filmus Apr 5 '15 at 21:44
  • $\begingroup$ Yes, of course I looked it up on Wikipedia. $\endgroup$ – Thomas Johnson Apr 5 '15 at 22:38

Turán's theorem states that if a graph on $n$ vertices doesn't contain an $(r+1)$-clique then it has at most $\lfloor \frac{r-1}{r} \frac{n^2}{2} \rfloor$ edges. You take it from here.

  • 1
    $\begingroup$ I'm not sure if the poster got the answer or not, but your answer just rephrases a hint that he already said he knew about. I fail to see how this is helpful. $\endgroup$ – nullgraph Jun 10 '15 at 17:41
  • $\begingroup$ @nullgraph You are welcome to offer your own answer instead. $\endgroup$ – Yuval Filmus Jun 10 '15 at 17:45
  • $\begingroup$ I think the following answer gives very good hint, I'm not sure how to offer it as it's not mine math.stackexchange.com/questions/1279241/… $\endgroup$ – nullgraph Jun 10 '15 at 17:54

Turan's theorem states the following:

If a graph with $n$ vertices does not contain a clique of size $r+1$, then the number of edges in that graph is at most $\frac{1}{2}(n^2 - (n\,\bmod\,r)\lceil n/r\rceil^2 - (r-(n\,\bmod\,r))\lfloor n/r\rfloor^2)$.

The former statement is equivalent to the following statement:

If a graph with $n$ vertices has more than $\frac{1}{2}(n^2 - (n\,\bmod\,r)\lceil n/r\rceil^2 - (r-(n\,\bmod\,r))\lfloor n/r\rfloor^2)$ edges, then it does contain a clique of size $r+1$.

The minimum size of the largest clique in any graph with $n \geq 2$ vertices and $m \geq 1$ edges can then be computed in a naive way as follows:

(1.) set $r=n-1$

(2.) compute $m^*(r) = \frac{1}{2}(n^2 - (n\,\bmod\,r)\lceil n/r\rceil^2 - (r-(n\,\bmod\,r))\lfloor n/r\rfloor^2)$

(3.) if $m > m^*(r)$ return $r+1$ else decrement $r$ by 1 and go to (2.)

The algorithm above runs in linear time. A more efficient solution runs in logarithmic time. The idea is to utilize binary search to find the value $r+1$ such that $m>m^*(r)$ and $m \leq m^*(r+1)$.

  • $\begingroup$ I don't understand this for r>1 how can m> m*(r)? $\endgroup$ – Kumar Gaurav Jul 19 '17 at 20:27

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.