On the Combinatorial Lower Bound for the Extension Complexity of the Spanning Tree Polytope

Abstract

In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best known lower bound is the trival (dimension) bound, $\Omega (n^2)$, the best known upper bound is the extended formulation by Wong (1980) of size $O(n^3)$ (also Martin, 1991). In this note we give a nondeterministic communication protocol with cost ${\log }_2(n^2\log n)+O(1)$ for the support of the spanning tree slack matrix. This means that the combinatorial lower bounds can improve the trivial lower bound only by a factor of (at most) $O(\log n)$.

9p

References in corpus (1)

• Fooling Sets and the Spanning Tree Polytope