On Extended Formulations For Parameterized Steiner Trees

We present a novel linear program (LP) for the Steiner Tree problem, where a set of terminal vertices needs to be connected by a minimum weight tree in a graph G = (V,E) with non-negative edge weights. This well-studied problem is NP-hard and therefore does not have a compact extended formulation (describing the convex hull of all Steiner trees) of polynomial size, unless P=NP. On the other hand, Steiner Tree is fixed-parameter tractable (FPT) when parameterized by the number k of terminals, and can be solved in O(3^k|V|+2^k|V|²) time via the Dreyfus-Wagner algorithm. A natural question thus is whether the Steiner Tree problem admits an extended formulation of comparable size. We first answer this in the negative by proving a lower bound on the extension complexity of the Steiner Tree polytope, which, for some constant c > 0, implies that no extended formulation of size f(k)2^{cn} exists for any function f. However, we are able to circumvent this lower bound due to the fact that the edge weights are non-negative: we prove that Steiner Tree admits an integral LP with O(3^k|E|) variables and constraints. The size of our LP matches the runtime of the Dreyfus-Wagner algorithm, and our poof gives a polyhedral perspective on this classic algorithm. Our proof is simple, and additionally improves on a previous result by Siebert et al. [2018], who gave an integral LP of size O((2k/e)^k)|V|^{O(1)}.