# The Clique vs. Independent Set Problem

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.

• The lecture notes contain a complete proof. – Yuval Filmus Apr 6 '19 at 13:52
• I did not understand the algorithm completely to understand the proof itself. – Jay Apr 6 '19 at 14:50

## 2 Answers

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.

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

• If $|V_{i-1}|$ is odd then your inequality is off by 1/2. – Yuval Filmus Apr 7 '19 at 5:05
• Correct. Resolving the issue of parity results in at most $1+\log n$ rounds. – James Bailey Apr 7 '19 at 5:31