betaFeedback

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 ss, we propose a deterministic algorithm running in 2O(s)poly⁡(n,b)2^{O(s)}\operatorname{poly}(n,b) time and polynomial space (nn vertices, non-negative bb-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)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.

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 G=(V,E)G=(V,E) with non-negative edge weights and a set of terminals K⊆VK \subseteq V. The goal is to find a minimum-weight connected subgraph containing all vertices of KK. An optimum can be chosen to be a tree, called a Steiner tree for KK. We write n=∣V∣n=|V|, m=∣E∣m=|E|, and k=∣K∣k=|K|. This work considers non-negative integer weights represented with at most b≥1b \ge1 bits.

We study the Steiner Tree problem using a multiway cut SS for KK: a vertex set S⊆VS \subseteq V such that each component of G−SG-S contains at most one terminal. Terminals are allowed to belong to SS. We present an algorithm parameterized by s=∣S∣s=|S|. The size of a multiway cut can be much smaller than ∣K∣|K|: 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 3kpoly⁡(n,b)3^k\operatorname{poly}(n,b) time, where k=∣K∣k=|K|. Fuchs et al. [4] improve this to (2+ε)kpoly⁡ε(n,b)(2+\varepsilon)^k\operatorname{poly}_{\varepsilon}(n,b) time for every fixed ε>0\varepsilon>0. Both algorithms use exponential space. Fomin et al. [3] combine single-exponential time in kk with polynomial space (see Theorem A). We use their algorithm in our approach.

Jansen and Swennenhuis [6] give an algorithm using 2O(slog⁡s)poly⁡(n,b)2^{O(s\log s)}\operatorname{poly}(n,b) time and polynomial space, as well as an algorithm that runs in 2O(s)poly⁡(n,b)2^{O(s)}\operatorname{poly}(n,b) 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 2O(slog⁡s)2^{O(s\log s)} 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 G=(V,E)G=(V,E) with weight function w:E→N0w:E\to\mathbb{N}_0, a set of terminals K⊆VK\subseteq V, and a multiway cut SS for KK, finds a minimum-weight Steiner tree for KK in GG, if it exists, in 2O(s)poly⁡(n,b)2^{O(s)}\operatorname{poly}(n,b) time using polynomial space.

