2026-07-21T14:13:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15401 2024-03-12T12:00:23Z ddc:004 open_access

On Extended Formulations For Parameterized Steiner Trees Feldmann, Andreas Emil Rai, Ashutosh Steiner trees integral linear program extension complexity fixed-parameter tractability 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)}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Emil Feldmann and Ashutosh Rai 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.18 urn:nbn:de:0030-drops-154010 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.18 eng https://creativecommons.org/licenses/by/4.0/legalcode