Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
share
Let G be a connected n-vertex graph in a proper minor-closed class 𝒢. We prove that the extension complexity of the spanning tree polytope of G is O(n^3/2). This improves on the O(n^2) bounds following from the work of Wong (1980) and Martin (1991). It also extends a result of Fiorini, Huynh, Joret, and Pashkovich (2017), who obtained a O(n^3/2) bound for graphs embedded in a fixed surface. Our proof works more generally for all graph classes admitting strongly sublinear balanced separators: We prove that for every constant β with 0<β<1, if 𝒢 is a graph class closed under induced subgraphs such that all n-vertex graphs in 𝒢 have balanced separators of size O(n^β), then the extension complexity of the spanning tree polytope of every connected n-vertex graph in 𝒢 is O(n^1+β). We in fact give two proofs of this result, one is a direct construction of the extended formulation, the other is via communication protocols. Using the latter approach we also give a short proof of the O(n) bound for planar graphs due to Williams (2002).
READ FULL TEXT