Skip to content
Preprint

Steiner Tree Parameterized by Multiway Cut: Single-Exponential Time and Polynomial Space

Oct 2026 · 0 citations · 9 references
Computer Science

Abstract

In the Steiner Tree problem, the goal is to find a minimum-weight tree containing a given set of terminals in an edge-weighted graph. Given a multiway cut of size $s$, we propose a deterministic algorithm running in $2^{O(s)}\operatorname{poly}(n,b)$ time and polynomial space ($n$ vertices, non-negative $b$-bit integer weights). A multiway cut for the terminals is a set of vertices whose deletion leaves at most one terminal in each connected component. This result answers a question of Jansen and Swennenhuis (ESA 2024). Building on their component decomposition, we show that it suffices to connect the selected cut vertices together with $O(s)$ additional terminals and attach the remaining terminals by shortest paths. We use colour coding to optimize over the choice of these additional terminals.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.