C&O Reading Group: Gabriel Morete

Title: Bounding the extended complexity of the stable set polytope on perfect graphs

Abstract: This week we will study the extension complexity of the stable set polytope for perfect graphs. More than 40 years ago, Grötschel et al. gave an algorithm to find maximal weight stable sets on perfect graphs based on a compact semidefinite extension. However, whether there is a compact linear extension is still an open problem. This talk will be based on the paper "On the linear extension complexity of stable set polytopes for perfect graphs" by Hu and Laurent. We will discuss an upper bound for the extension complexity of the stable set polytope based on the depth of the decomposition tree of perfect graphs.