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.


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.

  • $\begingroup$ Thanks, that's great! This 0-fooling set gives $N^0(\text{IS}_{n,r}) \ge \Omega(n^2)$ which is essentially the best possible. $\endgroup$ – András Salamon Apr 1 '15 at 12:51

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.