The stable set problem and the lift-and-project ranks of graphs

DOI10.1007/s10107-003-0407-5zbMath1160.90584OpenAlexW1604898370MaRDI QIDQ1424302

László Lipták, Tunçel, Levent

Publication date: 11 March 2004

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-003-0407-5

zbMATH Keywords

Integer programmingSemidefinite programmingLift-and-projectSemidefinite liftingStable set problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Boolean programming (90C09) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (24)

Lift-and-project ranks and antiblocker duality ⋮ Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs ⋮ Tree-width and the Sherali-Adams operator ⋮ Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs ⋮ Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture ⋮ On the behavior of the \(N_{+}\)-operator under blocker duality ⋮ Characterizing N+-perfect line graphs ⋮ Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ On the facets of lift-and-project relaxations under graph operations ⋮ Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope ⋮ Handelman's hierarchy for the maximum stable set problem ⋮ Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra ⋮ Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ Lift-and-project ranks of the set covering polytope of circulant matrices ⋮ On the commutativity of antiblocker diagrams under lift-and-project operators ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Strong reductions for extended formulations ⋮ On the polyhedral lift-and-project methods and the fractional stable set polytope ⋮ On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets ⋮ Unnamed Item ⋮ Lovász-Schrijver PSD-Operator on Claw-Free Graphs ⋮ On the facets of the lift-and-project relaxations of graph subdivisions ⋮ Near-perfect graphs with polyhedral

This page was built for publication: The stable set problem and the lift-and-project ranks of graphs