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$ – Yuval Filmus Apr 6 '19 at 13:52
  • $\begingroup$ I did not understand the algorithm completely to understand the proof itself. $\endgroup$ – Jay Apr 6 '19 at 14:50

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 '19 at 15:30
  • $\begingroup$ I'm sorry, I can't explain it any better than what I wrote. $\endgroup$ – Yuval Filmus Apr 6 '19 at 15:31
  • $\begingroup$ Thanks a lot Yuval, I’ll try to figure it out. $\endgroup$ – Jay Apr 6 '19 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$ – Yuval Filmus Apr 7 '19 at 5:05
  • $\begingroup$ Correct. Resolving the issue of parity results in at most $1+\log n$ rounds. $\endgroup$ – James Bailey Apr 7 '19 at 5:31

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.