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

DOI10.1007/S10107-021-01635-0zbMATH Open1489.90151arXiv1911.12179OpenAlexW3020834307MaRDI QIDQ2118145FDOQ2118145

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)

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$.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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

Uses Software

• Unimodularity
• Unimodularity Test

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)