Bxdty

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.

• 
  Lecture notes; the claim is Theorem 3


• Link to Nisan & Kushilevitz's textbook

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.

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.

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 $1leq |V_k|leq |V_0|/2^k$ for any k, i.e., we will terminate if ever $V_k$ is a singleton or empty. Solving for $k$, we must terminate if $kgeq log |V_0|=log n$.