In the Steiner Tree problem, we are given a weighted undirected graph and a set of terminals; the goal is to find a minimum‑weight tree that spans all terminals. When a multiway cut of size $s$ is provided (i.e., removing this vertex set leaves each connected component with at most one terminal), we present a deterministic algorithm running in $2^{O(s)}\operatorname{poly}(n,b)$ time and using only polynomial space (here $n$ is the number of vertices and $b$ the bit‑length of the non‑negative integer weights).
A multiway cut for a terminal set $T$ is a vertex subset $C\subseteq V$ such that every component of $G\setminus C$ contains at most one vertex of $T$. This notion appeared in the work of Jansen and Swennenhuis (ESA 2024); our result directly answers the open question they raised.
The main idea builds on their component decomposition: after deleting the cut vertices, the graph splits into components each holding at most one terminal. It then suffices to connect the cut vertices together with $O(s)$ additional “pseudo‑terminals” and attach the original terminals via shortest paths. The challenge is to choose those $O(s)$ pseudo‑terminals efficiently. We employ colour‑coding to enumerate all possible selections in a controlled exponential fashion, achieving a single‑exponential dependence on $s$.
Algorithm sketch:
- Given the multiway cut $C$, compute shortest‑path distances from each cut vertex to every terminal.
- Apply colour‑coding to assign colours to cut vertices and enumerate all colour‑combinations that correspond to a set of $O(s)$ pseudo‑terminals.
- For each combination, build the subgraph consisting of cut vertices, pseudo‑terminals, and terminals connected by their shortest paths, and test whether it forms a connected Steiner tree.
- Keep the minimum‑weight feasible solution as the optimal Steiner tree.
The algorithm uses only polynomial space because all intermediate structures can be stored in $O(n)$ memory, and the dynamic programming table for colour‑coding occupies $2^{O(s)}$ space.
Review: This work advances the parameterized complexity of Steiner Tree by exploiting the size of a multiway cut as a parameter, achieving single‑exponential time while preserving polynomial space, and showcases the power of colour‑coding in graph‑based optimization.