Communication complexity of Independent Set game?

Question

Consider the following communication game.

Independent Set game

Let $[n] = \{0,1,\dots,n-1\}$ and let $r$ be a positive integer smaller than $n/(1+\log n)$. Alice receives a set $X$ of edges, each edge being a pair of distinct vertices from $[n]$, and Bob receives a set $Y$ of edges. Alice and Bob must communicate to determine whether the graph $([n],X \cup Y)$ contains an independent set with $r$ vertices. Let IS$_{n,r}(X,Y) = 1$ if there is such a set, and IS$_{n,r}(X,Y) = 0$ otherwise.

There is a simple nondeterministic protocol to confirm that IS$_{n,r}(X,Y) = 1$; Alice nondeterministically chooses an $r$-vertex set $I$ that forms an independent set in her graph $([n],X)$ and sends Bob a description of this set using at most $r(1+\log n)$ bits. Bob responds with 1 if $I$ is an independent set in $([n],Y)$ also; otherwise he responds with 0. On the other hand, there is a fooling set of pairs of sets $(V,V)$ such that $([n],V)$ is a graph formed by $r$ disconnected vertices adjoined to a complete graph with $n-r$ vertices. This 1-fooling set contains $\binom{n}{r}$ such fooling pairs, so the nondeterministic communication complexity of $\text{IS}_{n,r}$ is at least $\Omega(r\log n)$. It follows that the simple protocol is optimal up to a small constant factor.

My question is:

Is there a large 0-fooling set for IS$_{n,r}$?

If not, is there an efficient deterministic protocol?

I would also be interested in pointers to the literature if this problem is known. The closest I have found is the Clique vs. Independent Set game of Yannakakis but this did not seem useful here.

Answer 1

Yes, there is a large 0-fooling set. It is enough to prove this for $r=2$, as we can add (the same) $r-2$ independent vertices to all graphs in our construction. For $r=2$, take every graph that has exactly ${n\choose 2}/2$ edges. Everyone will fool around with its complement.