Clique versus independent set

DOI10.1016/J.EJC.2014.02.003zbMATH Open1297.05173arXiv1301.2474OpenAlexW1990565272MaRDI QIDQ402465FDOQ402465

Stéphan Thomassé, A. Lagoutte, Nicolas Bousquet

Publication date: 28 August 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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(n^{logn})$, 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^{logn})$ instances of 2-SAT is again equivalent to the existence of a polynomial CS-separator.

Full work available at URL: https://arxiv.org/abs/1301.2474

zbMATH Keywords

chromatic numberpolynomial Alon-Saks-Seymour conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• \(\epsilon\)-nets and simplex range queries
• Expressing combinatorial optimization problems by linear programs
• Stable sets and polynomials
• The Erdős-Hajnal conjecture for paths and antipaths
• Random graphs.
• Linear vs. semidefinite extended formulations
• Communication Complexity
• Full Constraint Satisfaction Problems
• The Complexity of the List Partition Problem for Graphs
• Adapted List Coloring of Graphs and Hypergraphs
• List Partitions
• Bi‐arc graphs and the complexity of list homomorphisms
• Bounds of neighborly families of convex polytopes
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• Variations on a theme of Graham and Pollak
• On the decomposition ofkn into complete bipartite graphs
• A counterexample to the Alon-Saks-Seymour conjecture and related problems

Cited In (11)

• Ordered biclique partitions and communication complexity problems
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Some improved bounds on communication complexity via new decomposition of cliques
• Title not available (Why is that?)
• A simple \((2 + \epsilon)\)-approximation algorithm for split vertex deletion
• Extended formulations from communication protocols in output-efficient time
• Excluding hooks and their complements
• Communication Complexity of Pairs of Graph Families with Applications
• Large cliques and independent sets all over the place
• On the binary and Boolean rank of regular matrices
• Decomposition techniques applied to the clique-stable set separation problem

This page was built for publication: Clique versus independent set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q402465)