Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond (Q2121739)

Summary: Let \(G\) be a connected \(n\)-vertex graph in a proper minor-closed class \(\mathcal G\). 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 \textit{R. T. Wong} [``Integer programming formulations of the traveling salesman problem'', in: Proceedings of the IEEE international conference of circuits and computers. Piscataway, NJ: IEEE Press. 149--152 (1980)] and \textit{R. K. Martin} [Oper. Res. Lett. 10, No. 3, 119--128 (1991; Zbl 0747.90071)]. It also extends a result of \textit{S. Fiorini} et al. [Discrete Comput. Geom. 57, No. 3, 757--761 (2017; Zbl 1366.52010)], 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 \(\beta\) with \(0<\beta<1\), if \(\mathcal G\) is a graph class closed under induced subgraphs such that all \(n\)-vertex graphs in \(\mathcal G\) have balanced separators of size \(O(n^\beta)\), then the extension complexity of the spanning tree polytope of every connected \(n\)-vertex graph in \(\mathcal{G}\) is \(O(n^{1+\beta})\). 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 \textit{J. C. Williams} [Networks 39, No. 1, 53--60 (2002; Zbl 1014.90103)].