WorksComputer Science
Steiner Tree Parameterized by Multiway Cut: Single-Exponential Time and Polynomial Space
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 , we propose a deterministic algorithm running in time and polynomial space ( vertices, non-negative -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 additional terminals and attach the remaining terminals by shortest paths. We use colour coding to optimize over the choice of these additional terminals.
Introduction
In this work, we resolve an open question of Jansen and Swennenhuis [6] by giving a polynomial-space algorithm for the Steiner Tree problem whose running time is single-exponential in the size of a multiway cut for the terminals.
In the Steiner Tree problem, the input is an undirected graph with non-negative edge weights and a set of terminals . The goal is to find a minimum-weight connected subgraph containing all vertices of . An optimum can be chosen to be a tree, called a Steiner tree for . We write , , and . This work considers non-negative integer weights represented with at most bits.
We study the Steiner Tree problem using a multiway cut for : a vertex set such that each component of contains at most one terminal. Terminals are allowed to belong to . We present an algorithm parameterized by . The size of a multiway cut can be much smaller than : in a star whose leaves are terminals, the centre vertex alone is a multiway cut.
Karp [7] proved that the Steiner Tree problem is NP-hard. The classical Dreyfus–Wagner algorithm [2] runs in time, where . Fuchs et al. [4] improve this to time for every fixed . Both algorithms use exponential space. Fomin et al. [3] combine single-exponential time in with polynomial space (see Theorem A). We use their algorithm in our approach.
Jansen and Swennenhuis [6] give an algorithm using time and polynomial space, as well as an algorithm that runs in time but uses exponential space. For each chosen set of cut vertices used by the solution, their polynomial-space algorithm enumerates connecting systems that describe how subtrees connect these vertices. Counting these systems using Cayley’s formula gives the factor. They explicitly ask whether single-exponential time and polynomial space can be achieved simultaneously [6 Section 5]. This is the main result of this work.
Theorem 1.1. There exists a deterministic algorithm that, given an undirected graph with weight function , a set of terminals , and a multiway cut for , finds a minimum-weight Steiner tree for in , if it exists, in time using polynomial space.
Since terminals may belong to a multiway cut, is a valid choice. Theorem 1.1 therefore yields a -time algorithm using polynomial space.
The algorithm of Chen, Liu, and Lu [1] requires the cut to avoid terminals. We can handle this by forming an auxiliary graph : for each terminal , add a new leaf adjacent to , and use as the new terminal set. A multiway cut for in is also a multiway cut for and may contain original terminals. Since has at most vertices, the running-time and space bounds of Chen, Liu, and Lu remain unchanged.
A minimum multiway cut can therefore be found in time and polynomial space,1 where is the minimum multiway cut size. Combining this with Theorem 1.1 gives time and polynomial space if no multiway cut is supplied.
Our approach. We build on the component decomposition of Jansen and Swennenhuis [6]. For each chosen set of cut vertices used by the solution, we reduce the optimization to choosing core terminals outside the multiway cut (Lemma 3.3), avoiding the enumeration of connecting systems. Using colour coding [5] and the reduction of Lemma 3.4, we optimize over these terminal sets without enumerating them explicitly. The resulting Steiner Tree instances have terminals and can be solved using the single-exponential-time, polynomial-space algorithm of Fomin et al. [3].
Organization. § 2 states the algorithmic ingredients. § 3 proves the selection identity and its coloured reduction. § 4 gives the algorithm and its analysis.
Preliminaries
Notation and elementary preprocessing
For a subgraph , let be the sum of its edge weights. Deleting a vertex set means taking the induced subgraph on the remaining vertices. For a weighted graph and , let be the minimum weight of a connected subgraph of that contains . If no such subgraph exists, . For , we use the convention .
We apply the following preprocessing steps. We contract all zero-weight edges and update and . We only retain a minimum-weight edge between each pair of vertices. We return if and if the terminals lie in different components of . Otherwise, we restrict to the component containing all terminals. This does not influence the possible multiway cuts. Throughout the analysis, we assume that this preprocessing has been applied; hence is connected, all edge weights are positive, and .
A polynomial-space Steiner Tree algorithm
Theorem A (Fomin et al., [3 Theorem 1]). For a connected graph with vertices, terminals, and positive integer edge weights at most , the optimum Steiner Tree value can be computed deterministically using
Theorem A gives explicit, low-degree polynomial bounds. Fomin et al. also give variants with smaller exponential bases and higher polynomial dependence [3 Theorems 2 and 3]; these also suffice for our bound. The theorem numbers for this source refer to the published SIAM version.
For a connected graph and required vertices , let be if , and the value returned by Theorem A otherwise.
Deterministic colour coding
For a positive integer , write . The following theorem is obtained by setting in the indexed splitter construction of [5] and discarding non-surjective colourings.
Theorem B (Gutin et al., [5 Theorems 4 and 24]). For , there is a deterministically enumerable family of surjective functions such that, for every -element set , some is injective on . The family can be enumerated, including initialization, in total time and polynomial space in .
This construction uses polynomial initialization and query space. We only store the current colouring. For , only the constant colouring suffices.
Structural and reduction lemmas
Definition 3.1 (Admissible set). A set is admissible if , , and all vertices of belong to one connected component of .
For an admissible set , we denote this component by and write . Thus the vertices of are required and the vertices of are forbidden.
Lemma 3.2 (Fixing the intersection with the multiway cut). We have
Proof. Every connected subgraph of containing is feasible for in , so .
Conversely, let be an optimal tree for in . Since and each component of contains at most one terminal, meets . Set . This set contains , and connects while avoiding . Thus is admissible and , giving .
For the next two lemmas, fix an admissible set . We use the notation , , , and . Since , we have . Every component of lies in a component of and therefore contains at most one vertex of . Define
All are finite. If , then .
The following selection identity builds on the component decomposition of Jansen and Swennenhuis [6 Section 2] and the counting argument in their Lemma 2.4.
Lemma 3.3 (Selection identity). For , define
Then
Proof. Fix and let be an optimal tree for in . Add a shortest path from each to . The union is connected and contains . By non-negativity, its weight is at most the sum of the weights of these parts, so
For the reverse inequality, choose an optimal tree for in with the fewest edges among all optimal trees. Then , and no proper subgraph of connects .
For each component of , let count its attachment edges to . Since is connected and , we have . Also, , so each such component contains at most one terminal of . Let and denote the components with and , respectively.
Each contains a terminal : otherwise, deleting and its only attachment edge would contradict the inclusion-minimality of . If is this attachment edge, then together with contains a path from to , so .
Delete the components in and their attachment edges, and call the remaining subgraph . It is a tree containing , since no component with only one attachment edge lies on a path between two vertices of .
Let , and let count the edges of with both endpoints in . Denote by the graph obtained from by contracting every component in to a single vertex. This tree has vertices and edges, giving
Since , we obtain . Define using the uncontracted tree . Each component in contains at most one terminal of , so .
The deleted components and their attachment edges are pairwise edge-disjoint and together with form . They contain exactly the terminals of , one per component, and each contributes at least the corresponding distance . Hence
Since connects , we have and thus . Together with (1), this proves the identity.
This lemma shows that can be obtained by minimizing the cost of a tree containing , plus a penalty for each terminal outside the tree. There exists an optimal tree that needs at most core terminals of . It is possible that, for an arbitrary choice of , an optimal tree for contains other terminals of . This bound allows us to optimize the choice of these terminals using colour coding.
Figure 1. Example with and , showing two possible choices of in . Blue edges form an optimal tree for ; dashed orange edges are shortest paths from the remaining terminals to . The value is the sum of these weights. Lemma 3.3 guarantees that some optimal choice satisfies . In panel (b), the blue and orange edges form an optimal tree . The outlined regions are the components of . Deleting the components in and their attachment edges leaves the blue tree . The choice is optimal.
Encoding a coloured selection
We use colour coding to group the non-empty sets considered in Lemma 3.3 into families that can be optimized over together. Fix and assign each terminal in one of colours, represented by a surjective function . Define
The family consists of the sets containing exactly one terminal of each colour.
For each colouring , we construct a new graph by extending . For every colour , we add a colour vertex and connect it to all terminals with . The edge receives weight , where
Let be the required vertex set in . The discount removes the contribution of a selected terminal from the baseline .
Lemma 3.4 (Coloured selection reduction). Writing , we have
Proof. Since , every new colour vertex has a neighbour in , so is connected.
We first show that the large base cost forces all new colour vertices to have degree one in every optimal tree for in .
Take a spanning tree of and attach each of the colour vertices to this tree using one of its incident edges. This gives a tree in containing with cost at most . Thus,
Suppose that an optimal Steiner tree for in uses at least new edges. Each new edge has weight at least , so
This contradicts . Every colour vertex needs an incident edge, so uses exactly new edges and every has degree one in .
Let be the neighbour of in . Since for every , these vertices have different colours and are therefore distinct. Hence belongs to . Removing the colour leaves from yields a tree in containing . Therefore,
Thus is at least the minimum on the right-hand side of the claimed identity.
Conversely, take any and an optimal tree for in . For each , let be the unique terminal in with colour . Attach to the tree by adding only the edge from . This gives a tree in containing , of weight
Taking the minimum over gives the reverse inequality.
The algorithm and its analysis
Computing the optimum value
This section describes the algorithm . Every call to first applies the preprocessing from § 2.1; Algorithm 1 describes the remaining case. It uses as defined in § 2.2. Use the families from § 2.3, identifying with .
Algorithm 1.
Input: A weighted graph , terminals , and a multiway cut . Output: , or if infeasible.
best ← +∞
for each admissible set U ⊆ S, enumerated one at a time, do
Construct J = J_U; set p = |U|, R = K \ S, and r = |R|
Compute d_t for all t ∈ R, and B, D, Λ
best ← min{best, B + STVal(J, U)} (the ℓ = 0 case)
for ℓ = 1, …, min(p − 1, r) do
M ← Λ + (ℓ + 1)D + 1
for each h ∈ 𝓗_{r,ℓ} do
Construct (J′, Q) as in Lemma 3.4
F ← STVal(J′, Q)
best ← min{best, B + F − ℓM}
end for
end for
end for
return best
Correctness
Proposition 4.1. The procedure returns if a Steiner tree for in exists, and otherwise.
Proof. The preprocessing from § 2.1 handles the trivial and infeasible cases and preserves the optimum otherwise. Consider a non-trivial instance. Fix an admissible and let be the minimum candidate generated for .
The candidate is . For every pair with , Lemmas 3.4 and 3.3 give
Hence .
By Lemma 3.3, some satisfies and . If , equality is attained by the candidate. Otherwise, take . Theorem B (or the constant colouring for ) provides at least one colouring that is injective on . Since , we have , and hence . The candidate for therefore satisfies
Together with , this proves .
It follows from Lemma 3.2 that the returned value is
Running time
The preprocessing takes polynomial time. Consider an instance with . For each of the choices of , checking admissibility and, if is admissible, constructing and computing distances to in take polynomial time. There is one solver call for .
For fixed , enumerating , including initialization, takes time (§ 2.3). Each colouring requires one solver call.
To bound the cost of each solver call, define
For an admissible and , constructing from adds colour vertices and one new edge for each . Since ,
Since and , every new edge has weight at most , where
This bound has bits. Constructing therefore takes polynomial time in and . Theorem A bounds every solver call by
Combining these bounds, the overall running time is bounded by
Polynomial factors in are absorbed into , since .
Polynomial space
Since and , all stored distances and finite costs, including , , , and , have bits. Table 1 lists the data stored during one iteration.
| Stored data | Bit-space bound |
| Graphs , , and the current | |
| Set and loop counters | |
| One colouring | |
| Distances, scalar costs, and running minimum | |
| Splitter | |
| One active call to Theorem A |
Table 1. Storage used by the current iteration and one active solver call. The polynomial bounds the space used by the splitter construction in § 2.3.
The current set uses bits. The indexed generator of Theorem B uses polynomial initialization and query space, with bits for its current index. Only one colouring is stored during its solver call. Checking that all colours occur uses additional bits.
Summing the storage used simultaneously gives
The degrees of these polynomial bounds are independent of .
Recovering an optimal tree
Let , , denote the original feasible instance with , before preprocessing. Set and . Process each original edge once, deleting it from if . An infeasible call returns , so the edge is retained.
The deletions preserve the optimum . Any edge outside an optimal tree of the final graph would have been deleted when tested, since this tree was already feasible then. Thus, after discarding isolated non-terminals, the final graph is a tree with .
Edge deletion preserves as a multiway cut. Reconstruction makes at most additional calls to and reuses the same workspace. Thus the time bound of and the space bound of remain, proving Theorem 1.1.
Conclusion
This paper answers the question of Jansen and Swennenhuis by giving an algorithm for Steiner Tree that runs in poly time and polynomial space, where is the size of a multiway cut for the terminals. The selection identity reduces the optimization for each admissible to choosing at most core terminals outside the multiway cut. Using colour coding and the weighted reduction, we optimize over these choices without enumerating all such sets explicitly.
A further question is whether a poly-time algorithm exists for Steiner Tree. Such an algorithm would contradict the Exponential Time Hypothesis: taking would yield a poly-time algorithm, contrary to the known ETH-based lower bound [8 Theorem I.2]. The recent proposed refutation of ETH [9] gives motivation to investigate this question, although the exponential factors in our algorithm suggest that a different approach may be needed.
Use of generative AI
GPT-Astra (OpenAI) was asked to work on the open question posed by Jansen and Swennenhuis [6]. The model contributed substantially to the development of the algorithm and the proofs through an iterative dialogue with the first author. It was also used extensively to improve the exposition by rewriting and clarifying the mathematical arguments. The authors take full responsibility for the content of the paper.
References
- [1]Jianer Chen, Yang Liu, and Songjian Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 55(1):1–13, 2009. doi:10.1007/s00453-007-9130-6.
- [2]Stuart E. Dreyfus and Robert A. Wagner. The Steiner problem in graphs. Networks, 1(3):195–207, 1971. doi:10.1002/net.3230010302.DOI
- [3]Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Parameterized single-exponential time polynomial space algorithm for Steiner Tree. SIAM Journal on Discrete Mathematics, 33(1):327–345, 2019. doi:10.1137/17M1140030.DOI
- [4]Bernhard Fuchs, Walter Kern, Daniel Mölle, Stefan Richter, Peter Rossmanith, and Xinhui Wang. Dynamic programming for minimum Steiner trees. Theory of Computing Systems, 41(3):493–500, 2007. doi:10.1007/s00224-007-1324-4.DOI
- [5]Gregory Gutin, Felix Reidl, Magnus Wahlström, and Meirav Zehavi. Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials. Journal of Computer and System Sciences, 95:69–85, 2018. Theorem numbering refers to the full version, arXiv:1706.03698v2. URL: https://arxiv.org/abs/1706.03698v2.
- [6]Bart M. P. Jansen and Céline M. F. Swennenhuis. Steiner Tree parameterized by multiway cut and even less. In 32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 of Leibniz International Proceedings in Informatics (LIPIcs), pages 76:1–76:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ESA.2024.76.DOI
- [7]Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Plenum Press, 1972. doi:10.1007/978-1-4684-2001-2_9.DOI
- [8]Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk. On subexponential parameterized algorithms for Steiner Tree and directed subset TSP on planar graphs. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 474–484. IEEE, 2018. URL: https://ieee-focs.org/FOCS-2018-Papers/pdfs/59f474.pdf, doi:10.1109/FOCS.2018.00052.DOI
- [9]OpenAI. The Exponential Time Hypothesis is False. OpenAI Math Release preprint, 2026. Dated October 25, 2026. URL: https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf.hub.valency.io/works/W_h8uqubsk
