(Approximate) Symmetric Extension Complexity of the Spanning Tree Polytope
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\ge13$, 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 \[ \operatorname{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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.17017
curl -X POST /api/v1/records/arxiv/2606.17017/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.17017/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'