Parameterized Approximation Schemes
for Steiner Trees with Small Number of Steiner Vertices∗
Pavel Dvořák† 1 , Andreas Emil Feldmann2 ,
Dušan Knop2,3 , Tomáš Masařı́k2 , Tomáš Toufar1 , and Pavel Veselý1

arXiv:1710.00668v2 [] 29 Oct 2017

1

Computer Science Institute, Charles University, Prague, Czech Republic
{koblich,toufar,vesely}@iuuk.mff.cuni.cz
2
Department of Applied Mathematics, Charles University, Prague, Czech Republic
feldmann.a.e@gmail.com, {knop,masarik}@kam.mff.cuni.cz
3
Department of Informatics, University of Bergen, Bergen, Norway

Abstract
We study the Steiner Tree problem, in which a set of terminal vertices needs to be
connected in the cheapest possible way in an edge-weighted graph. This problem has been
extensively studied from the viewpoint of approximation and also parametrization. In particular, on one hand Steiner Tree is known to be APX-hard, and W[2]-hard on the other,
if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution.
In contrast to this we give an efficient parameterized approximation scheme (EPAS), which
circumvents both hardness results. Moreover, our methods imply the existence of a polynomial
size approximate kernelization scheme (PSAKS) for the assumed parameter.
We further study the parameterized approximability of other variants of Steiner Tree,
such as Directed Steiner Tree and Steiner Forest. For neither of these an EPAS is
likely to exist for the studied parameter: for Steiner Forest an easy observation shows that
the problem is APX-hard, even if the input graph contains no Steiner vertices. For Directed
Steiner Tree we prove that computing a constant approximation for this parameter is
W[1]-hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner
Tree. Also we prove that there is an EPAS and a PSAKS for Steiner Forest if in addition
to the number of Steiner vertices, the number of connected components of an optimal solution
is considered to be a parameter.

1

Introduction

