Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles

DOI10.1007/978-3-030-45771-6_9OpenAlexW3155752882MaRDI QIDQ5041738

Samuel Fiorini, Stefan Weltge, Tony Huynh, Michele Conforti

Publication date: 14 October 2022

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-45771-6_9

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Lifts for Voronoi cells of lattices

Uses Software

• Unimodularity
• Unimodularity Test

Cites Work

• Unnamed Item
• A simpler proof for the two disjoint odd cycles theorem
• Stable sets and graphs with no even holes
• Integer program with bimodular matrix
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• On certain polytopes associated with graphs
• On the minors of an incidence matrix and Smith normal form
• Implementation of a unimodularity test
• Extended formulations for stable set polytopes of graphs without two disjoint odd cycles
• Geometric random edge
• Projective-planar signed graphs and tangled signed graphs
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Disjunctive Programming
• Compositions of Graphs and Polyhedra II: Stable Sets
• Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting
• A strongly polynomial algorithm for bimodular integer linear programming
• The stable set problem in graphs with bounded genus and bounded odd cycle packing number
• On sub-determinants and the diameter of polyhedra