Suppose you have an undirected graph $G = (V, E)$, known to both Alice and Bob, Alice gets an independent set of $G$. Bob gets a Clique $B ⊆ V$.

Is there any algorithm in $O(\log^2 n)$ bits that finds whether $ A ∩ B = Ø $?

This is a well known communication complexity problem called CIS problem that was described by Yannakakis.

I'm not sure why and how does this work exactly. and which part of the $n/2$ vertices are reduced by both players.

P.S. I came to a conclusion that an independent and a clique can intersect in at most one vertex.

  • $\begingroup$ The lecture notes contain a complete proof. $\endgroup$ Apr 6, 2019 at 13:52
  • $\begingroup$ I did not understand the algorithm completely to understand the proof itself. $\endgroup$
    – Jay
    Apr 6, 2019 at 14:50

2 Answers 2


The two players construct a sequence $V_0 \supset V_1 \supset \cdots \supset V_m$ of sets of vertices such that:

  1. $V_0$ consists of all vertices in the graph.
  2. $|V_{i+1}| \leq (|V_i|+1)/2$.
  3. $V_i \supseteq C \cap I$.

The players stop once $|V_m| \leq 1$. At this point they can answer the question using $O(1)$ communication.

At round $i$, the players know $V_{i-1}$, and wish to construct $V_i$. They act as follows:

  • If $C \cap V_{i-1}$ contains a vertex $v$ with fewer than $|V_{i-1}|/2$ neighbors in $V_{i-1}$, then Alice sends Bob one such vertex $v$, and both players set $V_i$ to be this set of neighbors, together with $v$ (this is valid since $C \cap I \subseteq C \subseteq V_i$). Otherwise, she sends $\bot$.

  • If Alice sent $\bot$ and $I \cap V_{i-1}$ contains a vertex $v$ with fewer than $|V_{i-1}|/2$ non-neighbors in $V_{i-1}$, then Bob sends Alice one such vertex $v$, and both players set $V_i$ to be this set of non-neighbors, together with $v$ (this is valid since $C \cap I \subseteq I \subseteq V_i$). Otherwise, he sends Alice $\bot$.

  • If both players sent $\bot$, then $C \cap I = \emptyset$. Indeed, if $v \in C \cap I$, then $v$ has at least $|V_{i-1}|/2$ neighbors and at least $|V_{i-1}|/2$ non-neighbors inside $|V_{i-1}|$, whereas the number of potential neighbors and non-neighbors is just $|V_{i-1}|-1$. Therefore the players can abort and conclude that $C \cap I = \emptyset$.

Each round takes $O(\log n)$ bits of communication, and there are $O(\log n)$ rounds, for a total of $O(\log^2 n)$ bits of communication.

  • $\begingroup$ How does the number of vertices are resuced by factor of 2 - this leads to the $O(log(n))$ rounds? $\endgroup$
    – Jay
    Apr 6, 2019 at 15:30
  • $\begingroup$ I'm sorry, I can't explain it any better than what I wrote. $\endgroup$ Apr 6, 2019 at 15:31
  • $\begingroup$ Thanks a lot Yuval, I’ll try to figure it out. $\endgroup$
    – Jay
    Apr 6, 2019 at 15:32

The $O(\log n)$ rounds comes from the fact that we are doing a binary search:

If the algorithm fails to terminate, then either Alice or Bob share a vertex v.

If Alice shares $v$, then $v$ has fewer than $|V_{i-1}|/2$ neighbors in $V_{i-1}$. $V_i$ is set to be this neighborhood (along with v). Observe that $|V_i|< |V_{i-1}|/2+1$. We will be a little hand-wavy and say $|V_i|\leq |V_{i-1}|/2$ (although it may actually be $|V_{i-1}|/2+1/2$ when $|V_{i-1}|$ is odd).

Similarly, if Bob shares $v$, then $v$ has fewer than $|V_{i-1}|/2$ non-neighbors in $V_{i-1}$. $V_i$ is set to be this non-neighborhood (along with v). As such, $|V_i|\leq |V_{i-1}|/2$ (again we are being a little hand-wavy).

In both cases $|V_i|\leq |V_{i-1}|/2$. As such, if the algorithm fails to terminate after $k$ iterations, then, inductively, $|V_k|\leq |V_0|/2^k$. Finally, observe that the algorithm terminates if $|V_k|\leq 1$, i.e., we will terminate if ever $V_k$ is a singleton or empty. Finally, $|V_k|\leq |V_0|/2^k\leq 1$ if $k\geq \log |V_0|=\log n$ implying that we must terminate in $\log n$ iterations.

  • 1
    $\begingroup$ If $|V_{i-1}|$ is odd then your inequality is off by 1/2. $\endgroup$ Apr 7, 2019 at 5:05
  • $\begingroup$ Correct. Resolving the issue of parity results in at most $1+\log n$ rounds. $\endgroup$ Apr 7, 2019 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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