The Clique vs. Independent Set Problem

Question

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.

Answer 1

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.

Answer 2

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.