Let G be a connected n-vertex graph in a proper minor-closed class G. We prove that the extension complexity of the spanning tree polytope of G is O(n3/2). This improves on the O(n²) 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(n3/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 G is a graph class closed under induced subgraphs such that all n-vertex graphs in G have balanced separators of size O(n^β), then the extension complexity of the spanning tree polytope of every connected n-vertex graph in G is O(n1+β). 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).
No takes yet. Share an insight, caveat, or question.
Aprile et al. (2021) studied this question.