Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-genus Graphs

Abstract

We give an $O(g^{1/2}{n}^{3/2}+g^{3/2}{n}^{1/2})$-size extended formulation for the spanning tree polytope of an $n$-vertex graph embedded on a surface of genus $g$, improving on the known $O(n^2+gn)$-size extended formulations following from Wong and Martin.

v3: fixed some typos

References in corpus (1)

• Extension Complexity, MSO Logic, and Treewidth

Cited by in corpus (3)

• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Fooling Sets and the Spanning Tree Polytope
• On the Combinatorial Lower Bound for the Extension Complexity of the Spanning Tree Polytope