Decomposition techniques applied to the clique-stable set separation problem

DOI10.1016/J.DISC.2017.10.014MaRDI QIDQ1709553zbMATH OpenOpenAlexFDO

Authors Nicolas Bousquet, A. Lagoutte, Frédéric Maffray, Lucas Pastor

Publication date 5 April 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

clique-stable set separationgraph decompositionstable set polytopeextended formulationapple-free graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In a graph, a Clique-Stable Set separator (CS-separator) is a family $mathcalC$ of cuts (bipartitions of the vertex set) such that for every clique $K$ and every stable set $S$ with $KcapS=emptyset$, there exists a cut $(W,W^{\prime })$ in $mathcalC$ such that $KsubseteqW$ and $Ssubseteq{W}^{\prime }$. Starting from a question concerning extended formulations of the Stable Set polytope and a related complexity communication problem, Yannakakis [17] asked in 1991 the following questions: does every graph admit a polynomial-size CS-separator? If not, does every perfect graph do? Several positive and negative results related to this question were given recently. Here we show how graph decomposition can be used to prove that a class of graphs admits a polynomial CS-separator. We apply this method to apple-free graphs and cap-free graphs.

Recommendations

• Clique versus independent set
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• New applications of clique separator decomposition for the maximum weight stable set problem
• Fundamentals of Computation Theory
• Subdivided claws and the clique-stable set separation property

Cites work

• scientific article; zbMATH DE number 3878985 (Why is no real title available?)
• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• Clique versus independent set
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Even and odd holes in cap-free graphs
• Expressing combinatorial optimization problems by linear programs
• Independent sets of maximum weight in apple-free graphs
• Linear vs. semidefinite extended formulations
• Ordered biclique partitions and communication complexity problems
• Some improved bounds on communication complexity via new decomposition of cliques
• Stable sets and graphs with no even holes
• Stable sets and polynomials
• The Erdős-Hajnal conjecture for long holes and antiholes
• The strong perfect graph conjecture for pan-free graphs
• Vertex elimination orderings for hereditary graph classes
• Weakly triangulated graphs

Cited in

(5)

• Subdivided claws and the clique-stable set separation property
• On the binary and Boolean rank of regular matrices
• A novel decomposition approach to set covering problems by exploiting special structures
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Clique versus independent set

This page was built for publication: Decomposition techniques applied to the clique-stable set separation problem

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