Clique versus Independent Set

Nicolas Bousquet (1) , Aurélie Lagoutte (2) , Stéphan Thomassé (2)

1 ALGCO - Algorithmes, Graphes et Combinatoire
2 MC2 - Modèles de calcul, Complexité, Combinatoire

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) , 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 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 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(nlogn) instances of 2-SAT is again equivalent to the existence of a polynomial CS-separator.

Mots clés: Alon-Saks-Seymour conjecture; Clique-Stable separation; split-free graphs; Pk-free graphs; random graphs; stubborn problem

Domaines: Mathématique discrète [cs.DM]

Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé. Clique versus Independent Set. European Journal of Combinatorics, 2014, 40, pp.73-92. ⟨10.1016/j.ejc.2014.02.003⟩. ⟨hal-00958647⟩