Extended formulations for stable set polytopes of graphs without two disjoint odd cycles
成果类型：
Article
署名作者：
Conforti, Michele; Fiorini, Samuel; Huynh, Tony; Weltge, Stefan
署名单位：
University of Padua; Universite Libre de Bruxelles; Monash University; Technical University of Munich
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-021-01635-0
发表日期：
2022
页码：
547-566
关键词：
摘要：
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.