Clique versus independent set

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(nlogn)O(nlogn), 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 HH is a split graph (i.e. has a vertex-partition into a clique and a stable set) then there exists a constant cHcH for which we find a O(ncH)O(ncH) CS-separator on the class of HH-free graphs. This generalizes a result of Yannakakis on comparability graphs. We also provide a O(nck)O(nck) CS-separator on the class of graphs without induced path of length kk and its complement. Observe that on one side, cHcH is of order O(|H|log|H|)O(|H|log|H|) resulting from Vapnik–Chervonenkis dimension, and on the other side, ckck is a tower function, due to an application of the regularity lemma.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 kk complete bipartite graphs, then its chromatic number is polynomially bounded in terms of kk. 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(nlogn)O(nlogn) instances of 2-SAT is again equivalent to the existence of a polynomial CS-separator.