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.