On the commutativity of antiblocker diagrams under lift-and-project operators

DOI10.1016/J.DAM.2006.03.026MaRDI QIDQ2500533zbMATH OpenOpenAlexFDO

Authors M. C. Varaldo, Mariana S. Escalante, G. Nasini

Publication date 17 August 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.03.026

zbMATH Keywords

antiblocker dualitydisjunctive rankstable set problem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

The behaviour of the disjunctive operator in the context of the ``antiblocker duality diagram associated with the stable set polytope, \(\text{QSTAB}(G)\), of a graph and its complement has been studied by \textit{N. Aguilera, M. Escalante} and \textit{G. Nasini} [Math. Oper. Res. 27, 460--469 (2002; Zbl 1083.05505)]. The main consequence of this work is a generalization of the perfect graph theorem under disjunctive rank. The behaviour of the lift-and-project operators \(N_0, N\) and \(N_{+}\) has been studied by Lipták and Tunçel. They found an example of graph for which the diagram does not commute in one iteration of the \(N_0, N\) and \(N_{+}\) operator. In the present paper the authors give, for any number of iterations, explicit proofs of noncommutativity of the \(N_0, N\) and \(N_{+}\) diagram. In the particular case of the \(N_0\) and \(N\) operator, they found exact bounds for the ranks of the complements of line graphs (of complete graphs).

Recommendations

• Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs
• Lift-and-project ranks and antiblocker duality
• The stable set problem and the lift-and-project ranks of graphs
• On the polyhedral lift-and-project methods and the fractional stable set polytope
• A Generalization of the Perfect Graph Theorem Under the Disjunctive Index

Cites work

• A Generalization of the Perfect Graph Theorem Under the Disjunctive Index
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Applying Lehman's theorems to packing problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 2230212 (Why is no real title available?)
• Lift and project relaxations for the matching and related polytopes
• Maximum matching and a polyhedron with 0,1-vertices
• Note On: N. E. Aguilera, M. S. Escalante, G. L. Nasini, “A Generalization of the Perfect Graph Theorem Under the Disjunctive Index”
• On a representation of the matching polytope via semidefinite liftings
• On certain polytopes associated with graphs
• On the relationship between disjunctive relaxations and minors in packing and covering problems
• The stable set problem and the lift-and-project ranks of graphs

Cited in

(3)

• Lift-and-project ranks and antiblocker duality
• Anticommutant Lifting and Anticommuting Dilation
• On the behavior of the \(N_{+}\)-operator under blocker duality

This page was built for publication: On the commutativity of antiblocker diagrams under lift-and-project operators

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