Skip to Main content Skip to Navigation
Journal articles

Clique versus Independent Set

Nicolas Bousquet 1 Aurélie Lagoutte 2, * Stéphan Thomassé 2
* Corresponding author
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MC2 - Modèles de calcul, Complexité, Combinatoire
LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download
Contributor : Aurélie Lagoutte <>
Submitted on : Thursday, March 13, 2014 - 9:55:15 AM
Last modification on : Thursday, November 21, 2019 - 1:54:22 AM
Document(s) archivé(s) le : Friday, June 13, 2014 - 10:56:55 AM


Files produced by the author(s)



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



Record views


Files downloads