  Yannakakis' Clique versus Independent Set problem (CL-IS) in communication
complexity asks for the minimum number of cuts separating cliques from stable
sets in a graph, called CS-separator. Yannakakis provides a quasi-polynomial
CS-separator, i.e. of size $O(n^{\log n})$, and addresses the problem of
finding a polynomial CS-separator. This question is still open even for perfect
graphs. We show that a polynomial CS-separator almost surely exists for random
graphs. Besides, if H is a split graph (i.e. has a vertex-partition into a
clique and a stable set) then there exists a constant $c_H$ for which we find a
$O(n^{c_H})$ CS-separator on the class of H-free graphs. This generalizes a
result of Yannakakis on comparability graphs. We also provide a $O(n^{c_k})$
CS-separator on the class of graphs without induced path of length k and its
complement. Observe that on one side, $c_H$ is of order $O(|H| \log |H|)$
resulting from Vapnik-Chervonenkis dimension, and on the other side, $c_k$ is
exponential.
  One of the main reason why Yannakakis' CL-IS problem is fascinating is that
it admits equivalent formulations. Our main result in this respect is to show
that a polynomial CS-separator is equivalent to the polynomial
Alon-Saks-Seymour Conjecture, asserting that if a graph has an edge-partition
into k complete bipartite graphs, then its chromatic number is polynomially
bounded in terms of k. We also show that the classical approach to the stubborn
problem (arising in CSP) which consists in covering the set of all solutions by
$O(n^{\log n})$ instances of 2-SAT is again equivalent to the existence of a
polynomial CS-separator.