Since terminals may belong to a multiway cut, S=KS=K is a valid choice. Theorem 1.1 therefore yields a 2O(k)poly⁡(n,b)2^{O(k)}\operatorname{poly}(n,b)-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 G+G^+: for each terminal t∈Kt\in K, add a new leaf t′t' adjacent to tt, and use K′={t′:t∈K}K'=\{t':t\in K\} as the new terminal set. A multiway cut for K′K' in G+G^+ is also a multiway cut for KK and may contain original terminals. Since G+G^+ has at most 2n2n vertices, the running-time and space bounds of Chen, Liu, and Lu remain unchanged.

A minimum multiway cut can therefore be found in 4σpoly⁡(n)4^\sigma\operatorname{poly}(n) time and polynomial space,1 where σ\sigma is the minimum multiway cut size. Combining this with Theorem 1.1 gives 2O(σ)poly⁡(n,b)2^{O(\sigma)}\operatorname{poly}(n,b) 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 O(s)O(s) 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 O(s)O(s) 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 XX, let w(X)w(X) be the sum of its edge weights. Deleting a vertex set means taking the induced subgraph on the remaining vertices. For a weighted graph XX and Q⊆V(X)Q\subseteq V(X), let OPT⁡(X,Q)\operatorname{OPT}(X,Q) be the minimum weight of a connected subgraph of XX that contains QQ. If no such subgraph exists, OPT⁡(X,Q)=+∞\operatorname{OPT}(X,Q)=+\infty. For ∣Q∣≤1|Q|\leq1, we use the convention OPT⁡(X,Q)=0\operatorname{OPT}(X,Q)=0.

We apply the following preprocessing steps. We contract all zero-weight edges and update KK and SS. We only retain a minimum-weight edge between each pair of vertices. We return 00 if ∣K∣≤1|K|\leq1 and +∞+\infty if the terminals lie in different components of GG. 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 GG is connected, all edge weights are positive, and ∣K∣≥2|K|\geq2.

A polynomial-space Steiner Tree algorithm

Theorem A (Fomin et al., [3 Theorem 1]). For a connected graph with NN vertices, q≥2q\geq2 terminals, and positive integer edge weights at most WW, the optimum Steiner Tree value can be computed deterministically using

O(7.97qN4log⁡(NW)) time and O(N3log⁡(NW)log⁡q) space.O\left(7.97^{q}N^4\log(NW)\right)\text{ time and }O\left(N^3\log(NW)\log q\right)\text{ space}.

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 2O(s)poly⁡(n,b)2^{O(s)}\operatorname{poly}(n,b) bound. The theorem numbers for this source refer to the published SIAM version.

For a connected graph XX and required vertices QQ, let STVal⁡(X,Q)\operatorname{STVal}(X,Q) be 00 if ∣Q∣≤1|Q|\leq1, and the value returned by Theorem A otherwise.

Deterministic colour coding

For a positive integer aa, write [a]={1,…,a}[a] = \{1,\ldots,a\}. The following theorem is obtained by setting α=1\alpha= 1 in the indexed splitter construction of [5] and discarding non-surjective colourings.

Theorem B (Gutin et al., [5 Theorems 4 and 24]). For 2≤ℓ≤r2 \le\ell\le r, there is a deterministically enumerable family Hr,ℓ\mathcal{H}_{r,\ell} of surjective functions h:[r]→[ℓ]h : [r] \to[\ell] such that, for every ℓ\ell-element set A⊆[r]A \subseteq[r], some h∈Hr,ℓh \in\mathcal{H}_{r,\ell} is injective on AA. The family can be enumerated, including initialization, in total time 2O(ℓ)poly⁡(r)2^{O(\ell)}\operatorname{poly}(r) and polynomial space in rr.

This construction uses polynomial initialization and query space. We only store the current colouring. For ℓ=1\ell= 1, only the constant colouring h(t)=1h(t) = 1 suffices.

Structural and reduction lemmas

Definition 3.1 (Admissible set). A set U⊆SU \subseteq S is admissible if U≠∅U \ne\varnothing, K∩S⊆UK \cap S \subseteq U, and all vertices of K∪UK \cup U belong to one connected component of G−(S∖U)G - (S \setminus U).

For an admissible set UU, we denote this component by JUJ_U and write OPT⁡U=OPT⁡(JU,K∪U)\operatorname{OPT}_U = \operatorname{OPT}(J_U, K \cup U). Thus the vertices of UU are required and the vertices of S∖US \setminus U are forbidden.

Lemma 3.2 (Fixing the intersection with the multiway cut). We have

OPT⁡(G,K)=min⁡U admissibleOPT⁡U.\operatorname{OPT}(G,K)=\min_{U\ \mathrm{admissible}}\operatorname{OPT}_U.

Proof. Every connected subgraph of JUJ_U containing K∪UK \cup U is feasible for KK in GG, so OPT⁡(G,K)≤OPT⁡U\operatorname{OPT}(G,K) \le\operatorname{OPT}_U.

Conversely, let TT be an optimal tree for KK in GG. Since ∣K∣≥2|K| \ge2 and each component of G−SG-S contains at most one terminal, TT meets SS. Set U=V(T)∩SU = V(T) \cap S. This set contains K∩SK \cap S, and TT connects K∪UK \cup U while avoiding S∖US \setminus U. Thus UU is admissible and T⊆JUT \subseteq J_U, giving OPT⁡U≤w(T)=OPT⁡(G,K)\operatorname{OPT}_U \le w(T) = \operatorname{OPT}(G,K).

For the next two lemmas, fix an admissible set UU. We use the notation J=JUJ = J_U, p=∣U∣p = |U|, R=K∖SR = K \setminus S, and r=∣R∣r = |R|. Since K∩S⊆UK \cap S \subseteq U, we have R∪U=K∪UR \cup U = K \cup U. Every component of J−UJ-U lies in a component of G−SG-S and therefore contains at most one vertex of RR. Define

dt=dist⁡J(t,U)(t∈R),B=∑t∈Rdt,D=max⁡({0}∪{dt:t∈R}).d_t = \operatorname{dist}_J(t,U) \quad(t \in R), \qquad B = \sum_{t \in R} d_t, \qquad D = \max\bigl(\{0\} \cup\{d_t : t \in R\}\bigr).

All dtd_t are finite. If R=∅R = \varnothing, then B=D=0B = D = 0.

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 A⊆RA \subseteq R, define

Φ(A)=B+OPT⁡(J,U∪A)−∑t∈Adt=OPT⁡(J,U∪A)+∑t∈R∖Adt.\Phi(A) = B + \operatorname{OPT}(J,U \cup A) - \sum_{t \in A} d_t = \operatorname{OPT}(J,U \cup A) + \sum_{t \in R \setminus A} d_t.

Then

OPT⁡U=min⁡A⊆R∣A∣≤p−1Φ(A).\operatorname{OPT}_U = \min_{\substack{A \subseteq R\\ |A| \le p-1}} \Phi(A).

Proof. Fix A⊆RA \subseteq R and let XX be an optimal tree for U∪AU \cup A in JJ. Add a shortest path from each t∈R∖At \in R \setminus A to UU. The union is connected and contains R∪U=K∪UR \cup U = K \cup U. By non-negativity, its weight is at most the sum of the weights of these parts, so

OPT⁡U≤w(X)+∑t∈R∖Adt=Φ(A).(1)\operatorname{OPT}_U \le w(X) + \sum_{t \in R \setminus A} d_t = \Phi(A). \tag*{(1)}

For the reverse inequality, choose an optimal tree TT for K∪UK \cup U in JJ with the fewest edges among all optimal trees. Then w(T)=OPT⁡Uw(T) = \operatorname{OPT}_U, and no proper subgraph of TT connects K∪UK \cup U.

For each component CC of T−UT-U, let aCa_C count its attachment edges to UU. Since TT is connected and U≠∅U \ne\varnothing, we have aC≥1a_C \ge1. Also, T⊆JT \subseteq J, so each such component contains at most one terminal of RR. Let C1C_1 and C≥2C_{\ge2} denote the components with aC=1a_C = 1 and aC≥2a_C \ge2, respectively.

Each C∈C1C \in\mathcal{C}_1 contains a terminal t∈Rt \in R: otherwise, deleting CC and its only attachment edge would contradict the inclusion-minimality of TT. If eCe_C is this attachment edge, then CC together with eCe_C contains a path from tt to UU, so w(C)+w(eC)≥dtw(C) + w(e_C) \ge d_t.

Delete the components in C1\mathcal{C}_1 and their attachment edges, and call the remaining subgraph HH. It is a tree containing UU, since no component with only one attachment edge lies on a path between two vertices of UU.

Let c=∣C≥2∣c = |\mathcal{C}_{\ge2}|, and let eUe_U count the edges of TT with both endpoints in UU. Denote by HcontrH^{\mathrm{contr}} the graph obtained from HH by contracting every component in C≥2\mathcal{C}_{\ge2} to a single vertex. This tree has p+cp + c vertices and p+c−1p + c - 1 edges, giving

2c+eU≤∑C∈C≥2aC+eU=p+c−1.2c + e_U \le\sum_{C \in\mathcal{C}_{\ge2}} a_C + e_U = p + c - 1.

Since eU≥0e_U \ge0, we obtain c≤p−1c \le p - 1. Define A=V(H)∩RA = V(H) \cap R using the uncontracted tree HH. Each component in C≥2\mathcal{C}_{\ge2} contains at most one terminal of RR, so ∣A∣≤c≤p−1|A| \le c \le p - 1.

The deleted components and their attachment edges are pairwise edge-disjoint and together with HH form TT. They contain exactly the terminals of R∖AR \setminus A, one per component, and each contributes at least the corresponding distance dtd_t. Hence

w(H)+∑t∈R∖Adt≤w(T)=OPTU.w(H) + \sum_{t \in R \setminus A} d_t \le w(T) = \mathrm{OPT}_U.

Since HH connects U∪AU \cup A, we have OPT(J,U∪A)≤w(H)\mathrm{OPT}(J,U \cup A) \le w(H) and thus Φ(A)≤OPTU\Phi(A) \le\mathrm{OPT}_U. Together with (1), this proves the identity.

This lemma shows that OPTU\mathrm{OPT}_U can be obtained by minimizing the cost of a tree containing UU, plus a penalty dtd_t for each terminal t∈Rt \in R outside the tree. There exists an optimal tree that needs at most p−1p - 1 core terminals of RR. It is possible that, for an arbitrary choice of AA, an optimal tree for U∪AU \cup A contains other terminals of R∖AR \setminus A. This bound allows us to optimize the choice of these terminals using colour coding.

Figure 1. Example with K={t1,…,t5}K = \{t_1,\ldots,t_5\} and U={u1,u2,u3}U = \{u_1,u_2,u_3\}, showing two possible choices of AA in JUJ_U. Blue edges form an optimal tree for U∪AU \cup A; dashed orange edges are shortest paths from the remaining terminals to UU. The value Φ(A)\Phi(A) is the sum of these weights. Lemma 3.3 guarantees that some optimal choice satisfies ∣A∣≤p−1|A| \le p - 1. In panel (b), the blue and orange edges form an optimal tree TT. The outlined regions are the components of T−UT - U. Deleting the components in C1\mathcal{C}_1 and their attachment edges leaves the blue tree HH. The choice A2A_2 is optimal.

Encoding a coloured selection

We use colour coding to group the non-empty sets AA considered in Lemma 3.3 into families that can be optimized over together. Fix 1≤ℓ≤min⁡(p−1,r)1 \le\ell\le\min(p - 1, r) and assign each terminal in RR one of ℓ\ell colours, represented by a surjective function h:R→[ℓ]h : R \to[\ell]. Define

F(h)={A⊆R:∣A∣=ℓ and h(A)=[ℓ]}.\mathcal{F}(h) = \{ A \subseteq R : |A| = \ell\text{ and } h(A) = [\ell] \}.

The family F(h)\mathcal{F}(h) consists of the sets AA containing exactly one terminal of each colour.

For each colouring hh, we construct a new graph J′J' by extending JJ. For every colour i∈[ℓ]i \in[\ell], we add a colour vertex ziz_i and connect it to all terminals t∈Rt \in R with h(t)=ih(t) = i. The edge zitz_i t receives weight M−dtM - d_t, where

M=Λ+(ℓ+1)D+1,Λ=∑e∈E(J)w(e).M = \Lambda+ (\ell+ 1)D + 1, \qquad\Lambda= \sum_{e \in E(J)} w(e).

Let Q=U∪{zi:i∈[ℓ]}Q = U \cup\{z_i : i \in[\ell]\} be the required vertex set in J′J'. The discount dtd_t removes the contribution of a selected terminal from the baseline BB.

Lemma 3.4 (Coloured selection reduction). Writing F=OPT⁡(J′,Q)F = \operatorname{OPT}(J', Q), we have

F−ℓM=min⁡A∈F(h)[OPT⁡(J,U∪A)−∑t∈Adt].F - \ell M = \min_{A \in\mathcal{F}(h)} \left[ \operatorname{OPT}(J, U \cup A) - \sum_{t \in A} d_t \right].

Proof. Since h(R)=[ℓ]h(R) = [\ell], every new colour vertex has a neighbour in JJ, so J′J' is connected.

We first show that the large base cost MM forces all new colour vertices to have degree one in every optimal tree for QQ in J′J'.

Take a spanning tree of JJ and attach each of the ℓ\ell colour vertices to this tree using one of its incident edges. This gives a tree in J′J' containing QQ with cost at most Λ+ℓM\Lambda+ \ell M. Thus,

F≤Λ+ℓM.F \le\Lambda+ \ell M.

Suppose that an optimal Steiner tree T′T' for QQ in J′J' uses at least ℓ+1\ell+ 1 new edges. Each new edge has weight at least M−DM - D, so

w(T′)≥(ℓ+1)(M−D)=ℓM+Λ+1>ℓM+Λ≥F.w(T') \ge(\ell+ 1)(M - D) = \ell M + \Lambda+ 1 > \ell M + \Lambda\ge F.

This contradicts w(T′)=Fw(T') = F. Every colour vertex needs an incident edge, so T′T' uses exactly ℓ\ell new edges and every ziz_i has degree one in T′T'.

Let tit_i be the neighbour of ziz_i in T′T'. Since h(ti)=ih(t_i) = i for every i∈[ℓ]i \in[\ell], these vertices have different colours and are therefore distinct. Hence A={ti:i∈[ℓ]}A = \{t_i : i \in[\ell]\} belongs to F(h)\mathcal{F}(h). Removing the colour leaves from T′T' yields a tree XX in JJ containing U∪AU \cup A. Therefore,

F=w(X)+ℓM−∑t∈Adt≥OPT⁡(J,U∪A)+ℓM−∑t∈Adt.\begin{aligned} F = w(X) + \ell M - \sum_{t \in A} d_t \\ &\ge\operatorname{OPT}(J, U \cup A) + \ell M - \sum_{t \in A} d_t. \end{aligned}

Thus F−ℓMF - \ell M is at least the minimum on the right-hand side of the claimed identity.

Conversely, take any A∈F(h)A \in\mathcal{F}(h) and an optimal tree for U∪AU \cup A in JJ. For each i∈[ℓ]i \in[\ell], let tit_i be the unique terminal in AA with colour ii. Attach ziz_i to the tree by adding only the edge zitiz_i t_i from J′J'. This gives a tree in J′J' containing QQ, of weight

OPT⁡(J,U∪A)+ℓM−∑t∈Adt.\operatorname{OPT}(J, U \cup A) + \ell M - \sum_{t \in A} d_t.

Taking the minimum over A∈F(h)A \in\mathcal{F}(h) gives the reverse inequality.

The algorithm and its analysis

Computing the optimum value

This section describes the algorithm ST⁡(G,K,S)\operatorname{ST}(G, K, S). Every call to ST⁡\operatorname{ST} first applies the preprocessing from § 2.1; Algorithm 1 describes the remaining case. It uses STVal⁡\operatorname{STVal} as defined in § 2.2. Use the families Hr,ℓ\mathcal{H}_{r,\ell} from § 2.3, identifying RR with [r][r].

Algorithm 1. ST⁡(G,K,S)\operatorname{ST}(G,K,S)

Input: A weighted graph GG, terminals KK, and a multiway cut SS. Output: OPT⁡(G,K)\operatorname{OPT}(G,K), or +∞+\infty 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 ST⁡(G,K,S)\operatorname{ST}(G,K,S) returns OPT⁡(G,K)\operatorname{OPT}(G,K) if a Steiner tree for KK in GG exists, and +∞+\infty 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 UU and let bUb_U be the minimum candidate generated for UU.

The ℓ=0\ell=0 candidate is Φ(∅)≥OPT⁡U\Phi(\emptyset) \ge\operatorname{OPT}_U. For every pair (ℓ,h)(\ell,h) with ℓ>0\ell>0, Lemmas 3.4 and 3.3 give

B+F−ℓM=min⁡A∈F(h)Φ(A)≥OPT⁡U.B+F-\ell M=\min_{A\in\mathcal{F}(h)}\Phi(A)\ge\operatorname{OPT}_U.

Hence bU≥OPT⁡Ub_U \ge\operatorname{OPT}_U.

By Lemma 3.3, some A∗⊆RA^* \subseteq R satisfies ∣A∗∣≤p−1|A^*|\le p-1 and Φ(A∗)=OPT⁡U\Phi(A^*)=\operatorname{OPT}_U. If A∗=∅A^*=\emptyset, equality is attained by the ℓ=0\ell=0 candidate. Otherwise, take ℓ=∣A∗∣\ell=|A^*|. Theorem B (or the constant colouring for ℓ=1\ell=1) provides at least one colouring h∗h^* that is injective on A∗A^*. Since ∣A∗∣=ℓ|A^*|=\ell, we have h∗(A∗)=[ℓ]h^*(A^*)=[\ell], and hence A∗∈F(h∗)A^*\in\mathcal{F}(h^*). The candidate for h∗h^* therefore satisfies

B+F−ℓM=min⁡A∈F(h∗)Φ(A)≤Φ(A∗)=OPT⁡U.B+F-\ell M=\min_{A\in\mathcal{F}(h^*)}\Phi(A)\le\Phi(A^*)=\operatorname{OPT}_U.

Together with bU≥OPT⁡Ub_U\ge\operatorname{OPT}_U, this proves bU=OPT⁡Ub_U=\operatorname{OPT}_U.

It follows from Lemma 3.2 that the returned value is

min⁡U admissiblebU=min⁡U admissibleOPT⁡U=OPT⁡(G,K).\min_{U\ \mathrm{admissible}} b_U = \min_{U\ \mathrm{admissible}} \operatorname{OPT}_U = \operatorname{OPT}(G,K).

Running time

The preprocessing takes polynomial time. Consider an instance with s≥1s\ge1. For each of the 2s2^s choices of U⊆SU\subseteq S, checking admissibility and, if UU is admissible, constructing JUJ_U and computing distances to UU in JUJ_U take polynomial time. There is one solver call for ℓ=0\ell=0.

For fixed ℓ>0\ell>0, enumerating Hr,ℓ\mathcal{H}_{r,\ell}, including initialization, takes 2O(ℓ)poly⁡(n)2^{O(\ell)}\operatorname{poly}(n) time (§ 2.3). Each colouring requires one solver call.

To bound the cost of each solver call, define

W=max⁡({1}∪{w(e):e∈E}),β=b+⌈log⁡(n+m+2)⌉.W=\max\left(\{1\}\cup\{w(e):e\in E\}\right), \qquad \beta=b+\left\lceil\log(n+m+2)\right\rceil.

For an admissible UU and ℓ>0\ell>0, constructing J′J' from JJ adds ℓ\ell colour vertices and one new edge for each t∈Rt\in R. Since p≤sp\le s,

∣V(J′)∣≤2n,∣E(J′)∣≤m+n,∣Q∣=p+ℓ≤2s−1.|V(J')|\le2n, \qquad |E(J')|\le m+n, \qquad |Q|=p+\ell\le2s-1.

Since D≤(n−1)WD \le(n-1)W and ℓ+1≤s\ell+1 \le s, every new edge has weight at most MM, where

M=Λ+(ℓ+1)D+1≤mW+s(n−1)W+1.M = \Lambda+ (\ell+1)D + 1 \le mW + s(n-1)W + 1.

This bound has O(β)O(\beta) bits. Constructing J′J' therefore takes polynomial time in nn and bb. Theorem A bounds every solver call STVal⁡(J′,Q)\operatorname{STVal}(J',Q) by

7.97p+ℓpoly⁡(n,b)≤7.972s−1poly⁡(n,b).7.97^{p+\ell}\operatorname{poly}(n,b) \le7.97^{2s-1}\operatorname{poly}(n,b).

Combining these bounds, the overall running time is bounded by

2s[7.97s+∑ℓ=1s−12O(ℓ)7.972s−1]poly⁡(n,b)=2O(s)poly⁡(n,b).2^s\left[7.97^s+\sum_{\ell=1}^{s-1}2^{O(\ell)}7.97^{2s-1}\right]\operatorname{poly}(n,b) =2^{O(s)}\operatorname{poly}(n,b).

Polynomial factors in ss are absorbed into poly⁡(n,b)\operatorname{poly}(n,b), since s≤ns \le n.

Polynomial space

Since B≤r(n−1)WB \le r(n-1)W and F≤(∣V(J′)∣−1)MF \le(|V(J')|-1)M, all stored distances and finite costs, including BB, FF, ℓM\ell M, and B+F−ℓMB+F-\ell M, have O(β)O(\beta) bits. Table 1 lists the data stored during one iteration.

Stored dataBit-space bound
Graphs GG, JJ, and the current J′J'O((n+m)β)O((n+m)\beta)
Set UU and loop countersO(n)O(n)
One colouring h:R→[ℓ]h:R\to[\ell]O(rlog⁡(ℓ+1))O(r\log(\ell+1))
Distances, scalar costs, and running minimumO(nβ)O(n\beta)
SplitterPsplit(n)P_{\mathrm{split}}(n)
One active call to Theorem AO(n3βlog⁡(n+2))O(n^3\beta\log(n+2))

Table 1. Storage used by the current iteration and one active solver call. The polynomial Psplit(n)P_{\mathrm{split}}(n) bounds the space used by the splitter construction in § 2.3.

The current set UU uses ss bits. The indexed generator of Theorem B uses polynomial initialization and query space, with O(ℓ+log⁡(n+2))O(\ell+\log(n+2)) bits for its current index. Only one colouring is stored during its solver call. Checking that all colours occur uses O(ℓ)O(\ell) additional bits.

Summing the storage used simultaneously gives

Space⁡(ST⁡)≤Psplit(n)+O((n+m)β+n3βlog⁡(n+2))=poly⁡(n,b).\operatorname{Space}(\operatorname{ST}) \le P_{\mathrm{split}}(n) + O((n+m)\beta+n^3\beta\log(n+2)) = \operatorname{poly}(n,b).

The degrees of these polynomial bounds are independent of ss.

Recovering an optimal tree

Let GG, KK, SS denote the original feasible instance with ∣K∣≥2|K| \ge2, before preprocessing. Set v=ST⁡(G,K,S)v=\operatorname{ST}(G,K,S) and Gcur=GG_{\mathrm{cur}}=G. Process each original edge ee once, deleting it from GcurG_{\mathrm{cur}} if ST⁡(Gcur−e,K,S)=v\operatorname{ST}(G_{\mathrm{cur}}-e,K,S)=v. An infeasible call returns +∞+\infty, so the edge is retained.

The deletions preserve the optimum vv. 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 TT with w(T)=vw(T)=v.

Edge deletion preserves SS as a multiway cut. Reconstruction makes at most mm additional calls to ST⁡\operatorname{ST} and reuses the same workspace. Thus the time bound of 2O(s)poly⁡(n,b)2^{O(s)}\operatorname{poly}(n,b) and the space bound of poly⁡(n,b)\operatorname{poly}(n,b) 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 2O(s)2^{O(s)} poly(n,b)(n,b) time and polynomial space, where ss is the size of a multiway cut for the terminals. The selection identity reduces the optimization for each admissible U⊆SU \subseteq S to choosing at most ∣U∣−1|U| - 1 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 2o(s)2^{o(s)} poly(n,b)(n,b)-time algorithm exists for Steiner Tree. Such an algorithm would contradict the Exponential Time Hypothesis: taking S=KS = K would yield a 2o(k)2^{o(k)} poly(n,b)(n,b)-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. [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. [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. [3]Fedor V. Fomin, Petteri Kaski, Daniel Loksh­tanov, 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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_ekxe6g9u
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-Astra

View statement
Looking for related papers…
Contents