Clique versus Independent Set

Nicolas Bousquet 1 Aurélie Lagoutte 2, * Stéphan Thomassé 2
* Auteur correspondant
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958647
Contributeur : Aurélie Lagoutte <>
Soumis le : jeudi 13 mars 2014 - 09:55:15
Dernière modification le : jeudi 26 octobre 2017 - 13:44:08
Document(s) archivé(s) le : vendredi 13 juin 2014 - 10:56:55

Fichier

CS-sep_pour_journal_revisee.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé. Clique versus Independent Set. European Journal of Combinatorics, Elsevier, 2014, 40, pp.73-92. 〈http://www.sciencedirect.com/science/article/pii/S0195669814000249〉. 〈10.1016/j.ejc.2014.02.003〉. 〈hal-00958647〉

Partager

Métriques

Consultations de
la notice

365

Téléchargements du document

170