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.
Extended formulations for stable set polytopes of graphs without two disjoint odd cycles / Conforti, M.; Fiorini, S.; Huynh, T.; Weltge, S.. - In: MATHEMATICAL PROGRAMMING. - ISSN 1436-4646. - (2019).
Extended formulations for stable set polytopes of graphs without two disjoint odd cycles
Huynh, T.;
2019
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.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
