(Approximate) Symmetric Extension Complexity of the Spanning Tree Polytope
Abstract
We prove a tight lower bound on symmetric LP formulations for the spanning tree polytope of the complete graph. More precisely, let PST(Kn) be the spanning tree polytope of Kn. We show that, for all n≥13, every symmetric extended formulation for PST(Kn) has at least binom n3 inequalities. Since the classical Martin formulation has a symmetric formulation of size O(n3), this gives xcs(PST(Kn))=Θ(n3). We also study outer relaxations of the spanning tree polytope of Kn for maximization with nonnegative edge weights. We show that for every fixed approximation factor below 3/2, symmetric LP formulations still require Θ(n3) inequalities for all sufficiently large n, whereas factor 3/2 admits a formulation of size O(n2). Moreover, we provide an exact symmetric SDP formulation of size O(n2), measured by PSD matrix order, which implies xcpsd(PST(Kn))= Θ(n2). Thus symmetric LP and SDP sizes already differ for exact formulations, and for every fixed approximation factor 1≤β<3/2 for all sufficiently large n.
Related
- Fine asymptotics for approximate simulation of symmetric channels
- Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
- A symmetric extension of Zhao's series for ζ(5)
- Conservative CSPs in Logspace are in Symmetric Linear Datalog (under complexity theoretic assumptions)
- A Scale-Critical μ<3/8 Extension Principle for Spherically Symmetric Einstein-Scalar Field System
BibTeX
@misc{pokutta2026approximate,
title = {{(Approximate) Symmetric Extension Complexity of the Spanning Tree Polytope}},
author = {Sebastian Pokutta},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.17017},
eprint = {2606.17017},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.17017},
}
RIS
TY - UNPB
TI - (Approximate) Symmetric Extension Complexity of the Spanning Tree Polytope
AU - Sebastian Pokutta
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2606.17017
UR - https://arxiv.org/abs/2606.17017
AB - We prove a tight lower bound on symmetric LP formulations for the spanning tree polytope of the complete graph. More precisely, let P_ST(K_n) be the spanning tree polytope of K_n. We show that, for all n≥13, every symmetric extended formulation for P_ST(K_n) has at least binom n3 inequalities. Since the classical Martin formulation has a symmetric formulation of size O(n^3), this gives xcs(P_ST(K_n))=Θ(n^3). We also study outer relaxations of the spanning tree polytope of K_n for maximization with nonnegative edge weights. We show that for every fixed approximation factor below 3/2, symmetric LP formulations still require Θ(n^3) inequalities for all sufficiently large n, whereas factor 3/2 admits a formulation of size O(n^2). Moreover, we provide an exact symmetric SDP formulation of size O(n^2), measured by PSD matrix order, which implies xc_psd(P_ST(K_n))= Θ(n^2). Thus symmetric LP and SDP sizes already differ for exact formulations, and for every fixed approximation factor 1≤β<3/2 for all sufficiently large n.
ER -