In this paper we study several variants of the Steiner Tree problem. In its most basic form
this optimization problem takes an undirected graph G = (V, E) with edge weights w(e) ∈ R+
0 for
every e ∈ E, and a set R ⊆ V of terminals as input. The non-terminals in V \ R are called Steiner
vertices. A Steiner tree is a tree in the graph G, which spans all terminals inP
R and may contain
some of the Steiner vertices. The objective is to minimize the total weight e∈E(T ) w(e) of the
computed Steiner tree T ⊆ G. This fundamental optimization problem is one of the 21 original
NP-hard problems listed by Karp [25] in his seminal paper from 1972, and has been intensively
studied since then. The Steiner Tree problem and its variants have applications in network
design, circuit layouts, and phylogenetic tree reconstruction, among others (see survey [23]).
∗ This work was partially supported by the project SVV–2017–260452. D. Knop, T. Masařı́k and P. Veselý were supported by project 17-09142S of GAČR. A.E. Feldmann was supported by the Czech Science Foundation GAČR (grant
#17-10090Y). A.E. Feldmann, T. Masařı́k, T. Toufar, and P. Veselý were supported by the project GAUK 1514217.
† The research leading to these results has received funding from the European Research Council under the
European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 616787.

1

Two popular ways to handle the seeming intractability of NP-hard problems are to design
approximation [35] and parameterized [13] algorithms. For the former, an α-approximation is
computed in polynomial time for some factor α specific to the algorithm, i.e., the solution is always
at most a multiplicative factor of α worse than the optimum of the input instance. The Steiner
Tree problem, even in its basic form as defined above, is APX-hard [12], i.e., it is NP-hard to
obtain an approximation factor of α = 96
95 ≈ 1.01. However a factor of α = ln(4) + ε ≈ 1.39 can
be achieved in polynomial time [6], which is the currently best factor known for this runtime.
For parameterized algorithms, an instance is given together with a parameter p describing
some property of the input. The optimum solution is computed in time f (p) · nO(1) , where f
is a computable function independent of the input size n. If such an algorithm exists, we call
the problem fixed-parameter tractable (FPT) for parameter p. A well-studied parameter for the
Steiner Tree problem is the number of terminals |R|. It is known since the classical result
of Dreyfus and Wagner [16] that the Steiner Tree problem is FPT for this parameter, as the
problem can be solved in time 3|R| · nO(1) if n = |V |, which for unweighted graphs can be improved
to 2|R| · nO(1) using the results of Björklund et al. [2]. A somewhat complementary and less-studied
parameter to the number of terminals is the number of Steiner vertices in the optimum solution,
i.e., p = |V (T ) \ R| if T is an optimum Steiner tree. It is known [15] that Steiner Tree is
W[2]-hard for parameter p and therefore is unlikely to be FPT, in contrast to the parameter |R|.
This parameter p has been mainly studied in the context of unweighted graphs before. The problem
remains W[2]-hard in this special case and therefore the focus has been on designing parameterized
algorithms for restricted graph classes, such as planar or d-degenerate graphs [24, 33].
In contrast to this, our question is: what can be done in the most general case, in which the class
of input graphs is unrestricted and edges may have weights? Our main result is that we can overcome
the APX-hardness of Steiner Tree on one hand, and on the other hand also the W[2]-hardness for
our parameter of choice p, by combining the two paradigms of approximation and parametrization.
This relatively new and growing area has gained quite a bit of attention recently (see e.g., [3, 7, 9, 10,
11, 17, 20, 26, 27, 28, 29, 32, 34]). We show that there is an efficient parameterized approximation
scheme (EPAS), which for any ε > 0 computes a (1 + ε)-approximation in time f (p, ε) · nO(1) for
a computable function f independent of n. Note that here we consider the approximation factor
of the algorithm as a parameter as well, which accounts for the “efficiency” of the approximation
scheme (analogous to an efficient polynomial time approximation scheme or EPTAS).
Theorem 1. There is an algorithm for Steiner Tree, which given an edge-weighted undirected
graph G = (V, E), terminal set R ⊆ V , and integer p, computes a (1 + ε)-approximation to the
2
4
optimum Steiner tree T ⊆ G in time 2O(p /ε ) · nO(1) , if p ≥ |V (T ) \ R| and ε > 0. 1
Many variants of the Steiner Tree problem exist, and we explore the applicability of our
techniques to some common ones. For the Directed Steiner Tree problem the aim is to compute
an arborescence, i.e., a directed graph obtained by orienting the edges of a tree so that exactly one
vertex called the root has in-degree zero (which means that all vertices are reachable from the root).
More concretely, the input consists of a directed graph G = (V, A) with arc weights w(a) ∈ R+
0
for every a ∈ A, a terminal set R ⊆ V , and a specified terminal r ∈ R. A Steiner arborescence
is an arborescence in G with root r containing
P all terminals R. The objective is to find a Steiner
arborescence T ⊆ G minimizing the weight a∈A(T ) w(a). This problem is notoriously hard to

approximate: no O log2−ε (n) -approximation exists unless NP ⊆ ZTIME(npolylog(n) ) [22]. But even
for the Unweighted Directed Steiner Tree problem in which each arc has unit weight, a fairly
simple reduction from the Set Cover problem implies that no O (log n)-approximation algorithm is
possible unless NP ⊆ DTIME(nO(log log n) ) [19, 22]. At the same time, even Unweighted Directed
Steiner Tree is W[2]-hard for our considered parameter p [24, 30], just as the undirected case.
For this reason, all previous results have focused on restricted inputs: Jones et al. [24] prove that
when combining the parameter p with the size of the largest excluded topological minor of the
input graph, Unweighted Directed Steiner Tree is FPT. They also show that if the input
graph is acyclic and d-degenerate, the problem is FPT for the combined parameter p and d.
Our focus again is on general unrestricted inputs. We are able to leverage our techniques to
2

the unweighted directed setting, and obtain an EPAS, as summarized in the following theorem.
Here an optimum Steiner arborescence is one containing the minimum number of arcs.
Theorem 2. There is an algorithm for Unweighted Directed Steiner Tree, which given
an unweighted directed graph G = (V, A), terminal set R ⊆ V , root r ∈ R, and integer p, computes
2
a (1 + ε)-approximation to the optimum Steiner arborescence T ⊆ G in time 2p /ε · nO(1) , if
1
p ≥ |V (T ) \ R| and ε > 0.
Can our techniques be utilized for the even more general case when arcs have weights? Interestingly, in contrast to the above theorem we can show that in general the Directed Steiner Tree
problem most likely does not admit such approximation schemes, even when allowing “non-efficient”
runtimes of the form f (p, ε) · ng(ε) for any computable functions f and g. This follows from the next
theorem, since setting ε to any constant, the existence of such a (1 + ε)-approximation algorithm
would imply W[1] = FPT.
Theorem 3. For any constant α, it is W[1]-hard to compute an α-approximation of the optimum
Steiner arborescence T for Directed Steiner Tree parameterized by p = |V (T ) \ R|, if the
input graph is arc-weighted.
Other common variants of Steiner Tree include the Prize Collecting Steiner Tree
and Steiner Forest problems. The latter takes as input an edge-weighted undirected graph
G = (V, E) and a list {s1 , t1 }, . . . , {sk , tk } of terminal pairs, i.e., R = {si , ti | 1 ≤ i ≤ k}. A Steiner
forest is a forest F in G for which each {si , ti } pair is in the same connected component, and
the objective is to minimize the total weight of the forest F . For this variant it is not hard to
see that parametrizing by p = |V (F ) \ R| cannot yield any approximation scheme, as a simple
reduction from Steiner Tree shows that the problem is APX-hard even if the input has no Steiner
vertices (see Section 2.1). For the Prize Collecting Steiner Tree problem, the input is again
a terminal set in an edge-weighted graph, but the terminals have additional costs. A solution tree
is allowed to leave out a terminal but has to pay its cost in return (cf. [35]). It is also not hard to
see that this problem is APX-hard, even if there are no Steiner vertices at all. These simple results
show that our techniques to obtain approximation schemes reach their limit quite soon: with the
exception of Unweighted Directed Steiner Tree, most common variants of Steiner Tree
seem not to admit approximation schemes for our parameter p. We are however able to generalize
our EPAS to Steiner Forest if we combine p with the number c of connected components in
the optimum solution. In fact, our main result of Theorem 1 is a corollary of the next theorem,
using only the first part of the above reduction from Steiner Tree (cf. Section 2.1). Due to this,
it is not possible to have a parametrized approximation scheme for the parameter c alone, as such
an algorithm would imply a polynomial time approximation scheme for the APX-hard Steiner
Tree problem. Hence the following result necessarily needs to combine the parameters p and c.
Theorem 4. There is an algorithm for Steiner Forest, which given an edge-weighted undirected
graph G = (V, E), a list {s1 , t1 }, . . . , {sk , tk } ⊆ V of terminal pairs, and integers p, c, computes
2
4
a (1 + ε)-approximation to the optimum Steiner forest F ⊆ G in time (2c)O((p+c) /ε ) · nO(1) , if
p ≥ |V (F ) \ R| where R = {si , ti | 1 ≤ i ≤ k}, the number of connected components of F is at
most c, and ε > 0. 1
A topic tightly connected to parameterized algorithms is kernelization. We here use the framework of Lokshtanov et al. [28], who also give a thorough introduction to the topic (see Section 2.2
for some formal definitions). Loosely speaking, a kernelization algorithm runs in polynomial
time, and, given an instance of a parameterized problem, computes another instance of the same
problem, such that the size of the latter instance is at most f (p) for some computable function
f in the parameter p of the input instance. The computed instance is called the kernel, and for
an optimization problem it must be possible to convert an optimum solution to the kernel into
an optimum solution to the input instance.
1 If the input to this optimization problem is malformed (e.g., if p is smaller than the number of Steiner vertices
of the optimum) then the output of the algorithm can be arbitrary (cf. [28])

3

A fundamental result of parameterized complexity says that a problem is FPT if and only if
it has a kernelization algorithm [13]. This means that for our parameter p, most likely Steiner
Tree does not have a kernelization algorithm, as it is W[2]-hard. For this reason, the focus of
kernelization results have previously again shifted to special cases. By a folklore result, Steiner
Tree is FPT for our parameter p if the input graph is planar (cf. [24]). Of particular interest are
polynomial kernels, which have size polynomial in the input parameter. The idea is that computing
the kernel in this case is an efficient preprocessing procedure for the problem, such that exhaustive
search algorithms can be used on the kernel. Suchý [33] proved that Unweighted Steiner Tree
parameterized by p admits a polynomial kernel if the input graph is planar.
Our aspirations again are to obtain results for inputs that are as general as possible, i.e., on
unrestricted edge-weighted input graphs. We prove that Steiner Tree has a polynomial lossy
kernel, despite the fact that the problem is W[2]-hard: an α-approximate kernelization algorithm is
a kernelization algorithm that computes a new instance for which a given β-approximation can be
converted into an αβ-approximation for the input instance in polynomial time. The new instance
is now called a (polynomial) approximate kernel, and its size is again bounded as a function (a
polynomial) of the parameter of the input instance.
Just as for our parameterized approximation schemes in Theorems 1 and 4, we prove the
existence of a lossy kernel for Steiner Tree by a generalization to Steiner Forest where we
combine the parameter p with the number c of connected components in the optimum solution.
Also, our lossy kernel can approximate the optimum arbitrarily well: we prove that for our parameter the Steiner Forest problem admits a polynomial size approximate kernelization scheme
(PSAKS), i.e., for every ε > 0 there is a (1 + ε)-approximate kernelization algorithm that computes
a polynomial approximate kernel. An easy corollary then is that Steiner Tree parametrized only
by p also has a PSAKS, by setting c = 1 in Theorem 5 and using the above mentioned reduction
from Steiner Tree to Steiner Forest (cf. Section 2.1).
Theorem 5. There is a (1 + ε)-approximate kernelization algorithm for Steiner Forest, which
given an edge-weighted undirected graph G = (V, E), a list {s1 , t1 }, . . . , {sk , tk } ⊆ V of terminal
2O(1/ε)

pairs, and integers p, c, computes an approximate kernel of size ((p + c)/ε)
, if for the optimum
Steiner forest F ⊆ G, p ≥ |V (F ) \ R| where R = {si , ti | 1 ≤ i ≤ k}, the number of connected
components of F is at most c, and ε > 0. 1
Analogous to approximation schemes, it is possible to distinguish between efficient and nonefficient kernelization schemes: a PSAKS is efficient if the size of the approximate kernel is bounded
by f (ε) · pO(1) , where p is the parameter and f is a computable function independent of p. Our
bound on the approximate kernel size in Theorem 5 implies that we do not obtain an efficient
PSAKS for either Steiner Forest or Steiner Tree. This is in contrast to the existence of
efficient approximation schemes for the same parameters in Theorems 1 and 4. We leave open
whether an efficient PSAKS can be found in either case. Interestingly, we also do not obtain any
PSAKS for the Unweighted Directed Steiner Tree problem, even though by Theorem 2 an
EPAS exists. We leave open whether a PSAKS can be found for this variant as well.

1.1

Used techniques

Our algorithms are based on the intuition that a Steiner tree containing only few Steiner vertices
but many terminals must either contain a large component induced by terminals, or a Steiner vertex
with many terminal neighbours forming a large star. A high-level description of our algorithms
for Unweighted Directed Steiner Tree and Steiner Forest therefore is as follows. In
each step a tree is found in the graph in polynomial time, which connects some terminals using few
Steiner vertices. We save this tree as part of the approximate solution and then contract it in the
graph. The vertex resulting from the contraction is declared a terminal and the process repeats for
the new graph. Previous results [24, 33] have also built on this straightforward procedure in order
to obtain FPT algorithms and polynomial kernels for special cases of Unweighted Directed
Steiner Tree and Unweighted Steiner Tree. In particular, in the unweighted undirected

4

setting it is a well-known fact (cf. [33]) that contracting an adjacent pair of terminals is always
a safe option, as there always exists an optimum Steiner tree containing this edge. However this
immediately breaks down if the input graph is edge-weighted, as an edge between terminals might
be very costly and should therefore not be contained in any (approximate) solution.
Instead we employ more subtle contraction rules, which use the following intuition. Every time
we contract a tree with ` terminals we decrease the number of terminals by ` − 1 (as the vertex
arising from a contraction is a terminal). Our ultimate goal would be to reduce the number of
terminals to one—at this point, the edges that we contracted during the whole run connect all the
terminals. Decreasing the number of terminals by one can therefore be seen as a “unit of work”.
We will pick a tree with the lowest cost per unit of work done, and prove that as long as there are
sufficiently many terminals left in the graph, these contractions only lose an ε-factor compared to
the optimum. As soon as the number of terminals falls below a certain threshold depending on the
given parameter, we can use an FPT algorithm computing the optimum solution. This algorithm
is parametrized by the number of terminals, which now is bounded by our parameter. For the
variants of Steiner Tree considered in our positive results, such an FPT algorithm can easily
be obtained from the ones for Steiner Tree [2, 16]. Adding this exact solution to the previously
contracted trees gives a feasible solution that is a (1 + ε)-approximation.
Each step in which a tree is contracted in the graph, can be seen as a reduction rule as typically
used for kernelization algorithms. Typically, a proof for a kernelization algorithm will define a set of
reduction rules and then show that the instance resulting from applying the rules exhaustively has
size bounded as a function in the parameter. To obtain an α-approximate kernelization algorithm,
additionally it is shown that each reduction rule is α-safe. Roughly speaking, this means that at
most a factor of α is lost when applying any number of α-safe reduction rules (see Section 2.2 for
formal definitions).
Contracting edges in a directed graph may introduce new paths, which did not exist before.
Therefore, for the Unweighted Directed Steiner Tree problem, we need to carefully choose
the arborescence to contract. In order to prove Theorem 2 we show that each contraction is a
(1 + ε)-safe reduction rule. However, the total size of the graph resulting from exhaustively applying
the contractions is not necessarily bounded as a function of our parameter. Thus we do not obtain
an approximate kernel.
For Steiner Forest the situation is in a sense the opposite. Choosing a tree to contract follows
a fairly simple rule. On the downside however, the contractions we perform are not necessarily
(1 + ε)-safe reduction rules. In fact there are examples in which a single contraction will lose a large
factor compared to the optimum cost. We are still able to show however, that after performing
all contractions exhaustively, any β-approximation to the resulting instance can be converted into
a (1 + ε)β-approximation to the original input instance. Even though the total size of the resulting
instance again cannot be bounded in terms of our parameter, for Steiner Forest we can go
on to obtain a PSAKS. For this we utilize a result of Lokshtanov et al. [28], which shows how to
obtain a PSAKS for Steiner Tree if the parameter is the number of terminals. This result can
be extended to Steiner Forest, and since our instance has a number of terminals bounded in
our parameter after applying all contractions, we obtain Theorem 5.
Finally, to obtain our inapproximability result of Theorem 3, we use a reduction from the
Dominating Set problem. It was recently shown by Chen and Lin [9] that this problem does
not admit parameterized α-approximation algorithms for any constant α, if the parameter is the
solution size, unless W[1] = FPT. We are able to exploit this to also show that no such algorithm
exists for Directed Steiner Tree with edge weights, under the same assumption.

1.2

Related work

As the Steiner Tree problem and its variants have been studied since decades, the literature on
this topic is huge. We only present a selection of related work here, that was not yet mentioned above.
For planar graphs [5] it was shown that an EPTAS exists for Steiner Tree. For Steiner
Forest a 2-approximation can be computed in polynomial time on general inputs [1], but an EPTAS
also exists if the input is planar [18]. If the Unweighted Steiner Tree problem is parametrized by
5

the solution size, it is known [14] that no polynomial (exact) kernel exists, unless NP ⊆ coNP/Poly.
If the input is restricted to planar or bounded-genus graphs it was shown that polynomial kernels
do exist for this parametrization [31]. It was later shown [33] that for planar graphs this is even true
for our parameter p. For the Directed Steiner Tree problem it is a long standing open problem
whether a polylogarithmic approximation can be computed in polynomial time. It is
 known that an
O (|R|ε )-approximation can be computed in polynomial time [8], and an O log2 n -approximation
in quasi-polynomial time [8]. A recent result [21] considers generalizations of Directed Steiner
Tree and characterizes which of these problems are FPT and which are W[1]-hard for parameter |R|.

2
2.1

Preliminaries
Reducing Steiner tree to Steiner forest

We may reduce the Steiner Tree problem to Steiner Forest by picking an arbitrary terminal
r of the Steiner Tree instance, and for every other terminal v of this instance, introduce a
terminal pair {v, r} for Steiner Forest.
If we want to construct an instance without Steiner vertices, we can add a new vertex w0 for
every Steiner vertex w of Steiner Tree and add an edge ww0 of cost 0. Additionally we introduce
a terminal pair {w, w0 } to our Steiner Forest instance. Hence {si , ti | 1 ≤ i ≤ k} = V in the constructed Steiner Forest instance (i.e., there are no Steiner vertices), but an optimum Steiner forest
in the constructed graph costs exactly as much as an optimum Steiner tree in the original graph. As
Steiner Tree is APX-hard, the same is true for Steiner Forest, even if all vertices are terminals.

2.2

Lossy kernels

We give a brief introduction to the lossy kernel framework as introduced by Lokshtanov et al. [28].
See the latter for a thorough introduction to the topic.
For an optimization problem, a polynomial time pre-processing algorithm is a pair of polynomial
time algorithms: the reduction algorithm R and the solution lifting algorithm L. The former takes
an instance I with parameter p of a given problem as input, and outputs another instance I 0 with
parameter p0 . The solution lifting algorithm L converts a solution for the instance I 0 to a solution
of the input instance I: given a solution s0 to I 0 , L computes a solution s for I, such that s is
optimal for I if s0 is optimal for I 0 . If additionally the output of R is bounded as a function of p,
i.e., when |I 0 | + p0 ≤ f (p) for some computable function f independent of |I|, then the pair given
by R and L is called a kernelization algorithm, and I 0 together with parameter p0 is the kernel.
If the reduction and solution lifting algorithms get an input that is not an instance of the problem
(for example if the parameter does not correctly describe some property of the optimum solution),
then the outputs of the algorithms are undefined and can be arbitrary.
An α-approximate polynomial time pre-processing algorithm is again a pair of a reduction
algorithm R and a solution lifting algorithm L, both running in time polynomial in the input size.
The reduction and solution lifting algorithms are as before, but there is a different property on the
output of the latter: if the given solution s0 to the instance I 0 computed by R is a β-approximation,
then the output of L is a solution s that is an αβ-approximation for the original instance I.
Analogous to before, an α-approximate kernelization algorithm is an α-approximate polynomial
time pre-processing algorithm for which the size of the output of the reduction algorithm is bounded
in terms of p only. The output of R is in this case called an approximate kernel, and it is polynomial
if its size is bounded by a polynomial in p.
In the context of lossy kernels a reduction rule is a reduction algorithm R. It is called α-safe if
a solution lifting algorithm L exists, which together with R form a strict α-approximate polynomial
time pre-precessing algorithm. This means that if s0 is a β-approximation for the instance computed
by R, then L computes a (max{α; β})-approximation s for the input instance. As shown in [28],
the advantage of considering this stricter definition is that, as usual, reduction rules can be applied
exhaustively, until a stable point is reached in which none of the rules would change the instance

6

any longer: the algorithm resulting from applying these rules together with their corresponding
solution lifting algorithms, forms a strict α-approximate polynomial time pre-precessing algorithm
(which is not necessarily the case when using the non-strict definition; see [28]).

3

The weighted undirected Steiner forest and Steiner tree
problems

In this section we describe an approximate polynomial time preprocessing
algorithm that returns

an instance of Steiner Forest containing at most O (p + c)2 /ε4 terminals if the optimum
Steiner forest has at most p Steiner vertices and at most c connected components. We can use this
algorithm in two ways. Either we can proceed with a kernelization derived from Lokshtanov et al.
[28] and obtain a polynomial size lossy kernel (Theorem 5), or we can run an exact FPT algorithm
derived from Dreyfus and Wagner [16] on the reduced instance, obtaining an EPAS running in
single exponential time with respect to the parameters (Theorems 1 and 4). In both cases we use
the combined parameter (p, c).

Input:
Solution:

Steiner Forest
A graph G = (V, E), with edge weights w(e) ∈ R+ for each e ∈ E, and a list
{s1 , t1 }, . . . , {sk , tk } of pairs of terminals.
A Steiner forest F ⊆ G containing an si -ti path for every i ∈ [k]

We first rescale all weights so that every edge has weight strictly greater than 1. Then, in
each step of our algorithm we pick a star, add it to the solution, and contract the star in the
current graph. We repeat this procedure until the number of terminals falls below a specified bound
depending on ε, p, and c. To describe how we pick the star to be contracted in each step, we need
to introduce the ratio of a star. Let C be a set of edges of a star, i.e., all edges of C are incident
to a common vertex which is the center of the star, and denote by Q the set of terminals
P incident
to C. Provided |Q| ≥ 2, we define the ratio of C as w(C)/(|Q| − 1), where w(C) = e∈C w(e).
Note that we allow C to contain only a single edge if it joins two terminals. Observe also that
due to rescaling of edge weights each star has ratio strictly greater than 1.
In every step, our algorithm contracts a star with the best available ratio (i.e., the lowest ratio
among all stars connecting at least two terminals). Due to the following lemma, the star with best
ratio has a simple form: it consists of the cheapest i edges incident to its center vertex and some
terminal. As there are n possible center vertices and at most n incident edges to each center
which

can be sorted in time O (n log n), the best ratio star can be found in time O n2 log n . Later we
show that there is a star with at least two terminals in every step, provided that the number of
terminals is more that p.
Lemma 6. Let v be a vertex and denote by q1 , q2 , . . . the terminals adjacent to v, where w(vq1 ) ≤
w(vq2 ) ≤ · · · , i.e., the terminals are ordered non-decreasingly by the weight of the corresponding edge
vqi . The star with the best ratio having v as its center has edge set {vq1 , vq2 , . . . , vq` } for some `.
Proof. Let C be an edge set of a star with center vertex v. First note that if this star contains a
Steiner vertex w as a leaf, vw can be removed from C in order to decrease the ratio w(C)/(|Q| − 1),
since only the terminals Q of the star are counted in the denominator. Also if C does not contain
some edge vqi but an edge vqj with j > i, then we may switch the edge vqj for vqi in C in order
to optimize the ratio: the denominator stays the same, but the numerator cannot increase, as the
terminals q1 , q2 , . . . are ordered non-decreasingly according to the weights vqi .
To analyse our algorithm we need to keep track of the different graphs resulting from each contraction step t. Initially we set G0 to the input graph, and in each step t ≥ 0 we obtain a new graph
Gt+1 from Gt by contracting a set of edges Ct in Gt , such that Ct forms a star of minimum ratio in
Gt . That is, we obtain Gt+1 from Gt by identifying all vertices incident to edges in Ct , removing all
resulting loops, and among the resulting parallel edges we delete all but the lightest one with respect
7

v
Ct

v0
···

v0

···

Ft∗

∗
Ft+1

∗
Figure 1: An example of creating Ft+1
from Ft∗ after a contraction Ct . Each edge in Ct (dashed)
∗
may or may not be in Ft . The thick edge cannot be in Dt because it is not incident to any terminal.

to their weights. We also adjust the terminal pairs in a natural way: let v be the vertex of Gt+1
resulting from contracting Ct . If Gt had a terminal pair {s, t} such that s is incident to some edge of
Ct while t is not, then we introduce the terminal pair {v, t} for Gt+1 . Also every terminal pair {s, t}
of Gt for which neither s nor t is incident to any edge of Ct is introduced as a terminal pair of Gt+1 .
Any terminal pair for which both s and t are incident to edges of Ct is going to be connected by a path
in the computed solution, as it will contain Ct . Hence, such a terminal pair can be safely removed.
The algorithm stops contracting best-ratio stars when there are less than τ terminals left; the
exact value of τ depends on p, c, and the desired approximation factor, it will satisfy τ > p and
we specify it later. If the algorithm stops in step t̃, the solution lifting algorithm takes a feasible
St̃
solution F of Gt̃ and returns the union of F and t=0 Ct . Such a solution is clearly feasible, since
we adapted the terminal pairs accordingly after each contraction.
For the purpose of analysis, we consider a solution in the current graph Gt that originates
from an optimal solution of the original instance G0 , but may contain edges that are heavier than
those in Gt . More concretely, denote by F0∗ an optimal solution in G0 , i.e., F0∗ is a Steiner forest
containing every si -ti path with at most p Steiner vertices and at most c connected components.
∗
Given Ft∗ for t ≥ 0, we modify this solution to obtain a new feasible solution Ft+1
on the terminal
pairs of Gt+1 . Note that the edges of the contracted star Ct might not be part of Ft∗ . We still
∗
mimic the contraction of the star in Ft∗ : to obtain Ft+1
from Ft∗ , we identify all leaves of Ct (which
are terminals by Lemma 6 and thus part of the solution Ft∗ ) and possibly also the center v of Ct if it
is in Ft∗ . This results in a vertex v 0 . We now want to delete edges incident to v 0 in such a way that
we are left with an acyclic feasible solution. If we delete an inclusion-wise minimal feedback edge
set, we clearly get a feasible solution. Let Qt denote the set of terminals incident to Ct . We choose
a feedback edge set Dt for which every edge was incident to a vertex of Qt before the contraction in
Ft∗ , i.e., an edge of Gt corresponding to an edge of Dt never connects two Steiner vertices. Note that
such an inclusion-wise minimal feedback edge set always exists: if we delete all edges of Ft∗ incident
to Qt except Ct and then contract Ct , we get an acyclic graph. See Fig. 1 for an illustration.
∗
The resulting graph is Ft+1
, which now forms a forest connecting all terminal pairs of Gt+1 .
∗
Note that for each edge in Ft+1
there is a corresponding edge in Gt+1 , which however may be
lighter in Gt+1 , as from each bundle of parallel edges in Gt we keep the lightest one, but this edge
may not exist in Ft∗ .
We now observe that there is always a star with at least two terminals and thus the algorithm
always selects some star.
Lemma 7. Provided that there are at least τ > p terminals in Gt , there is a star with a least two
terminals in Gt .
Proof. Note that it is sufficient to find such a star in Ft∗ as edges in Ft∗ are also present in Gt
(even if their weight may be smaller). If there is an edge e between two terminals in Ft∗ , then we
are done as e itself is a star. Otherwise, all terminals are incident to Steiner vertices only. Thus
there must be a Steiner vertex incident to at least two terminals in Ft∗ , since Ft∗ contains at most
p Steiner vertices but more than p terminals.
8

To show that our algorithm only loses an ε-factor compared to the cost of the optimum
solution F0∗ , we will compare the cost of the edges Ct contracted by our algorithm to the set
∗
Dt = E(Ft+1
) \ E(Ft∗ ) of deleted edges of Ft∗ . Note that there are at least |Qt | − c edges in Dt ,
since we contracted Qt terminals in the forest Ft∗ with at most c connected components to obtain
∗
Ft+1
, and a forest on n vertices and k components has n − k edges. We decrease the number of
vertices of Ft∗ by at least |Qt | − 1 (one more if the center of the star with edge set Ct was a Steiner
vertex present in Ft∗ ), and we decrease the number of components by at most c − 1. Note also
that for any two time steps t =
6 t0 , the sets Dt and Dt0 , but also the sets Ct and Ct0 , are disjoint.
Thus if w(Ct ) ≤ (1 + ε)w(Dt ) for every t, then our algorithm computes a (1 + ε)-approximation.
Unfortunately, this is not always the case: there are contractions for which this condition does
not hold (see Fig. 2) and we have to account for them differently.
Definition 8. If w(Ct ) ≤ (1 + ε)w(Dt ) we say that the contracted edge set Ct in step t is good ;
∗
otherwise Ct is bad. Moreover, if Ft∗ has strictly more components than Ft+1
, we say that Ct is
multiple-component, otherwise it is single-component.
Our goal is to show that the total weight of bad contraction is bounded by an ε-fraction of
the weight of an optimum solution. We start by proving that if the set Qt of terminals in Ct is
sufficiently large, then the contraction is good. We define
λ :=

(1 + ε)(p + c)
.
ε

Lemma 9. If |Qt | ≥ λ, then the contracted edge set Ct is good.
Proof. For brevity, we drop the index t. Let r = w(C)/(|Q| − 1) be the ratio of the contracted
star, and let `0 be the number of deleted edges in D that connect two terminals. Note that any
such edge has weight at least r, since it spans a star with two terminals, which has ratio equal
to its weight, and since each edge in F ∗ (of which D is a subset) can only be heavier than the
corresponding edge in the current graph G.
Let u1 , . . . , uq be the Steiner vertices adjacent to edges in D, and let `i be the number of edges
in D incident to one such Steiner vertex ui (see Fig. 3). Since D is a feedback edge set in which any
edge was incident to a terminal in Q before the contraction, there is no edge in D which connects two
Steiner vertices. Consider the star spanned by the `i edges of D incident to ui . If `i ≥ 2, the ratio
of this star is at least r, since its edges are at least as heavy as the corresponding edges in G and the
algorithm chose the star with minimum ratio in G. Thus, the weight of edges in D incident to ui is at
least r(`i − 1). In the case where `i = 1, the lower bound r(`i − 1) = 0 on the weight holds trivially.
Any edge
Pq in D not incident to any Steiner vertex ui connects two terminals. Therefore, we
have `0 + i=1 `i = |D| as any edge in D is incident to a vertex in Q and we thus do not count
any edge twice. Also recall that |D| ≥ |Q| − c. Since F contains at most p Steiner vertices we have
q ≤ p, and we obtain
!
q
q
X
X
0
0
w(D) ≥ r` +
r(`i − 1) = r ` +
`i − q ≥ r(|Q| − p − c) .
i=1

···
1

0.5
1

s1

i=1

v

···

0.5

w

w

1

1

F∗

s2

w

Figure 2: An example of a bad contraction. The numbers of terminals can be arbitrarily large
and the weight w can be arbitrarily small. The star centered at v has ratio 1 while every star
centered either at s1 or s2 has ratio slightly more than 1. By contracting the star centered at
v we create a cycle containing only edges of weight w. Thus, for a sufficiently small value of w
the contraction cannot be charged.
9

v
C

···

······

···

···

Q
D

`q

`1

`0

uq

u1

Figure 3: The contracted star C and a part of the optimal solution spanned by the terminals
Q of the star C.
Finally, using |Q| ≥ λ we bound w(C) by (1 + ε)w(D) as follows:

(1 + ε)w(D) ≥ (1 + ε)r(|Q| − p − c) = r(|Q| − 1) + r ε|Q| − (1 + ε)(p + c) + 1


(1 + ε)(p + c)
− (1 + ε)(p + c) = w(C) .
≥ w(C) + r ε
ε
Note that there may be a lot of contractions with |Q| < λ. However, we show that only a
bounded number of them is actually bad. The key idea is to consider contractions with ratio in
some interval ((1 + δ)i ; (1 + δ)i+1 ] for some δ > 0 and integer i. Due to the rescaling of weights
every star belongs to an interval with i ≥ 0. The following crucial lemma of our analysis shows that
the number of bad single-component contractions
√ in each such interval is bounded in terms of p and
ε, if δ is a function of ε. In particular, let δ := 1 + ε − 1, so that (1 + δ)2 = 1 + ε. We call an edge
set C with ratio r in the i-th interval, i.e., with r ∈ ((1 + δ)i ; (1 + δ)i+1 ], an i-contraction, and define
κ :=

(1 + δ)p
+ p.
δ

Lemma 10. For any integer i the number of bad single-component i-contractions is at most κ.
Proof. Suppose for a contradiction that the number of bad single-component i-contractions is larger
than κ. Let t̃ be the first step with a bad single-component i-contraction, i.e., t̃ is the minimum
among all t for which w(Ct ) > (1 + ε)w(Dt ) and w(Ct )/(|Qt | − 1) ∈ ((1 + δ)i ; (1 + δ)i+1 ] and the
contraction is single-component. The plan is to show that at step t̃ there is a “light” star in Gt̃
with ratio at most (1 + δ)i and consequently the algorithm would do a j-contraction for some j < i.
This leads to a contradiction, since we assumed that in step t̃ the contraction has ratio in interval i.
Note that it is sufficient to find such a light star in Ft̃∗ as for each edge in Ft̃∗ there is an edge in
the graph Gt̃ between the same vertices of the same weight or even lighter.
We claim that for each step t in which the algorithm does a bad single-component i-contraction
there is an edge et ∈ Dt with weight at most (1 + δ)i−1 . We have w(Ct ) > (1 + ε)w(Dt ) as Ct is
bad and w(Ct ) ≤ (1 + δ)i+1 (|Qt | − 1) as the ratio of Ct is in interval i. Putting it together and
using the definition of δ we obtain
w(Dt ) <

(1 + δ)i+1
(|Qt | − 1) = (1 + δ)i−1 (|Qt | − 1) .
1+ε

Because Ct is single-component, we have |Dt | ≥ |Qt | − 1 and therefore there is an edge et ∈ Dt
with weight at most (1 + δ)i−1 , which proves the claim.
Note that the edge et also exists at time step t̃, as t̃ ≤ t and Ft∗ is obtained from Ft̃∗ by a
sequence of edge contractions and deletions. At time t̃ it cannot be that et connects two terminals,
10

since we assume that the algorithm picked a star of ratio more than (1 + δ)i in step t̃ (recall that
each edge connecting two terminals is a star with ratio equal to its weight). It may happen though
that et connects two Steiner vertices in step t̃. We discard any such edge et that connects two
Steiner vertices in step t̃. That is, let S be the set of light edges et that lead between a Steiner
vertex and a terminal in step t̃. Note that edges et and et0 for steps t < t0 with bad i-contractions
are distinct, because Dt ∩ Dt0 = ∅ as all edges in Dt are deleted from Ft∗ . There are at most p − 1
edges et ∈
/ S connecting two Steiner vertices in Ft̃∗ , since Ft̃∗ is a forest and the optimum, from
∗
which Ft̃ is derived, contained at most p Steiner vertices. As we assume that there are more than
κ bad single-component i-contractions, we have |S| > κ − p.
At step t̃ there must be a Steiner vertex v in Ft̃∗ incident to at least |S|/p > (κ−p)/p ≥ (1+δ)/δ
edges in S. Consider a star C with v as the center and with edges from S that are incident to v;
we have |C| ≥ (1 + δ)/δ. The ratio of this star is at most |C|(1 + δ)i−1 /(|C| − 1). Since
|C|/(|C| − 1) ≤ (1 + δ) (by a routine calculation) we get that the ratio of C is at most (1 + δ)i
which is a contradiction to the assumption that the algorithm does an i-contraction in step t̃.
We also need a bound on number of bad multiple-component edge sets.
Lemma 11. The number of steps t in which a bad multiple-component edge set Ct is contracted
is at most c − 1.
∗
must have at least one component fewer
Proof. If Ct is a bad multiple-component edge set, Ft+1
∗
∗
than Ft . Since F0 has at most c components, the bound follows.

We remark that the proofs of Lemmas 10 and 11 do not use that the number of terminals in
a bad i-contraction is bounded by λ, as shown in Lemma 9. Instead we bound the total weight
of bad contractions in terms of λ. For this let j be the largest interval of any contraction during
the whole run of the algorithm, i.e., the ratio of every contracted star is at most (1 + δ)j+1 .
Lemma 12. The total weight of bad edge sets Ct is at most
(κ + c) · λ ·

(1 + δ)j+2
.
δ

Proof. By Lemma 11, there are less than c bad multiple-component contractions. Each of them
has at most λ terminals by Lemma 9 and has ratio at most (1 + δ)j+1 by the choice of j. Thus,
the total weight of all bad multiple-component contractions can be bounded by (1 + δ)j · λ · c.
Note that it follows from Lemmas 9 and 10 that the total weight of bad single-component
i-contractions is at most κ · λ · (1 + δ)i+1 . The bound on the total weight of bad contractions
follows by summing over all intervals in which the algorithm does a contraction:
κ·λ·

X
i≤j

(1 + δ)i+1 + c · λ · (1 + δ)j = κ · λ ·

(1 + δ)j+2 − 1
(1 + δ)j+2
+ c · λ · (1 + δ)j ≤ (κ + c) · λ ·
.
(1 + δ) − 1
δ

To bound the approximation ratio, as usual we need a suitable lower bound on the cost of the
optimum solution.
Lemma 13. w(F0∗ ) ≥ (1 + δ)j · (τ − 2p − c).
Proof. When our algorithm contracted a star having ratio r ≥ (1 + δ)j in the largest interval j
in some step t, all stars in Ft∗ with Steiner vertices v1 , . . . , vq as centers had ratios at least r. Thus
if `i is the number of terminals incident to vi in Ft∗ , then these terminals together with vi form
a star of weight at least r · (`i − 1). Similarly, all edges between terminals in Ft∗ have weight at
least r; let `0 be the number of such edges.

11

Since there are at least τ terminals in step t (otherwise the algorithmPwould have terminated),
q
and at most q −1 of edges in Ft∗ connect two Steiner vertices, we have `0 + i=1 `i ≥ τ −c−(q −1) ≥
∗
τ − c − p as p ≥ q. The total weight of edges in Ft is thus at least
`0 r +

q
X

r · (`i − 1) ≥ r · (τ − 2p − c) ≥ (1 + δ)j · (τ − 2p − c) .

i=1

This proves the lemma as w(Ft∗ ) ≤ w(F0∗ ).
Finally, we show that the total weight of bad contracted edge sets is very small compared to
the weight of the optimum, provided that there are still many terminals in the graph during the
last contraction. More precisely, we set
τ := (κ + c) · λ ·

(1 + δ)2
+ 2p + c.
εδ

Lemma 14. The total weight of bad edge sets Ct is at most ε · w(F0∗ ).
Proof. By Lemma 13 and using the value of τ we have
ε · w(F0∗ ) ≥ ε(1 + δ)j · (τ − 2p − c) ≥ ε(1 + δ)j · (κ + c) · λ ·

(1 + δ)j+2
(1 + δ)2
= (κ + c) · λ ·
,
εδ
δ

which is the upper bound on the total weight of bad edges sets by Lemma 12.
The above lemmas can now be used to prove that all the contractions put together (by scaling ε)
form a (1 + ε)-approximate pre-processing procedure (cf. Section 2.2).

Lemma 15. The algorithm outputs an instance with τ ∈ O (p + c)2 /ε4 terminals and (together
with the solution lifting algorithm) it is a (1 + 2ε)-approximate polynomial time pre-processing
algorithm. In case the given p is smaller than the number of Steiner vertices in the optimum, or
c is smaller than its number of connected components, the algorithm still outputs a Steiner forest,
but the approximation factor may be arbitrary.
Proof. By Lemma 7 each step of the algorithm can be executed since τ > p. Thus the upper bound
on the number of terminals follows directly from the description of the algorithm. To bound the run
ning time, we already noted that finding a minimum ratio star to contract can be done in O n2 log n
time. Since such a star with at least two vertices is contracted in each step t to form the next
graph Gt+1 , the total time used for contractions until only τ terminals are left is polynomial in n.
Let us focus on the (1 + 2ε)-approximate part. Let H = Gt̃ be the graph left after the last
contraction step t̃, and let FH be a Steiner forest for the remaining terminal pairs. The solution
lifting algorithm simply adds all contracted edge sets C0 , C1 , . . . to FH in order to compute a Steiner
forest FG in the input graph G. We need to show that, if FH is a β-approximation to the optimum
∗
FH
in H, the resulting forest FG is a ((1 + 2ε)β)-approximation to the optimum FG∗ = F0∗ of G.
Let us call a step t of the algorithm good (bad ) if the corresponding contracted edge set Ct is
good (bad). As all sets Ct are disjoint, using Lemmas 9 and 14 the weight of FG can be bounded by
X
X
X
∗
w(FG ) =
w(Ct ) +
w(Ct ) + w(FH ) ≤
(1 + ε)w(Dt ) + ε · w(FG∗ ) + β · w(FH
).
good t

bad t

good t

The forest Ft̃∗ left after the last contraction corresponds to a feasible solution in H. As the
∗
∗
edge weights might be less expensive in H than in Ft̃∗ , we have w(F
P H ) ≤ w(Ft̃ ). At
P the same
∗
time, the deleted sets Dt and the edges of Ft̃ are disjoint, so that good t w(Dt ) ≤ t w(Dt ) ≤
w(FG∗ ) − w(Ft̃∗ ). Therefore the above bound becomes

w(FG ) ≤ (1 + ε) w(FG∗ ) − w(Ft̃∗ ) + ε · w(FG∗ ) + β · w(Ft̃∗ )

≤ (1 + ε)β w(FG∗ ) − w(Ft̃∗ ) + w(Ft̃∗ ) + ε · w(FG∗ ) ≤ (1 + 2ε)β · w(FG∗ ),
which proves the claim.
12

1
2
3
4
5
6
7
8
9
10

input : undirected graph G = (V, E),
list of terminal pairs {s1 , t1 }, . . . , {sk , tk }, edge weights w(e) ∈ R+
0
output : a forest F ⊆ G such that it contains every si -ti path.
Function BestStar(v )
if v is a terminal then z ← 1
else z ← 0
q1 , . . . , qk ← terminals adjacent to v sorted by the weight of edge vqi
for i in 1, . . . , k do
Pi
ri ← j=1 w(vqi )/(i + z − 1)
return edges {vq1 , . . . , vqi } of star with the smallest ri /* which exists by Lemma 7 */
while number of terminals is at least τ do
C ← arg min{w(Cv ) | Cv ← BestStar(v), v ∈ V }
Contract C

Run FPT algorithm parametrized by the number of terminals
Algorithm 1: An algorithm for solving Steiner Forest. If we stop before Line 11 we obtain
the reduced instance.

11

Algorithm 1 gives a pseudo-code of the resulting algorithm.
Proof of Theorem 4. Obtaining an FPT algorithm for Steiner Forest parameterized by the
number of terminals and connected components is not hard given an FPT algorithm as the one
given in [16] for Steiner Tree: we only need to guess the sets of terminals that form connected
components in the optimum Steiner forest. We can then invoke the algorithm of [16] on each subset
to compute an optimum Steiner tree connecting it. The input to our algorithm is an integer c
upper-bounding the number of components of the optimum. Thus each terminal can be in one of at
most c components, so that there are c|R| partitions of the terminal set R that need to be considered.
The algorithm of [16] runs in time 3|R| · nO(1) , and so this results in an algorithm with runtime
(3c)|R| · nO(1) to solve Steiner Forest. We may run this algorithm on the Steiner Forest
instance that our pre-processing algorithm of Lemma 15 computes, in order to obtain Theorem 4.
Proof of Theorem 5. To obtain our result on lossy kernels we rely on the fact that a PSAKS exists
for Steiner Tree parameterized by the number of terminals. It is known that despite being
FPT [16], this problem does not admit polynomial (exact) kernels [14], unless NP ⊆ coNP/Poly.
However, as shown by Lokshtanov et al. [28], the Borchers and Du Theorem [4] can be reinterpreted
to show that a PSAKS exists. The theorem states that for any optimum Steiner tree T on terminal
set R there exists a collection
of trees T1 , . . . , Tk , each of which contains 2O(1/ε) terminals of R, and
Sk
for which the union i=1 Ti is a (1 + ε)-approximation of T . To obtain a kernel we first preprocess
the input graph by removing any vertex that is far away from any terminal and can therefore never
be part of an optimum Steiner tree. For this a rough estimate of the cost of an optimum Steiner
tree is needed, which can be obtained in polynomial time using existing constant approximation
algorithms for Steiner Tree. The next step is to take the metric closure of the remaining graph,
so that any minimum cost tree connecting 2O(1/ε) terminals only contains 2O(1/ε) Steiner vertices
as well. We then compute an optimum Steiner tree for each subset of R of size 2O(1/ε) and take
their union. Within this union exists the (1 + ε)-approximate Steiner tree due to the Borchers and
O(1/ε)
Du Theorem [4], and the total number of vertices in this union is |R|2
. It is still necessary to
round the edge weights of the resulting instance. It can be shown [28] that this is possible using at
most O (log(|R|) + log(1/ε)) bits, and so that any Steiner tree in the resulting approximate kernel
corresponds to a Steiner tree in the original instance that costs at most a factor of (1 + ε) more.
Obtaining a PSAKS for Steiner Forest can be done in essentially the same way: the Borchers
and Du Theorem [4] can be applied to each tree in the optimum Steiner forest, and a rough estimate
of the cost of an optimum Steiner forest can be obtained via the polynomial time 2-approximation
of Agrawal et al. [1]. Using the same steps as for Steiner Tree, if the Steiner Forest instance

13

O(1/ε)

contains |R| terminal pairs, we obtain an approximate kernel of size |R|2
in which every
optimum Steiner forest corresponds to a Steiner forest in the original instance of cost at most
a factor of (1 + ε) more. Since the number of terminals in the instance that we obtain after
exhaustively applying our contractions is bounded in terms of our parameters p, c, and ε, we may
compute an approximate kernel for these parameters by Lemma 15. This implies Theorem 5.

4

The unweighted directed Steiner tree problem

In this section we provide an EPAS for the Unweighted Directed Steiner Tree problem, in
which each arc has unit weight.

Input:
Solution:

Unweighted Directed Steiner Tree
A directed graph G = (V, A), and a set R of terminals with a root terminal r.
A Steiner arborescence T ⊆ G containing a directed path from r to each terminal
v ∈ R.

The idea behind our algorithm given in this section is to reduce the number of terminals of
the input instance via a set of reduction rules. That is, we would like to reduce the input graph
G to a graph G0 , and prove that the number of terminals in G0 is bounded by a function of our
parameter p and the approximation ratio (1 + ε). On the reduced instance we can use the algorithm
of Björklund et al. [2] to obtain an optimum solution.
Our first reduction rule represents the idea that a terminal in the immediate neighborhood of
the root can be contracted to the root. Observe that in this case our algorithm has to pay 1 for
connecting such a terminal to the root, however, an optimal solution must connect this terminal
as well using at least one arc—this argument is formalized in Lemma 16 (cf. Section 2.2).
Reduction Rule R1. If there is an arc from the root r to a terminal v ∈ R, we contract the
arc (r, v), and declare the resulting vertex the new root.
Lemma 16. Reduction Rule R1 is 1-safe and can be implemented in polynomial time. Furthermore,
there is a solution lifting algorithm running in polynomial time and returning a Steiner arborescence
if it gets a Steiner arborescence of the reduced graph as input.
Proof. The implementation of the reduction rule is straightforward. Let H be a graph resulting
∗
from G after the contraction of the arc (r, v) to the new root r0 , let TH
and TG∗ denote optimal
Steiner arborescences for H and G, respectively, and let TH be a Steiner arborescence in H.
Our solution lifting algorithm constructs a Steiner arborescence TG in G by simply taking TH
and uncontracting (r, v) in it. Note that TG spans all terminals, as TH does in H and we added
(r, v). Also TG is an arborescence, since r has in-degree zero (as r0 has), v has in-degree one, and
TG is clearly a tree. Thus TG is a Steiner arborescence in G.
The solution lifting algorithm adds 1 to the solution value, so that w(TG ) = w(TH ) + 1. Note
∗
that w(TG∗ ) ≥ w(TH
) + 1 as the optimal solution in G must additionally connect v to r, i.e., it has
to add some arc of cost 1. Finally we have


w(TG )
w(TH ) + 1
w(TH ) 1
≤
∗ ) + 1 ≤ max w(T ∗ ) ; 1 ,
w(TG∗ )
w(TH
H
∗
so that if TH is a β-approximation of TH
, then TG is a (max{1; β})-approximation of TG∗ . Hence
the rule is 1-safe.

The idea behind our next reduction rule is the following. Assume there is a Steiner vertex s
in the optimum arborescence T connected to many terminals with paths not containing any other
Steiner vertices. We can then afford to buy all these paths emanating from s together with a path
connecting the root to s. Formally, we say that a vertex u is a k-extended neighbor of some vertex
v, if there exists a directed path P starting in v and ending in u, such that V (P ) \ {v} contains at
14

s

s

0
Figure 4: An example of extended neighborhood of Steiner vertex s. The set NExt
(s) is depicted
on the left using full arcs, while the vertices connected by dotted arcs are not a part of this set.
1
The set NExt
(s) is depicted on the right using full arcs.

most k Steiner vertices. Note that a vertex is always a k-extended neighbor of itself for any k, and
that each of the above terminals connected to s in T is a 0-extended neighbor of s. We denote by
k
NExt
(v) the set of all k-extended neighbors of v, and call it the k-extended neighborhood of v (see
Fig. 4). By the following observation the Steiner vertex s of T lies in the p-extended neighborhood
of the root r. Therefore there is a path containing at most p Steiner vertices connecting r to s.
Observation 17. Let G = (V, A) be a directed graph with root r ∈ R. Suppose there exists a
p
Steiner arborescence T ⊆ G with at most p Steiner vertices. It follows that V (T ) ⊆ NExt
(r).
In what follows we fix ε > 0. The second reduction rule contracts a path from r to a Steiner
vertex s in the p-extended neighborhood of r together with the 0-extended neighborhood of s if
this neighborhood is sufficiently large.
p
0
Reduction Rule R2. If there exists a Steiner vertex s with NExt
(r) so
(s) ≥ p/ε and s ∈ NExt
that there is an r → s path P containing at most p Steiner vertices, then we contract the subgraph
0
of G induced by NExt
(s) and P in G, and declare the resulting vertex the new root.

Lemma 18. Reduction Rule R2 is (1 + ε)-safe and can be implemented in polynomial time. Furthermore, there is a solution lifting algorithm running in polynomial time and returning a Steiner
arborescence if it gets a Steiner arborescence of the reduced graph as input.
0
Proof. Checking the applicability of Rule R2 and finding s together with NExt
(s) can be done in
polynomial time as follows. We set arc lengths so that each arc ending at a terminal has length
zero, while arcs ending at Steiner vertices have length one. Now a length of a directed path P
from the root corresponds to the number of Steiner vertices in P . Then we run an algorithm for
p
finding a shortest path from r to each vertex which allows us to find the set NExt
(r). Finally, for
p
0
each s ∈ NExt (r) we compute NExt
(s) by a simple breadth-first search.
We now specify the solution lifting algorithm. Denote by H the reduced graph obtained from
∗
G by applying R2. Let TH be a solution of the reduced instance H and let TH
be an optimal
solution in H. Consider the graph Q, which is the union of P and the subgraph of G induced by
0
NExt
(s). The solution lifting algorithm first computes an arborescence A of Q rooted in r (e.g.,
0
by a depth-first search). It then takes TH , uncontracts NExt
(s) ∪ V (P ), and adds the arcs in A
to TH ; let TG be the resulting graph. We show that TG is a Steiner arborescence.
First observe that TG spans all terminals as TH contains all terminals in H and A is an
arborescence containing all vertices in Q. Note that TG is a tree as A is an arborescence of Q, TH
is a tree, and TH contains at most one arc from the root in H to each vertex (recall that the root
0
in H was created by contracting NExt
(s) ∪ V (P )). The root in TG has clearly in-degree zero, while
all other vertices have in-degree one, since this holds for H as TH is an arborescence, and A is an
arborescence of Q rooted in r. Thus TG is a Steiner arborescence in G.
It remains to show the safeness of the rule. Let x be the total number of terminals in
0
NExt
(s)∪V (P ) (not counting the root). Note that w(TG ) ≤ w(TH )+x+p. We obtain a solution for
H of weight at most w(TG∗ )−x by starting with TG∗ , removing x arcs each having one of the x non-root
0
0
terminals in NExt
(s) ∪ V (P ) (and thus not in H) as their head, identifying all vertices in NExt
(s) ∪

15

∗
V (P ) with the new root, and removing loops and parallel arcs. Thus w(TG∗ ) ≥ w(TH
)+x and we get




w(TH ) + x + p
w(TH ) x + p
w(TH )
w(TG )
≤
≤ max
≤ max
∗)+x
∗ );
∗ ); 1 + ε .
w(TG∗ )
w(TH
w(TH
x
w(TH
∗
The last inequality is valid because x ≥ p/ε. Thus if TH is a β-approximation of TH
, then TG is
a (max{1 + ε; β})-approximation of TG∗ , and so the reduction rule is (1 + ε)-safe.

Now we prove that if none of the above reduction rules is applicable and our algorithm was
provided with a correct value for parameter p, then the number of terminals in the reduced graph
can be bounded by p2 /ε.
Lemma 19. Let G be an instance of Directed Steiner Tree, and denote by H the graph
obtained from G by exhaustive application of Reduction Rules R1 and R2. Suppose that there exists
an optimal Steiner arborescence in G containing at most p Steiner vertices. It follows that the
remaining terminal set R of H has size less than p2 /ε.
Proof. Observe first that both our reduction rules use contractions in the underlying graph and
∗
thus if there was a solution TG∗ in G with at most p Steiner vertices, then there is a solution TH
in H again containing at most p Steiner vertices.
0
Since Reduction Rule R1 is not applicable to H, we conclude that NExt
(r) ∩ R = ∅. As
0
Reduction Rule R2 is not applicable to H it holds that NExt
(s) ∩ R < p/ε for every Steiner
p
vertex s ∈ NExt
(r). Therefore |R| < p2 /ε, since any terminal in H must be in the 0-extended
∗
∗
neighborhood of some Steiner vertex in TH
and there are at most p Steiner vertices in TH
.
The last step of the algorithm (cf. proof of Theorem 2) is to compute an optimum solution in
the graph H obtained from the input graph G after exhaustively applying the two above reduction
rules. From the resulting arborescence in H we obtain an arborescence in G by running the
solution lifting algorithms for each reduction rule applied (in the reverse order); the existence and
correctness of the solution lifting algorithms for our reduction rules is provided by Lemmas 16
and 18. The algorithm is summarized in Algorithm 2.
input : directed graph G = (V, A), terminals R ⊆ V , root r ∈ R, and integer p
output : Steiner arborescence T ⊆ G, if p is at most the nr. of terminals in the optimum
1
2
3
4
5
6

7

8
9

p
if R \ NExt
(r) 6= ∅ then /* no solution with at most p Steiner vertices
return “no”

while Reduction Rule R1 or R2 is applicable do
if there is an arc from r to v ∈ R then /* Reduction Rule R1
Contract the arc (r, v), and declare the resulting vertex the new root.
p
0
(s) ≥ p/
if there exists s ∈ V \ R with s ∈ NExt
(r) and NExt
then /* Reduction Rule R2
Find an r → s path P with at most p Steiner vertices. Contract the subgraph
0
of G induced by NExt
(s) and P , and declare the resulting vertex the new root.

if |R| > p2 /ε then /* no solution with at most p Steiner vertices
return “no”

*/

*/

*/

*/

Run the FPT algorithm of [2] and let T be the returned solution.
In the reverse order of application of Reduction Rules R1 and R2:
12
Revert the contraction of the reduction rule.
13
Run the solution lifting algorithm for the reduction rule on T .
14
Store the resulting arborescence in T .
15 return T
Algorithm 2: Algorithm for solving Directed Steiner Tree. As explained earlier, all steps
except Line 10 can be implemented in polynomial time.
10
11

16

root
d
1
c

e

b

f

a

b

c

d

e

f

0

a
a

b

c

d

e

f

Figure 5: An example for the reduction. A graph G with its dominating set U = {c, e} on the
left. The corresponding instance of Directed Steiner Tree to the right.
Proof of Theorem 2. If neither Reduction Rule R1 nor R2 is applicable and the current number of
terminals exceeds the bound p2 /ε we can return “no” as it follows from Lemma 19 that no optimal
solution with at most p Steiner vertices exists. If this is not the case we return an optimal solution
using the algorithm of [2], which runs in time 2|R| · nO(1) where R is the current set of terminals with
size at most p2 /ε. As explained earlier both reduction rules can be implemented in polynomial time,
2
together with their solution lifting algorithms. Thus the total running time is 2p /ε · nO(1) . The
approximation guarantee and correctness of the obtained solution follow from Lemmas 16 and 18.

5

The weighted directed Steiner tree problem

Here we prove that the standard reduction from the Dominating Set problem to the Directed
Steiner Tree problem (with arc weights) translates into inapproximability of the latter problem.
By a recent result [9], there is no constant approximation algorithm for the Dominating Set
problem, even when parametrizing by the size of the optimum solution, unless W[1] = FPT.

Input:
Solution:

Dominating Set
an undirected graph G = (V, E).
the smallest dominating set U ⊆ V for which every v ∈ V either is in U or v has a
neighbour in U .

Proof of Theorem 3. We give a parameterized reduction from the Dominating Set problem
parameterized by the size of the solution U , which we denote by b = |U |.
For an overview of the reduction please refer to Fig. 5. Let G = (V, E) be a graph in which we
are searching for the smallest dominating set of size b and let n = |V | and m = |E|. We create an
instance of Directed Steiner Tree having 2n + 1 vertices and n + 2m arcs as follows. There are
n terminals, each corresponding to a vertex in V , one auxiliary terminal (the root), and n Steiner
vertices again corresponding to vertices in V . There are arcs of two kinds. The first kind of arcs are
of weight 1 and connect the root to each Steiner vertex, i.e., they are directed towards the Steiner
vertices. The second kind of arcs are of weight 0 and connect the Steiner vertices with the terminals,
directed towards the terminals. There is an arc from each Steiner vertex corresponding to a vertex
w ∈ V to every terminal corresponding to a vertex v ∈ V if v = w or v is a neighbour of w in G.
Observe that there is a dominating set of size b in G if and only if there is an arborescence
connecting the root to all terminals of cost b. Note also that this arborescence contains b Steiner
vertices. Thus we set the parameter p to value b.
Suppose that there is a parameterized α-approximation algorithm for the Directed Steiner
Tree problem for parameter p, where α is some constant. Then, we would obtain a parameterized
17

α-approximation algorithm for the Dominating Set problem parameterized by the size b of the
solution. This would imply W[1] = FPT by [9].
Acknowledgements. We would like to thank Michael Lampis and Édouard Bonnet for helpful
discussions on the problem.

References
[1] Ajit Agrawal, Philip N. Klein, and R. Ravi. When Trees Collide: An Approximation Algorithm
for the Generalized Steiner Problem on Networks. SIAM J. Comput., 24(3):440–456, 1995.
[2] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets
Möbius: fast subset convolution. In STOC, pages 67–74, 2007.
[3] Edouard Bonnet, Bruno Escoffier, EunJung Kim, and Vangelis T. Paschos. On subexponential
and FPT-time inapproximability. In IPEC, pages 54–65, 2013.
[4] Al Borchers and Ding-Zhu Du. The k-Steiner Ratio in Graphs. SIAM Journal on Computing,
26(3):857–869, 1997.
[5] Glencora Borradaile, Philip N. Klein, and Claire Mathieu. An O(n log n) approximation
scheme for Steiner tree in planar graphs. ACM Transactions on Algorithms, 5(3), 2009.
[6] Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree
approximation via iterative randomized rounding. Journal of the ACM, 60(1):6, 2013.
[7] Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi,
Danupon Nanongkai, and Luca Trevisan. From Gap-ETH to FPT-Inapproximability: Clique,
Dominating Set, and More. In To appear in FOCS, 2017.
[8] Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha,
and Ming Li. Approximation algorithms for directed Steiner problems. J. Algorithms, 33
(1):73–91, 1999.
[9] Yijia Chen and Bingkai Lin. The constant inapproximability of the parameterized dominating
set problem. In FOCS, pages 505–514, 2016.
[10] Rajesh Chitnis, MohammadTaghi Hajiaghayi, and Guy Kortsarz. Fixed-parameter and
approximation algorithms: A new look. In IPEC, pages 110–122, 2013.
[11] Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. Parameterized approximation
algorithms for directed steiner network problems. arXiv preprint arXiv:1707.06499, 2017.
[12] Miroslav Chlebı́k and Janka Chlebı́ková. Approximation hardness of the Steiner tree problem
on graphs. In SWAT 2002, pages 170–179.
[13] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin
Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
[14] Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization Lower Bounds Through
Colors and IDs. ACM Trans. Algorithms, 11(2):13:1–13:20, 2014.
[15] Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer-Verlag,
New York, 1999.
[16] Stuart E. Dreyfus and Robert A. Wagner. The Steiner problem in graphs. Networks, 1(3):
195–207, 1971.

18

[17] Eduard Eiben, Mithilesh Kumar, Amer E Mouawad, and Fahad Panolan. Lossy kernels for
connected dominating set on sparse graphs. arXiv preprint arXiv:1706.09339, 2017.
[18] David Eisenstat, Philip Klein, and Claire Mathieu. An efficient polynomial-time approximation
scheme for Steiner forest in planar graphs. In SODA 2012, pages 626–638.
[19] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM),
45(4):634–652, 1998.
[20] Andreas Emil Feldmann. Fixed parameter approximations for k-center problems in low
highway dimension graphs. In ICALP, pages 588–600, 2015.
[21] Andreas Emil Feldmann and Dániel Marx. The Complexity Landscape of Fixed-Parameter
Directed Steiner Network Problems. In ICALP, pages 27:1–27:14, 2016.
[22] Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In STOC, pages
585–594, 2003.
[23] Frank K Hwang, Dana S Richards, and Pawel Winter. The Steiner tree problem, volume 53.
Elsevier, 1992.
[24] Mark Jones, Daniel Lokshtanov, MS Ramanujan, Saket Saurabh, and Ondřej Suchý.
Parameterized complexity of directed steiner tree on sparse graphs. In European Symposium
on Algorithms (ESA), pages 671–682. Springer, 2013.
[25] Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer
computations, pages 85–103. Plenum, 1972.
[26] R Krithika, Pranabendu Misra, Ashutosh Rai, and Prafullkumar Tale. Lossy kernels for graph
contraction problems. In LIPIcs-Leibniz International Proceedings in Informatics, volume 65.
Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
[27] Michael Lampis. Parameterized approximation schemes using graph widths. In ICALP, pages
775–786, 2014.
[28] Daniel Lokshtanov, Fahad Panolan, MS Ramanujan, and Saket Saurabh. Lossy Kernelization.
In STOC, pages 224–237, 2017.
[29] Dániel Marx. Parameterized complexity and approximation algorithms. The Computer
Journal, 51(1):60–78, 2008.
[30] Daniel Mölle, Stefan Richter, and Peter Rossmanith. Enumerate and expand: Improved
algorithms for connected vertex cover and tree cover. Theory of Computing Systems, 43(2):
234–253, 2008.
[31] Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network
Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. In FOCS, pages
276–285, 2014.
[32] Sebastian Siebertz. Lossy kernels for connected distance-r domination on nowhere dense
graph classes. arXiv preprint arXiv:1707.09819, 2017.
[33] Ondřej Suchý. Extending the kernel for planar steiner tree to the number of steiner vertices.
Algorithmica, 79(1):189–210, 2017.
[34] Andreas Wiese. A (1 + )-approximation for unsplittable flow on a path in fixed-parameter
running time. In ICALP 2017, pages 67:1–67:13.
[35] David P Williamson and David B Shmoys.
Cambridge university press, 2011.
19

The design of approximation algorithms.

