Extended formulations for stable set polytopes of graphs without two disjoint odd cycles

DOI10.1007/S10107-021-01635-0MaRDI QIDQ2118145zbMATH OpenOpenAlexFDO

Authors Michele Conforti, Samuel Fiorini, Tony Huynh, Stefan Weltge

Publication date 22 March 2022

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

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Integer programming (90C10) Flows in graphs (05C21)

Abstract: Let $G$ be an $n$-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC'17) for bimodular integer programs can be used to find a maximum weight stable set in $G$ in strongly polynomial time. Building on structural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size-$O(n^2)$ extended formulation for the stable set polytope of $G$.

Recommendations

• Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
• A smaller extended formulation for the odd cycle inequalities of the stable set polytope
• Solving the stable set problem in terms of the odd cycle packing number
• Separation routine and extended formulations for the stable set problem in claw-free graphs
• Stability critical graphs and ranks facets of the stable set polytope

Cites work

• scientific article; zbMATH DE number 863479 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A simpler proof for the two disjoint odd cycles theorem
• A strongly polynomial algorithm for bimodular integer linear programming
• Compositions of Graphs and Polyhedra II: Stable Sets
• Disjunctive Programming
• Geometric random edge
• Graphs on surfaces
• Implementation of a unimodularity test
• Integer program with bimodular matrix
• Lifting linear extension complexity bounds to the mixed-integer setting
• On certain polytopes associated with graphs
• On the minors of an incidence matrix and Smith normal form
• Projective-planar signed graphs and tangled signed graphs
• Properties of vertex packing and independence system polyhedra
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• Stable sets and graphs with no even holes
• The stable set problem in graphs with bounded genus and bounded odd cycle packing number

Cited in

(8)

• Notes on \(\{a,b,c\}\)-modular matrices
• A smaller extended formulation for the odd cycle inequalities of the stable set polytope
• Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
• Stable Set Polytopes for a Class of Circulant Graphs
• On the b-Stable Set Polytope of Graphs without Bad K₄
• Solving the stable set problem in terms of the odd cycle packing number
• Polyhedral results on the stable set problem in graphs containing even or odd pairs
• An extended formulation for the 1‐wheel inequalities of the stable set polytope

Describes a project that uses

Uses Software

• Unimodularity Test
• Unimodularity

This page was built for publication: Extended formulations for stable set polytopes of graphs without two disjoint odd cycles

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