Clique versus independent set

DOI10.1016/J.EJC.2014.02.003MaRDI QIDQ402465zbMATH OpenOpenAlexFDO

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

Publication date 28 August 2014

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

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)

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.

Recommendations

• Decomposition techniques applied to the clique-stable set separation problem
• Subdivided claws and the clique-stable set separation property
• Complexity of graph partition problems
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Clique and anticlique partitions of graphs

Cites work

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

Cited in

(12)

• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Subdivided claws and the clique-stable set separation property
• Communication complexity of pairs of graph families with applications
• A simple \((2 + \epsilon)\)-approximation algorithm for split vertex deletion
• scientific article; zbMATH DE number 5206702 (Why is no real title available?)
• Large cliques and independent sets all over the place
• On the binary and Boolean rank of regular matrices
• Ordered biclique partitions and communication complexity problems
• Excluding hooks and their complements
• Decomposition techniques applied to the clique-stable set separation problem
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Some improved bounds on communication complexity via new decomposition of cliques

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)