Dijkstra meets Steiner: a fast exact goal-oriented
Steiner tree algorithm
Stefan Hougardy, Jannik Silvanus, and Jens Vygen

arXiv:1406.0492v3 [] 8 Sep 2015

Research Institute for Discrete Mathematics, University of Bonn
{hougardy, silvanus, vygen}@or.uni-bonn.de

Abstract. We present a new exact algorithm for the Steiner tree problem in
edge-weighted graphs. Our algorithm improves the classical dynamic programming approach by Dreyfus and Wagner. We achieve a significantly better practical performance via pruning and future costs, a generalization of a well-known
concept to speed up shortest path computations. Our algorithm matches the best
known worst-case run time and has a fast, often superior, practical performance:
on some large instances originating from VLSI design, previous best run times are
improved upon by orders of magnitudes. We are also able to solve larger instances
of the d-dimensional rectilinear Steiner tree problem for d ∈ {3, 4, 5}, whose Hanan
grids contain up to several millions of edges.
Keywords: Graph algorithms; Steiner tree problem; Dynamic programming; Exact algorithm

1

Introduction

We consider the well-known Steiner tree problem (in graphs): Given an undirected graph
G, costs c : E(G) → R≥0 and a terminal set R ⊆ V (G), find a tree T in G such that
R ⊆ V (T ) and c(E(T )) is minimum. The decision version of the Steiner tree problem is
one of the classical NP-complete problems [22]; it is even NP-complete in the special case
that G is bipartite with c ≡ 1. Furthermore, it is NP-hard to approximate the Steiner
tree problem within a factor of 96
95 [6]. The currently best known approximation algorithm
by Byrka et al. [5] uses polyhedral methods to achieve a 1.39-approximation. The Steiner
tree problem has many applications, in particular in VLSI design [20], where electrical
connections are realized by Steiner trees.
From now on, we will refer to |V (G)| by n, |E(G)| by m and |R| by k. Dreyfus
and Wagner [9] applied dynamic programming to the Steiner tree problem to obtain an
exact algorithm with a run time of O(n(n log n + m) + 3k n + 2k n2 ) if implemented using
Fibonacci heaps [14]. In 1987, Erickson, Monma and Veinott [11] improved the run time
to O(3k n + 2k (n log n + m)) using a very similar approach. In 2006, Fuchs et al. [15]
ζ
1
proposed an algorithm with a run time of O((2 + δ)k n(ln( δ )/δ) ) for every sufficiently
small δ > 0 and ζ > 21 , improving the exponential dependence on k from 3k to (2 + δ)k .
Vygen [33] developed an algorithm with a worst-case run time of O(nk2k+log2 (k) log2 (n) ),
which is the fastest known algorithm if f (n) < k < g(n) for some f (n) = polylog(n)
and g(n) = n2 − polylog(n). However, for k < 4 log n, the run time obtained by Erickson,
Monma and Veinott [11] is still the best known. See [33] for a more detailed analysis of
the run times mentioned above.

2

For graphs with treewidth t, one can solve the Steiner tree problem in time O(n2O(t) )
[4]. An implementation of this algorithm was evaluated in [12]. Polzin and Vahdati
Daneshmand [26] proposed an algorithm with a worst-case run time of O(n2p log p+3p+log p )
where p is a parameter closely related to the pathwidth of G. They use this algorithm as
a subroutine in their successful reduction-based Steiner tree solver [24, 32].
Except for the last mentioned algorithm, these results have played a very limited role
in practice. Instead, empirically successful algorithms rely on preprocessing and reduction
techniques, heuristics and branching: First, reductions [3, 10, 25, 31] are applied to reduce
the size of the graph and the number of terminals, guaranteeing that optimum solutions
of the reduced instance correspond to optimum solutions of the original instance. These
reductions are not limited to simple local edge elimination tests, but may also rely on
linear programming formulations and optimum solutions of partial instances. Primal and
dual [2, 35] heuristics yield good upper and lower bounds, in many cases even resulting
in a provably optimum solution. If these methods do not already solve the instance,
enumerative algorithms are used. To this end, various authors [2, 7, 23] perform branch
and cut. However, the solver by Polzin and Vahdati Daneshmand [24, 32], which achieved
the best results so far, uses a branch and bound approach, where high effort is put into
single branching nodes.
We propose a dynamic programming based algorithm with a worst-case run time of
O(3k n + 2k (n log n + m)), matching the best known bound for small k, and which is
fast in practice. Good practical performance is achieved by effectively pruning partial
solutions and using future cost estimates. The latter are motivated by the similarity
of our algorithm with Dijkstra’s algorithm [8] and the well-known speed-up technique
for Dijkstra’s algorithm (first described by Hart, Nilsson and Raphael [17]) which uses
reduced edge costs. More precisely, given an instance (G, c, s, t) of the shortest path
problem, where we assume G to be a directed graph, we use a feasible potential π, which
is a function π : V (G) → R≥0 with
π(t) = 0

(1)

π(v) ≤ π(w) + c((v, w))

(2)

and

for all (v, w) ∈ E(G). Define reduced costs cπ by
cπ (e) := c(e) + π(w) − π(v) ≥ 0

(3)

for every e = (v, w) ∈ E(G). Then, run Dijkstra’s algorithm on the instance (G, cπ , s, t).
The numbers π(v) are lower bounds on the distance from v to t (we also say that π(v)
estimates the future cost at v). Moreover, the cost of every s-t-path changes by the same
amount when going from c to cπ , namely −π(s), so any shortest s-t-path in (G, cπ ) is a
shortest s-t-path in (G, c). If the future costs are good lower bounds, only vertices close
to a shortest path will be labeled by Dijkstra’s algorithm before t is labeled permanently
(i.e., the distance to t is known) and the algorithm can be stopped. This can lead to huge
speedups.
The rest of this paper is organized as follows: In Section 2, we generalize this future
cost idea from paths to Steiner trees and describe our algorithm. Examples of future
cost estimates are given in Section 3. Section 4 introduces a pruning technique to further
improve practical performance. Section 5 contains implementation details and computational results.

3

2

The Algorithm

Now, let (G, c, R) be an instance of the Steiner tree problem, where G is an undirected
graph, c : E(G) → R≥0 is a cost function on the edges and R is the set of terminals to be
connected. As usual, for a set X ⊆ V (G), we denote by smt(X), short for Steiner minimal
tree, the cost of an optimum Steiner tree for the terminal set X. Our algorithm uses an
arbitrary root terminal r0 ∈ R. We will call the terminals in R \ {r0 } source terminals.
The algorithms by Dreyfus and Wagner [9] and Erickson et al. [11] as well as our algorithm
use dynamic programming to compute smt({v} ∪ I) for (v, I) ∈ V (G) × 2R\{r0 } . Then,
at termination, smt({r0 } ∪ (R \ {r0 })) is the cost of an optimum Steiner tree.
The former two algorithms work as follows: For each i from 1 to |R \ {r0 }|, they
consider all I ⊆ R \ {r0 } with |I| = i one after another and then compute smt({v} ∪ I)
for all v ∈ V (G). This way, it is guaranteed that when computing smt({v}∪I), the values
smt({w} ∪ I 0 ) for all w ∈ V (G) and I 0 ⊂ I are already known. However, this leads to
an exponential best case run time and memory consumption of Ω(2k n). In contrast, our
new algorithm considers all subsets of source terminals simultaneously, using a labeling
technique similar to Dijkstra’s algorithm. This way, we do not necessarily have to compute
smt({v} ∪ I) for all pairs (v, I).
Our new algorithm labels from the source terminals towards the root r0 . More precisely, the algorithm labels elements of V (G) × 2R\{r0 } . Each label (v, I) represents an
optimum Steiner tree for {v} ∪ I found so far. As in Dijkstra’s algorithm, each iteration selects one label (v, I) and declares it to be permanent. Each time a label (v, I)
becomes permanent, all neighbors w of v are checked and updated if the Steiner tree
represented by (v, I) plus the edge {v, w} leads to a better solution for (w, I) than previously known. This operation is well-known from Dijkstra’s algorithm. In addition, for
all sets J ⊆ (R \ {r0 }) \ I it is checked whether the Steiner trees for (v, I) and (v, J)
combined to a tree for (v, I ∪ J) lead to a better solution than previously known.
To allow a simpler presentation, we restrict ourselves to instances without edges of
zero cost, as these can be contracted in a trivial preprocessing step.
Now, we introduce the notion of valid lower bounds, which are used by the algorithm
to estimate the future cost of a label (v, I).
Definition 1. Let (G, c, R) be an instance of the Steiner tree problem and r0 ∈ R. A
function L : V (G) × 2R → R≥0 is called a valid lower bound if
L(r0 , {r0 }) = 0
and
L(v, I) ≤ L(w, I 0 ) + smt((I \ I 0 ) ∪ {v, w})
for all v, w ∈ V (G) and {r0 } ⊆ I 0 ⊆ I ⊆ R.
Note that the values L(v, I) for r0 ∈
/ I do not affect whether L is a valid lower bound.
Also note that by choosing I 0 = {r0 } and w = r0 , we have L(v, I) ≤ smt(I ∪ {v}), so
a valid lower bound by definition indeed is a lower bound on the cost of an optimum
Steiner tree. Moreover, if e = {v, w} ∈ E(G) is an edge, by choosing I 0 = I, we have
L(v, I) ≤ L(w, I) + smt({v, w}) ≤ L(w, I) + c(e).

4

Dijkstra-Steiner Algorithm
Input : A connected undirected graph G, costs c : E(G) → R>0 , a terminal set
R ⊆ V (G), a root terminal r0 ∈ R, and (an oracle to compute) a valid lower
bound L : V (G) × 2R → R≥0 .
Output: The edge set of an optimum Steiner tree for R in G.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

27
28
29
30
31

l(v, I) := ∞ for all (v, I) ∈ V (G) × 2R\{r0 } ;
l(s, {s}) := 0 for all s ∈ R \ {r0 };
l(v, ∅) := 0 for all v ∈ V (G);
b(v, I) := ∅ for all (v, I) ∈ V (G) × 2R\{r0 } ;
N
:= {(s, {s}) | s ∈ R \ {r0 }};
P
:= V (G) × {∅};
while (r0 , R \ {r0 }) ∈
/ P do
Choose (v, I) ∈ N minimizing l(v, I) + L(v, R \ I);
N := N \ {(v, I)};
P := P ∪ {(v, I)};
for all edges e = {v, w} incident to v do
if l(v, I) + c(e) < l(w, I) and (w, I) ∈
/ P then
l(w, I) := l(v, I) + c(e);
b(w, I) := {(v, I)};
N
:= N ∪ {(w, I)};
end
end
for all ∅ 6= J ⊆ (R \ {r0 }) \ I with (v, J) ∈ P do
if l(v, I) + l(v, J) < l(v, I ∪ J) and (v, I ∪ J) ∈
/ P then
l(v, I ∪ J) := l(v, I) + l(v, J);
b(v, I ∪ J) := {(v, I), (v, J)};
N
:= N ∪ {(v, I ∪ J)};
end
end
end
return backtrack(r0 , R \ {r0 });
Procedure backtrack(v, I)
if b(v, I) = {(w, I)} then
return {{v, w}} ∪ backtrack(w, I);
else
S
return (w,I 0 )∈b(v,I) backtrack(w, I 0 );
end
Fig. 1. The Dijkstra-Steiner Algorithm

This shows that valid lower bounds generalize feasible potentials as defined in (1) and
(2). In fact, our algorithm applied to the case |R| = 2 is identical to Dijkstra’s algorithm
using future costs in the very same way.
Our new algorithm is described in Figure 1. For each label (v, I) ∈ V (G)×2R\{r0 } , the
algorithm stores the cost l(v, I) ∈ R≥0 ∪{∞} of the cheapest Steiner tree for {v}∪I found
so far as well as backtracking data b(v, I) ⊆ V (G)×2R\{r0 } which is used to construct the
Steiner tree represented by this label. If b(v, I) is not empty, it will always either be of the
form b(v, I) = {(w, I)} where w is a neighbor of v or of the form b(v, I) = {(v, I1 ), (v, I2 )}

5

where I1 and I2 form a partition of I (into nonempty disjoint sets). In the first case, i.e.,
b(v, I) = {(w, I)}, the Steiner tree represented by the label (v, I) contains exactly one
edge incident to v, which is {v, w}. In the second case, i.e., b(v, I) = {(v, I1 ), (v, I2 )}, the
Steiner tree represented by (v, I) can be split into two Steiner trees for the terminal sets
I1 ∪ {v} and I2 ∪ {v}, where I1 and I2 form a partition of I. To be precise, it may happen
that the subgraph of G corresponding to some label (v, I) contains cycles. However,
since we ruled out edges of zero cost, this can only be the case as long as the label is not
permanent, because – as we will show – permanent labels correspond to optimal Steiner
trees.
We incorporate the valid lower bound L into the algorithm as follows. First note
that instead of running Dijkstra’s algorithm on reduced edge costs cπ as defined in
(3), one can equivalently apply the following modification. For a vertex v ∈ V (G), we
denote by l(v) the cost of a label v in Dijkstra’s algorithm, i.e., the cost of a shortest
path connecting s with v found so far. Then, in each iteration, instead of choosing a
non-permanent vertex v minimizing l(v) to become permanent, choose a non-permanent
vertex minimizing l(v) + π(v). We generalize this approach by always choosing a nonpermanent label minimizing l(v, I) + L(v, R \ I).
By P ⊆ V (G) × 2R\{r0 } we denote the set of permanently labeled elements. We also
maintain a set N of non-permanent labels which are candidates to be selected. The set N
contains exactly the labels (v, I) ∈ (V (G)×2R\{r0 } )\P with l(v, I) < ∞. Note that L ≡ 0
is always a valid lower bound, which may serve as an example to help understanding the
algorithm. Other examples of valid lower bounds will be discussed in Section 3.
Theorem 2. The Dijkstra-Steiner algorithm works correctly: Given an instance (G, c, R)
of the Steiner tree problem, r0 ∈ R, and a valid lower bound L, it always returns the edge
set of an optimum Steiner tree for R in G.
Proof. We will prove that the following invariants always hold when line 8 is executed:
(a) For each (v, I)(∈ N ∪ P :
c({v, w}) + l(w, I) if b(v, I) = {(w, I)},
(a1) l(v, I) = P
l(v, J) otherwise,
(v,J)∈b(v,I)
S
(a2) I ∪ {v} = {v} ∪ (w,J)∈b(v,I) J,
(a3) b(v, I) ⊆ P , and backtrack(v, I) returns the edge set F of a connected subgraph
of G containing {v} ∪ I with c(F ) ≤ l(v, I).
(b) For each (v, I) ∈ P :
l(v, I) = smt({v} ∪ I).
(c) For each (v, I) ∈ (V (G) × 2R\{r0 } ) \ P :
(c1) l(v, I) ≥ smt({v} ∪ I),
(c2) If I = {v}, then l(v, I) = 0, otherwise
l(v, I) ≤ min{v,w}∈E(G),(w,I)∈P (l(w, I) + c({v, w})) and
l(v, I) ≤ min∅6=I 0 ⊂I and (v,I 0 ),(v,I\I 0 )∈P (l(v, I 0 ) + l(v, I \ I 0 )).
(c3) If l(v, I) = smt({v} ∪ I), then (v, I) ∈ N .
(d) N is not empty and N ∩ P = ∅.
Assuming (a) – (d), the correctness of the algorithm directly follows: Once we have
(r0 , R \ {r0 }) ∈ P , (b) implies l(r0 , R \ {r0 }) = smt({r0 } ∪ (R \ {r0 })) = smt(R). Furthermore, (a3) implies that the algorithm returns the edge set F of a connected subgraph
of G containing R with c(F ) ≤ l(r0 , R \ {r0 }) = smt(R). Since there are no edges of zero

6

cost, F indeed is the edge set of a tree. Invariant (d) guarantees that in each iteration, a
label (v, I) ∈ N can be chosen and that the algorithm terminates, since |P | is increased
in each iteration.
Clearly, after line 6 these invariants hold. We have to prove that lines 8 to 24 preserve
(a) – (d). Below, we first verify that (a) and (c) are preserved. Then, the main part of
the proof shows that (b) is preserved. Finally, we will see that the latter argument also
shows that (d) is preserved.
Let (v, I) be the label chosen in line 8 in some iteration. Clearly, lines 8 to 24 preserve (a2),
(a3), (c2) and (c3). If a label l(w, I) or l(v, I ∪ J) is decreased, it cannot be permanent,
so (a1) is maintained.
We now consider (c1). Since (c) held before the current iteration, we have l(v, I) ≥
smt({v} ∪ I). This directly implies
l(v, I) + c({v, w}) ≥ smt({v} ∪ I) + c({v, w})
≥ smt({v, w} ∪ I)
≥ smt({w} ∪ I),
so line 13 does not destroy (c1). Also, if ∅ =
6 J ⊆ (R \ {r0 }) \ I is a set chosen in line 18
leading to the change of l(v, I ∪ J), we have
l(v, I ∪ J) = l(v, I) + l(v, J)
≥ smt({v} ∪ I) + smt({v} ∪ J)
≥ smt({v} ∪ I ∪ J),
so (c1) indeed is preserved.
In order to prove that (b) is preserved, we now show that l(v, I) ≤ smt({v} ∪ I), which
together with (c1) yields the desired result. Since l(v, {v}) = 0 = smt({v}), we can
assume I 6= {v}. Let T be an optimum Steiner tree for {v} ∪ I in G. Then, all leaves of
T are contained in {v} ∪ I. For a vertex w ∈ V (T ), let Tw be the subtree of T containing
all vertices x for which the unique x-v-path in T contains w.
We will now show that there is a vertex w ∈ V (T ), a nonempty terminal set I 0 ⊆ I∩V (Tw )
and a subtree T 0 of Tw such that
(I)
(II)
(III)
(IV)

(w, I 0 ) ∈ N ,
l(w, I 0 ) = c(T 0 ) = smt({w} ∪ I 0 ),
T 0 is a subtree of Tw containing I 0 ∪ {w},
T − T 0 is a tree containing (I \ I 0 ) ∪ {v, w}.

Here, by T − T 0 , we refer to the graph ((V (T ) \ V (T 0 )) ∪ {w}, E(T ) \ E(T 0 )). Assuming
we have a triple (w, I 0 , T 0 ) satisfying (I) – (IV), l(v, I) ≤ smt({v} ∪ I) can easily be
proved: Since L is a valid lower bound, we have
L(w, R \ I 0 ) ≤ L(v, R \ I) + smt((I \ I 0 ) ∪ {v, w})
≤ L(v, R \ I) + c(T − T 0 )

(4)
0

= L(v, R \ I) + c(T ) − c(T ).
Adding (II) and (4) yields
l(w, I 0 ) + L(w, R \ I 0 ) ≤ c(T ) + L(v, R \ I).

7

By (I) and the choice of (v, I) in line 8 we have
l(v, I) + L(v, R \ I) ≤ l(w, I 0 ) + L(w, R \ I 0 ),
so
l(v, I) ≤ c(T ).
It remains to be shown that there is such a triple (w, I 0 , T 0 ). We call w ∈ V (T ) proper
if (w, I ∩ V (Tw )) ∈ P before the execution of line 24. If we have a leaf w ∈ V (T ) \ {v}
which is not proper, we set I 0 = {w} and T 0 = ({w}, ∅), satisfying (I) – (IV). Note that
here (I) follows from (c3). Otherwise, since v is not proper, there is a vertex w in T which
is not proper but all neighbors wi of w in Tw are proper. We define
(
{I ∩ V (Twi ) | wi is neighbor of w in Tw } ∪ {{w}} if w ∈ I,
J =
{I ∩ V (Twi ) | wi is neighbor of w in Tw }
if w ∈
/ I.
0
Note that J is aSpartition
subset
 of I ∩ V (Tw ). Let J be an inclusion-wise minimal
of J such that w, J∈J 0 J ∈
/ P . Since w is not proper and (w, ∅) ∈ P , J 0 exists and
J 0 is not empty. For J ∈ J 0 , let TJ be the unique minimum connected subgraph of T
such that ({w} ∪ J) ⊆ V (TJ ). By optimality of T , TJ is an optimum Steiner tree for
({w} ∪ J), as the only vertex in TJ which is incident to edges in E(T ) \ E(TJ ) is w. We
define
S
(i) I 0 = J∈J
S0 J,
(ii) V (T 0 ) = SJ∈J 0 V (TJ ) and
(iii) E(T 0 ) = J∈J 0 E(TJ ).

See Figure 2 for an illustration of this setting.

v

T0

w

w1

w3
w2

Fig. 2. A possible configuration with J 0 = {I ∩ V (Tw1 ), I ∩ V (Tw2 )}. Vertices in I are drawn
as squares, proper vertices are drawn in blue.

8

The conditions (III) and (IV) are satisfied by construction. We now show (II), which
due do (c3) also implies (I). First, we deal with the case |J 0 | = 1. If J 0 = {{w}}, by
(c2) clearly l(w, I 0 ) = 0 = c(T 0 ). If J 0 = {I ∩ V (Twi )} for some neighbor wi of w in Tw ,
by (c2), (b), and the fact that wi is proper, we have
l(w, I 0 ) ≤ l(wi , I 0 ) + c({wi , w})
= smt({wi } ∪ I 0 ) + c({wi , w})
= c(Twi ) + c({wi , w})
= c(T 0 ).
Otherwise, i.e., |J 0 | > 1, choose an element J ∈ J 0 and see again by (c2), (b) and the
minimality of J 0 that
l(w, I 0 ) ≤ l(w, I 0 \ J) + l(w, J)
= smt({w} ∪ (I 0 \ J)) + smt({w} ∪ J)
= c(T 0 − TJ ) + c(TJ )
= c(T 0 ).
As T is an optimum Steiner tree for {v} ∪ I, by (IV) we get c(T 0 ) = smt({w} ∪ I 0 ),
together with (c1) showing (II). By (c3), (w, I 0 ) ∈ N , so (I) holds as well, completing the
proof that (b) is preserved by lines 8 to 24.
To see that (d) is maintained, note that applying the previous argument to (r0 , R \ {r0 })
instead of (v, I) always yields a label (w, I 0 ) ∈ N , so N is not empty. Also, whenever a
label (v, I) is inserted to P , it is removed from N . By (b), from then on l(v, I) cannot
be changed, so (v, I) is never inserted again into N .
t
u
Note that in line 8, one can actually choose any label (v, I) ∈ N with l(v, I) + L(v, R \
I) ≤ l(w, J) + L(w, R \ J) for all (w, J) ∈ (V (G) × 2I ) ∩ N . This is a generalization of the
choice as specified in the algorithm. However, in our implementation, we always choose
a label minimizing l(v, I) + L(v, R \ I).
Theorem 3. The Dijkstra-Steiner algorithm can be implemented to run in O(3k n +
2k (n log n + m) + 2k nfL ) time, where n = |V (G)|, m = |E(G)|, k = |R|, and fL is an
upper bound on the time required to evaluate L.
Proof. Since |P | increases in each iteration, we have at most n2k−1 iterations. We use
a Fibonacci heap [14] to store all labels (v, I) ∈ N , which allows updates in constant
amortized time. Since the heap contains at most 2k−1 n elements, each execution of line 8
takes O(log(2k−1 n)) = O(k + log(n)) amortized time. Line 12 is executed at most 2k m
times and each execution takes O(1) amortized time. Furthermore, there are exactly
3k−1 pairs I, J ⊆ R \ {r0 } with I ∩ J = ∅, since every element in R \ {r0 } can either be
contained in I, J or (R \ {r0 }) \ (I ∪ J), independently of the others. Thus, line 18 – 24
take O(3k−1 n) time. By caching values of L, we can achieve that we query L at most
once for each label, resulting in an additional run time of O(2k nfL ). The run time of
the backtracking clearly is dominated by the previous tasks, since backtrack is called at
most O(kn) times and requires effort linear in the size of its output. We get a total run
time of
O(2k n(log n + k) + 2k m + 3k n + 2k nfL ) = O(3k n + 2k (n log n + m) + 2k nfL ),
since 2k k = O(3k ).

t
u

9

In Section 3, we will see that there are non-trivial valid lower bounds L which can be used
in the algorithm while still achieving a worst-case run time of O(3k n + 2k (n log n + m)),
matching the bound of [11].

3

Lower Bounds

Roughly speaking, the larger the valid lower bound L is, the faster our algorithm will be.
Before we describe examples of valid lower bounds, we note:
Proposition 4. Let L and L0 be valid lower bounds. Then, max(L, L0 ) also is a valid
lower bound.
Proof. Let v, w ∈ V (G) and I 0 ⊆ I ⊆ R. Then
L(v, I) ≤ L(w, I 0 ) + smt((I \ I 0 ) ∪ {v, w})
≤ max(L(w, I 0 ), L0 (w, I 0 )) + smt((I \ I 0 ) ∪ {v, w})
and
L0 (v, I) ≤ L0 (w, I 0 ) + smt((I \ I 0 ) ∪ {v, w})
≤ max(L(w, I 0 ), L0 (w, I 0 )) + smt((I \ I 0 ) ∪ {v, w}),
so
max(L(v, I), L0 (v, I)) ≤ max(L(w, I 0 ), L0 (w, I 0 )) + smt((I \ I 0 ) ∪ {v, w}).
t
u
Proposition 4 allows the combination of arbitrary valid lower bounds.
Now, we present three types of valid lower bounds. A simple valid lower bound can
be obtained by considering terminal sets of bounded cardinality:
Definition 5. Let (G, c, R) be an instance of the Steiner tree problem, r0 ∈ R and let
j ≥ 1 be an integer. Then, Lj is defined as
Lj (v, I) =

max

{r0 }⊆J⊆I∪{v},|J|≤j+1

smt(J)

for v ∈ V (G) and {r0 } ⊆ I ⊆ R. For v ∈ V (G) and I ⊆ R with r0 ∈
/ I, set Lj (v, I) = 0.
Lemma 6. Let (G, c, R) be an instance of the Steiner tree problem, r0 ∈ R and let j ≥ 1
be an integer. Then, Lj is a valid lower bound. Furthermore, we can implement Lj such
that after a preprocessing time of O(3k + (2k)j−1 n + k j−1 (n log n + m)), we can evaluate
j−1
Lj (v, I) for every v ∈ V (G) and {r0 } ⊆ I ⊆ R in time O(|I| ), where n = |V (G)|,
m = |E(G)| and k = |R|.
Proof. Let v, w ∈ V (G) and {r0 } ⊆ I 0 ⊆ I ⊆ R. To prove that Lj is a valid lower bound,
we have to show
max

{r0 }⊆J⊆I∪{v}
|J|≤j+1

smt(J) ≤

max

{r0 }⊆J 0 ⊆I 0 ∪{w}
|J 0 |≤j+1

smt(J 0 )

+ smt((I \ I 0 ) ∪ {v, w}).

10

Consider the map f : I ∪{v} → I 0 ∪{w} with f (x) = w for x ∈
/ I 0 and f (x) = x otherwise.
Let J be a set with {r0 } ⊆ J ⊆ I ∪ {v} and |J| ≤ j + 1. Set J 0 = {f (x) : x ∈ J}. Then,
clearly {r0 } ⊆ J 0 ⊆ I 0 ∪ {w} and |J 0 | ≤ |J| ≤ j + 1. Moreover,
smt(J) ≤ smt(J 0 ) + smt((I \ I 0 ) ∪ {v, w}).
To achieve the given run time, we first compute smt({v} ∪ I) for all v ∈ V (G) and I ⊆ R
with |I \ {r0 }| ≤ j − 1 in time O((2k)j−1 n + k j−1 (n log n + m)) using a modified variant
of the Dijkstra-Steiner algorithm. More precisely, we do not use a lower bound, do not
use a root terminal and consider terminal sets of increasing cardinality, very similar to
[11]. There are O(k j−1 ) sets I with I ⊆ R, |I \ {r0 }| ≤ j − 1. Since we consider terminal
sets of increasing cardinality one after another, we always have at most n labels in the
Fibonacci heap. As a set of cardinality j has 2j subsets, there are O((2k)j−1 n) updates
of supersets.
Then, to evaluate Lj (v, I), we exploit
Lj (v, I) =

max

{r0 }⊆J⊆I∪{v},|J|≤j+1


= max

max

J⊆I,|J|≤j−1

smt(J)

smt(J ∪ {v, r0 }),

max

{r0 }⊆J⊆I,|J|≤j+1


smt(J) ,

where the first expression can be computed in O(|I|j−1 ) time using the precomputed
values smt({v, r0 } ∪ J) and the second expression does not depend on v and can be
computed in advance for every I ⊆ R in O(3k ) time.
t
u
Thus, for small j, e.g., j ≤ 3, Lj can be efficiently computed. In experiments without
pruning, this lower bound is useful on low-dimensional instances like planar rectilinear
grid graphs. However, pruning has a much larger impact and eliminates this effect.
We now present a more effective lower bound. We will use the notion of 1-trees, which
have long been studied [19] as a lower bound for the traveling salesman problem. Given
a complete graph H with metric edge costs and a special vertex v ∈ V (H), a 1-tree for v
and H is a spanning tree on H − v together with two additional edges connecting v with
the tree. A tour in H is a connected 2-regular subgraph of H. Since every tour consists
of a path, which is a spanning tree, and a vertex connected to the endpoints of the path,
every tour is a 1-tree. Thus, a 1-tree of minimum cost is a lower bound on the cost of a
tour of minimum cost. Since such a tour of minimum cost is at most twice as expensive
as a minimum Steiner tree, we can use 1-trees to get a lower bound for the Steiner tree
problem.
For v, w ∈ V (G), we denote by d(v, w) the cost of a shortest path connecting v and
w in G. Furthermore, for a set of vertices X ⊆ V , we denote by GX the distance graph
of X, which is the subgraph of the metric closure of G induced by X. Note that since
the edge costs in GX are the costs of shortest paths with respect to positive edge costs
in G, the edge costs in GX are always metric. Moreover, for X ⊆ V (G), we denote by
mst(X) the cost of a minimum spanning tree in GX .
Definition 7. Let (G, c, R) be an instance of the Steiner tree problem and r0 ∈ R. Then,
the 1-tree bound L1-tree is defined as
L1-tree (v, I) =

min
i,j∈I:i6=j∨|I|=1

d(v, i) + d(v, j) mst(I)
+
2
2

for v ∈ V (G) and {r0 } ⊆ I ⊆ R. For v ∈ V (G) and I ⊆ R \ {r0 }, we set L1-tree (v, I) = 0.

11

Lemma 8. Let (G, c, R) be an instance of the Steiner tree problem and r0 ∈ R. Then,
L1-tree is a valid lower bound.
Proof. Let v, w ∈ V (G) and {r0 } ⊆ I 0 ⊆ I ⊆ R. We will show
2L1-tree (v, I) ≤ 2L1-tree (w, I 0 ) + 2 smt((I \ I 0 ) ∪ {v, w}),
which translates to
min

(d(v, i) + d(v, j)) + mst(I)

i,j∈I:i6=j∨|I|=1

≤

min

(d(w, i) + d(w, j)) + mst(I 0 ) + 2 smt((I \ I 0 ) ∪ {v, w}).

i,j∈I 0 :i6=j∨|I 0 |=1

Consider a minimum spanning tree T1 in GI 0 and a Steiner tree T2 for (I \I 0 )∪{v, w}.
Furthermore, let j1 , j2 ∈ I 0 with j1 6= j2 ∨ |I 0 | = 1. This setting is illustrated in Figure 3.
First, we construct a tour C in G(I\I 0 )∪{v,w} of cost at most 2c(T2 ) using the standard
double tree argument: If we double each edge in T2 , the graph gets Eulerian and we can
find a Eulerian cycle. If we visit the vertices in the order the Eulerian cycle visits them
and skip already visited vertices, we obtain a tour of at most the same cost exploiting
that the edge costs in the distance graph are metric.
We can decompose the tour into two paths P1 and P2 in GI∪{v,w} with endpoints v
and w such that (I \ I 0 ) ∪ {v, w} = V (P1 ) ∪ V (P2 ) and c(P1 ) + c(P2 ) = c(C). Now, for
i ∈ {1, 2}, we define Pi0 = (V (Pi ) ∪ {ji }, E(Pi ) ∪ {{w, ji }}), which is the path obtained
by appending the edge {w, ji } to Pi .
If I1 := (I \ I 0 ) ∩ V (P1 ) is empty, let j10 be j1 , else, let j10 be the first terminal in I1 when
traversing P1 from v to w.
Similarly, if I2 := (I \ I 0 ) \ V (P1 ) ⊆ V (P2 ) is empty, set j20 = j2 , else let j20 be the first
terminal in I2 when traversing P2 from v to w.
Since I1 and I2 are disjoint and do not contain j1 , j2 ∈ I 0 , we have
j10 = j20 =⇒ (j1 = j10 = j20 = j2 ∧ I \ I 0 = ∅),
which together with
j1 = j2 =⇒ |I 0 | = 1
implies that
j10 = j20 =⇒ |I| = 1.
Then, let Qi be the path in GI obtained from the subpath of Pi0 from ji0 to ji by
skipping w. This is illustrated in Figure 4. We have
d(v, j10 ) + d(v, j20 ) + d(Q1 ) + d(Q2 ) ≤ d(w, j1 ) + d(w, j2 ) + 2c(T2 ).
Also, we have (I \ I 0 ) ∪ {j1 , j2 } ⊆ V (Q1 ) ∪ V (Q2 ) and clearly, we can find a spanning
tree in GI with cost at most d(Q1 ) + d(Q2 ) + d(T1 ) by attaching Q1 and Q2 to T1 .
Therefore,
min

(d(v, i) + d(v, j)) + mst(I)

i,j∈I:i6=j∨|I|=1

≤ d(v, j10 ) + d(v, j20 ) + d(Q1 ) + d(Q2 ) + d(T1 )
≤ d(w, j1 ) + d(w, j2 ) + d(T1 ) + 2c(T2 ).
t
u

12

j1
w
v

j2
2T2

T1

Fig. 3. The minimum spanning tree T1 , the double Steiner tree 2T2 and the edges {w, j1 } and
{w, j2 }. Edges in 2T2 contributing to P1 are colored red and edges contributing to P2 are colored
blue. Vertices in I are drawn as squares.

j10

Q1
j1

v

j20

j2
Q2

Fig. 4. j10 , j20 , Q1 and Q2 in the same setting as in Figure 3.

Note that we could also use half the cost of a minimum spanning tree for I ∪ {v} to
obtain a valid lower bound. However, the 1-tree lower bound is always larger and hence
leads to better run times.
Lemma 9. Let (G, c, R) be an instance of the Steiner tree problem and r0 ∈ R. Then, we
can implement L1-tree such that after a preprocessing time of O(k(n log n + m) + 2k k 2 ),
we can evaluate L1-tree for every v ∈ V (G) and {r0 } ⊆ I ⊆ R in time O(|I|), where
n = |V (G)|, m = |E(G)| and k = |R|.
Proof. First, for every terminal s ∈ R, we compute d(v, s) for all v ∈ V (G) in O(n log n +
m) time using Dijkstra’s algorithm implemented with a Fibonacci heap [14]. For every
I ⊆ R, we compute mst(I) in O(|I|2 ) time using Prim’s algorithm [28]. This results in a

13

total preprocessing time of O(k(n log n + m) + 2k k 2 ). Clearly,
min

(d(v, i) + d(v, j))

i,j∈I:i6=j∨|I|=1

can be evaluated in O(|I|) time if d(v, i) is known for all v ∈ V (G) and i ∈ I.

t
u

Of course, in practice we do not compute minimum spanning trees for all sets of
terminals in advance, but compute them dynamically when needed.
Theorem 10. Let j ∈ N be a constant. Let (G, c, R) be an instance of the Steiner tree
problem and r0 ∈ R. Then, we can compute smt(R) in time O(3k n + 2k (n log n + m))
using the Dijkstra-Steiner algorithm with L = max(Lj , L1-tree ).
t
u
The 1-tree lower bound exploits the fact that 1-trees can be used to compute lower
bounds on the minimum cost of a tour, which in turn is at most twice as expensive
as a minimum cost Steiner tree. Using more preprocessing and evaluation time, we can
eliminate the loss of approximating tours by 1-trees by using optimum tours to get lower
bounds. While it may sound unreasonable to use optimum solutions for an NP-hard
problem to speed up another algorithm, it turns out we can compute optimum tours
for the union of sets of terminals and at most one vertex quite fast if there are only
few terminals. This is due to the fact that the cost of an optimum tour in GI∪{v} only
depends on the distances from terminals to v and shortest Hamiltonian paths with given
endpoints in GI , which can be computed in advance. For a set of vertices X ⊆ V (G), we
denote by tsp(X) the minimum cost of a Hamiltonian circuit in GX .
Definition 11. Let (G, c, R) be an instance of the Steiner tree problem and r0 ∈ R.
Then, the TSP bound LT SP is defined as
LT SP (v, I) =

tsp(I ∪ {v})
2

for v ∈ V (G) and I ⊆ R.
Lemma 12. Let (G, c, R) be an instance of the Steiner tree problem and r0 ∈ R. Then,
LT SP is a valid lower bound. Moreover, after a preprocessing time of O(k(n log n + m) +
2k k 3 ), we can evaluate LT SP (v, I) in time O(|I|2 ) for all v ∈ V (G) and I ⊆ R.
Proof. Let v, w ∈ V (G) and {r0 } ⊆ I 0 ⊆ I ⊆ R. We will show
2LT SP (v, I) ≤ 2LT SP (w, I 0 ) + 2 smt((I \ I 0 ) ∪ {v, w}),
which is equivalent to
tsp(I ∪ {v}) ≤ tsp(I 0 ∪ {w}) + 2 smt((I \ I 0 ) ∪ {v, w}).
First, we choose an optimal tour C1 in GI 0 ∪{w} . Then, we construct a tour C2 in
G(I\I 0 )∪{v,w} of cost at most 2 smt((I \ I 0 ) ∪ {v, w}) by doubling the edges of an optimum Steiner tree, finding a Eulerian walk and taking shortcuts. We have I ∪ {v} =
V (C1 )∪V (C2 ) and w ∈ V (C1 )∩V (C2 ), so we can construct a tour in GI∪{v} by inserting
C2 into C1 after w and taking shortcuts, which results in a tour of cost of at most
tsp(I 0 ∪ {w}) + 2 smt((I \ I 0 ) ∪ {v, w}).

14

We achieve the given run time using a dynamic programming approach very similar to
the TSP algorithm by Held and Karp [18]. The idea is to compute shortest Hamiltonian
paths in the distance graph of the terminals for all possible pairs of endpoints. Then, one
can evaluate LT SP (v, I) in O(|I|2 ) time by enumerating all possible pairs of neighbors
of v in the tour.
t
u

4

Pruning

In this section, we present techniques to speed up the algorithm further by discarding
labels (v, I) for which we can prove that they cannot contribute to an optimum solution.
This affects the number of iterations, since these labels then are not chosen in line 8 of
the algorithm. Also, it speeds up the execution of line 18, since we only have to consider
existing labels in the merge step. First, we show how to identify labels that cannot
contribute to an optimum solution. Then we show that we can indeed safely discard
them in our algorithm.
Definition 13. Let (G, c, R) be an instance of the Steiner tree problem, (v, I) ∈ V (G) ×
2R and T be a Steiner tree for R. A tree T1 is said to be a (v, I)-subtree of T if there
exists a tree T2 such that
(i)
(ii)
(iii)
(iv)

V (T1 ) ∪ V (T2 ) = V (T ),
V (T1 ) ∩ V (T2 ) = {v},
T1 is a subtree of T containing {v} ∪ I and
T2 is a subtree of T containing {v} ∪ (R \ I).

For a tree T and a (v, I)-subtree T1 of T , we will also refer to the corresponding subtree
T2 by T − T1 .
Lemma 14. Let (G, c, R) be an instance of the Steiner tree problem and r0 ∈ R. Let L
be a valid lower bound and U ≥ smt(R). Furthermore, let v ∈ V (G), I ⊆ R \ {r0 } and
T1 be a tree in G containing {v} ∪ I with
c(T1 ) + L(v, R \ I) > U.
Then, there is no optimum Steiner tree for R containing T1 as a (v, I)-subtree.
Proof. Let T be a Steiner tree for R such that T1 is a (v, I)-subtree of T . Then,
c(T ) = c(T1 ) + c(T − T1 )
≥ c(T1 ) + smt({v} ∪ (R \ I))
= c(T1 ) + smt({v, r0 } ∪ ((R \ I) \ {r0 })) + L(r0 , {r0 })
≥ c(T1 ) + L(v, R \ I)
>U
≥ smt(R).
t
u
Lemma 14 is a trivial exploitation of the lower bound L. Its effect on the run time of
the algorithm is rather limited, since we only discard labels that would never have been
labeled permanently anyway. In contrast, the following lemma allows significant run time
improvements of our algorithm, in particular on geometric instances. An application is
illustrated in Figure 5.

15

Lemma 15. Let (G, c, R) be an instance of the Steiner tree problem, v ∈ V (G), I ⊂ R
and ∅ =
6 S ⊆ R \ I. Furthermore, let T1 be a Steiner tree for {v} ∪ I and H be a subgraph
of G with
(i) (I ∪ S) ⊆ V (H),
(ii) each connected component of H contains a terminal in S and
(iii) c(H) < c(T1 ).
Then, there is no optimum Steiner tree for R in G containing T1 as a (v, I)-subtree.
Proof. Let T be a Steiner tree for R in G containing T1 as a (v, I)-subtree. Then, there
exists a tree T2 containing {v} ∪ (R \ I) with c(T ) = c(T1 ) + c(T2 ). We construct a
subgraph T 0 of G containing R by T 0 = T2 + H. As H contains a path from every vertex
in H to some vertex in S, T2 is connected and S ⊆ R \ I ⊆ V (T2 ), T 0 is connected. Thus,
smt(R) ≤ c(T 0 )
≤ c(T2 ) + c(H)
= c(T ) − c(T1 ) + c(H)
< c(T ).
t
u

S
S
I

I

I
H

I
I

Fig. 5. By Lemma 15, no label for the set I with cost strictly larger than c(H) can be part of
an optimum solution. Terminals are drawn as squares, elements of I and S are labeled with the
respective set.

In Section 5, we will explain how suitable graphs H can be found. Lemmata 14 and 15
allow us to identify labels that cannot contribute to an optimum solution. Theorem 17
shows that we can discard these labels without affecting the correctness of the algorithm.
First, we prove an auxiliary lemma used in the proof of Theorem 17:
Lemma 16. Let (G, c, R) be an instance of the Steiner tree problem and r0 ∈ R. Let
O ⊆ V (G) × 2R\{r0 } be the set of pairs (v, I) with the property that there is an optimum
Steiner tree for R containing a (v, I)-subtree. Furthermore, let (v, I) ∈ O and T1 be a
tree containing {v} ∪ I with c(T1 ) = smt({v} ∪ I). Then, there is an optimum Steiner
tree T for R containing T1 as a (v, I)-subtree.

16

Proof. Since (v, I) ∈ O, there is an optimum Steiner tree T 0 for R and a tree T10 which
is a (v, I)-subtree of T . Set T = (T 0 − T10 ) + T1 . Then, since T 0 − T10 is a tree containing
{v}∪(R\I) and T1 is a tree containing {v}∪I, T is a connected subgraph of G containing
{v} ∪ R. Furthermore, we have
smt(R) ≤ c(T ) ≤ c(T 0 − T10 ) + c(T1 )
= c(T 0 − T10 ) + smt({v} ∪ I)
= c(T 0 ) − c(T10 ) + smt({v} ∪ I)
≤ c(T 0 )
= smt(R).
Since we do not have edges of zero cost, this shows T is an optimum Steiner tree and T1
is a (v, I)-subtree of T .
t
u
We now formalize a general method of pruning:
Procedure prune(v, I)
1

2
3

if we can prove that there is no optimum Steiner tree T for R such that
backtrack(v, I) is the edge set of a (v, I)-subtree of T then
N := N \ {(v, I)};
end

Note that when considering a not permanently labeled element (v, I) ∈ N , we cannot
guarantee that backtrack(v, I) is the edge set of a tree, since it may contain cycles.
However, if it is not a tree, we can prune (v, I) obviously.
Theorem 17. The Dijkstra-Steiner algorithm still works correctly if we modify it to
execute prune(w, I) after line 15 and prune(v, I ∪ J) after line 22.
Proof. Let O ⊆ V (G) × 2R\{r0 } be the set of pairs (v, I) with the property that there is
an optimum Steiner tree for R containing a (v, I)-subtree. It suffices that the modified
algorithm is correct on O, which we will now prove.
To this end, we modify invariants (a) – (d) as defined in the proof of Theorem 2 by
restricting (a) – (c) to labels (v, I) ∈ O and not changing (d). We call these new invariants
(a’) – (d’).
Since (r0 , R \ {r0 }) ∈ O, the algorithm is correct assuming that these invariants hold.
They clearly hold after the initialization.
Moreover, (a’), (c1’) and (c2’) are clearly preserved. To see that (c3’) is preserved, recall
that prune only removes labels (v, I) from N if there is no optimum Steiner tree T for R
such that backtrack(v, I) is the edge set of a (v, I)-subtree of T . However, if (v, I) ∈ O
and l(v, I) = smt({v} ∪ I), by (a3’) and Lemma 16 the label (v, I) cannot be pruned, so
(c3’) is preserved as well.
The argument showing that (b) is preserved remains unchanged: (c’) can be applied to
(w, I 0 ), because if (v, I) ∈ O, then (w, I 0 ) is in O as well. This directly implies that the
same argument as in the proof of Theorem 2 can be used to prove that (d’) is preserved,
since (r0 , R \ {r0 }) ∈ O.
t
u
Of course, in practice we just avoid the creation of such labels instead of removing
them immediately after creation. Moreover, whenever a label (v, I) is selected in line 8,

17

we also try to prune it. This is not redundant, since after l(v, I) was updated the last
time, bounds used to prune may have improved. Moreover, we could have pruned (v, I)
immediately after the last update of l(v, I) with an equivalent impact on the execution
of the algorithm, so the algorithm still works correctly.

5

Implementation and Results

We implemented the algorithm using the C++ programming language. In our implementation, we use a binary heap instead of a Fibonacci heap. We represent terminal sets by
bitsets using the canonical bijection 2R → {0, . . . , 2|R| −1}. For each vertex v ∈ V (G), we
maintain an array containing the labels (v, I) with l(v, I) < ∞ and a hash table storing
for each label its index in the array, if it exists. This enables us to access labels very
quickly and traverse over the existing labels in linear time, which is important for an
efficient implementation of the merge step:
To implement line 18, we have two options. Either we explicitly enumerate all sets
J ⊆ (R \ {r0 }) \ I and check whether the label (v, J) exists, or we traverse over all
existing labels at v and omit the labels (v, J) with J ∩ I 6= ∅. We always choose the
option resulting in fewer sets to be considered.
We implement the pruning rule of Lemma 14 using a shortest-paths Steiner tree
heuristic similar to Prim’s algorithm [28], maintaining and extending one component at
a time. This takes O(k(n log n + m)) time. Then, we use the cost of that Steiner tree as
an upper bound and apply Lemma 14 each time we create a new label.
To implement Lemma 15, we maintain an upper bound U (I) on the cost of labels for
each set I ⊆ R \ {r0 } of terminals, which is initially set to infinity. For each occurring
set I ⊆ R \ {r0 }, we compute the distance d(I, R \ I) = minx∈I,y∈R\I d(x, y). Then, each
time we extract a label (v, I) from the heap, we update U (I) by
U (I) := min (U (I), l(v, I) + min(d(I, R \ I), d(v, R \ I))) .
Also, we keep track of the set S(I) that was used to generate the currently best upper
bound for the set I. In the routine described above, we always have |S| = 1. However,
when merging two sets I1 and I2 , we can use the sum of their upper bounds as an upper
bound for the set I1 ∪ I2 if S(I1 ) ∩ I2 = ∅ or S(I2 ) ∩ I1 = ∅, resulting in S(I1 ∪ I2 ) =
(S(I1 ) ∪ S(I2 )) \ (I1 ∪ I2 ).
Furthermore, we use the 1-tree bound as a lower bound. Of course, we do not compute
minimum spanning trees for all subsets of terminals in advance. Instead, each time we
consider a set I for the first time, we compute mst(R \ I).
Lacking a good selection strategy for general instances, we always choose the last
terminal of the instance w.r.t. the order in the instance file as root terminal. Note that
our implementation is limited to instances with less than 64 terminals.
We now present computational results of our algorithm on instances of the 11th
DIMACS implementation challenge [1].
Our results were achieved single-threaded on a computer with 3.33 GHz Intel Xeon
W5590 CPUs, which produced a score of 391 for the DIMACS benchmark. We compare
our results with those obtained by the state-of-the-art algorithm by Polzin and Vahdati
Daneshmand [27], which were obtained using one thread on a computer with a 2.66 GHz
Intel i7 920 CPU. This computer produced a score of 307 in the DIMACS benchmark. The

18

|R|

Opt

Time [s]

Time PV [s]

(a) VLSI-derived grid graphs with holes
diw0779
11821
22516
50
diw0819
10553
20066
32
diw0820
11749
22384
37
lin23
3716
6750
52
lin24
7998
14734
16
lin30
19091
35644
31
lin32
19112
35665
53
lin34
38282
71521
34
lin35
38294
71533
45
lin36
38307
71546
58

4440
3399
4167
17560
15076
27684
39832
45018
50559
55608

1.60
0.29
1.50
11.08
0.10
0.68
150.20
12.93
26.90
47.59

1.26
0.52
1.06
0.54
1.73
14.74
816.51
1848.24
1911.09
39931.77

obstacle-avoiding instances preprocessed by ObSteiner
114
228
33
1341
0.02
109
202
50
54160
0.15
788
1938
50
45852
0.70

0.01
0.00
1.99

Instance

(b) Rectilinear
ind5
rc03
rt02

|V |

|E|

(c) Group Steiner tree instances
wrp3-14
128
247
wrp3-15
138
257
wrp3-16
204
374
wrp3-17
177
354
wrp3-19
189
353

14
15
16
17
19

1400250
1500422
1600208
1700442
1900439

3.78
51.16
11.62
422.08
1765.72

0.01
0.01
0.03
0.02
0.03

(d) Random graphs with so-called incidence costs
i160-141
160
2544
12
2549
i320-111
320
1845
17
4273
i640-022
640
204480
9
1756
i640-031
640
1280
9
3278
i640-043
640
40896
9
1931

3.40
1706.67
4.03
0.07
0.89

0.01
0.03
0.52
0.00
0.13

(e) Artificial instances from the hard PUC testset
cc3-4p
64
288
8
2338
0.01
cc3-4u
64
288
8
23
0.01
cc3-5p
125
750
13
3661
3.45
cc3-5u
125
750
13
36
4.64
cc6-2p
64
192
12
3271
0.17
cc6-2u
64
192
12
32
0.28
Table 1. Results on various instance types.

1.99
1.37
87.98
115.83
0.40
0.90

19

algorithm by Polzin and Vahdati Daneshmand successively performs various optimalitypreserving reductions combined with a branch and bound approach.
In Table 1, we show results on multiple instance classes (a) – (e). For each instance, we
give its name, the number of vertices, edges and terminals. Then, we state the cost of an
optimum solution as reported by our algorithm and the run time in seconds. Moreover,
for each instance, we give the run time reported by Polzin and Vahdati Daneshmand.
For the lin testset, Polzin and Vahdati Daneshmand improved run times by modifying
their algorithm to use stronger reductions. With default settings, their algorithm did not
solve lin36 within a time limit of 24 hours.
On instances (a) and (b), both arising from rectilinear VLSI problems, our algorithm
is much faster than the worst-case bound tells. This is primarily caused by the high
impact of our pruning method. In particular, on instances with large underlying graphs,
our algorithm performs very well, beating the reduction-based solver.
In contrast, on group Steiner tree instances (c), our pruning implementation has no
effect. Although these instances are based on VLSI-derived grid graphs with holes as well,
they have been modified to model the groups as terminals: For each group of the group
Steiner tree instance, a new terminal is added to the graph and connected to the elements
of the group by edges of very high cost. By choosing the cost of these new edges sufficiently
large, one can guarantee that an optimum Steiner tree in the new instance corresponds
to an optimum group Steiner tree in the original instance and vice versa, since each
terminal will be a leaf of the Steiner tree. To prune a label (v, I) ∈ V (G) × 2R\{r0 } , our
implementation needs to connect the terminal set I to at least one additional terminal
s ∈ R \ I with cost strictly less than the cost of the label (v, I). However, on these
instances, connecting to an additional terminal is always much more expensive than any
path in the original graph.
On incidence cost instances (d), where edges incident to terminals are assigned larger
costs, a similar effect can be observed. On other random graph instances, the 1-tree lower
bound is very effective.
Although neither pruning nor future cost estimates do have a noticeable effect on
instances from the hard PUC testset (e), our algorithm performs very well on instances
with few terminals. This is caused by the strong worst-case run time guarantee, which,
albeit exponential in the number of terminals, is quasilinear in the size of the graph.
Detailed further computational results can be found in Appendix A.
We also applied our algorithm to the d-dimensional rectilinear Steiner tree problem
for d ∈ {3, 4, 5}. For d = 2, instances with thousands of terminals can be solved by the
GeoSteiner algorithm [34], which works by generating a candidate set of full Steiner trees
for subsets of terminals and then concatenating a subset of these candidates to form an
optimum Steiner tree. A full Steiner tree is a Steiner tree where each terminal has degree
1. The concatenation phase works by either solving a Steiner tree problem in graphs or a
minimum spanning tree problem in hypergraphs. Exploiting a result by Hwang [21], the
GeoSteiner algorithm only has to consider full Steiner trees following a special structure,
which allows a significant reduction of the number of generated candidates. In contrast,
for higher dimensions, eliminating possible full Steiner trees is much harder, as Hwang’s
result does not apply and complicated full Steiner trees have to be considered [36]. An
implementation of the GeoSteiner algorithm for higher dimension is only able to solve
instances with up to around 15 terminals in dimension 3 and up to around 10 terminals
in dimensions 4, 5 and 6 [36]. The situation is similar in the Euclidean case, where huge

20

instances can be solved for d = 2 using the GeoSteiner algorithm, but only instances
with up to around 17 terminals for d ≥ 3, using very different algorithms [13].
It is well-known that to compute an optimum rectilinear Steiner tree in dimension
2, it suffices to compute an optimum Steiner tree in the so-called Hanan grid [16]. The
Hanan grid is the graph obtained by drawing axis-parallel lines through each terminal,
taking intersections of these lines as vertex set and segments between intersections as
edges. This result was later generalized to arbitrary dimension by Snyder [30], leading to
a grid graph with O(k d ) vertices and O(dk d ) edges for a d-dimensional instance with k
terminals.
Using this reduction, we ran our algorithm on instances from the CARIOCA [1] testset, which contains randomly generated instances for d ∈ {3, 4, 5} with between 11 and
20 terminals. To test our algorithm on larger instances, we generated new random instances (using the prefix “bonn”), as other available testsets do not contain sufficiently
many instances which are neither too small nor too large. For these new instances, coordinates were chosen uniformly at random from {0, 1, . . . , 999}. In particular for the larger
instances, coordinates may appear multiple times, leading to grid graphs with slightly
less than k d vertices. Coordinates of instances from the CARIOCA testset were scaled
by 108 to obtain integral coordinates. For these instances, we chose a terminal as close
as possible to the center of gravity of all terminals as root terminal, improving results
compared to a random choice.
Instance

d

|V |

|E|

|R|

Opt

Time [s]

carioca
carioca
carioca
carioca
bonn 3
bonn 3
bonn 3

3 11
3 11
3 20
3 20
40 1
40 2
55 3

01
02
01
02

3
3
3
3
3
3
3

1331
1331
8000
8000
64000
57798
154548

3630
3630
22800
22800
187200
168909
455004

11
11
20
20
40
40
55

311221222
466149453
638376617
477950448
9024
9633
12138

0.02
0.02
1.61
0.15
25.44
710.09
6201.10

carioca
carioca
carioca
carioca

4
4
4
4

11
11
20
20

01
02
01
02

4
4
4
4

14641
14641
160000
160000

53240
53240
608000
608000

11
11
20
20

627022001
636772154
889180827
822698792

0.43
0.22
82.72
101.11

carioca
carioca
carioca
carioca
carioca

5
5
5
5
5

11
11
15
15
18

01
02
01
02
03

5
161051
732050
11
925163690
5
161051
732050
11
844673618
5
759375
3543750
15
1011895745
5
759375
3543750
15
1067623193
5
1889568
8922960
18
1177091608
Table 2. Results on d-dimensional rectilinear instances.

34.55
13.02
1046.36
888.81
1081.01

Excerpts of experimental results are given in Table 2, the full results can be found in
Appendix B.
In dimension 3, we are able to solve all tested instances with up to 34 terminals.
Many of the larger instances with up to 40 terminals are solved as well, and additionally
one instance with 55 terminals. In dimension 4, we solve all instances of the CARIOCA
testset as well. Experiments with larger instances are not reported here, since we were

21

only able to solve instances with up to 22 terminals. In dimension 5, all instances with up
to 15 terminals are solved. The largest solved instance carioca 5 18 03 has 18 terminals
and nearly 9 million edges. Solving it required approximately 20 GB of memory.

6

Discussion

Note that due to the dynamic programming nature of our algorithm, it can also be used
to compute all optimum Steiner trees or even all Steiner trees up to a given cost. If
we enumerate all Steiner trees up to a cost of Opt + ∆, we have to relax the pruning
implementations by ∆ and continue labeling until all labels (v, I) with l(v, I) ≤ Opt + ∆
are permanent. Also, we have to save all predecessors instead of only one optimum
predecessor. Then, we can recursively combine Steiner trees for subsets of terminals. In
practice, the additional effort is linear in the size of the output, allowing the enumeration
of millions of near-optimum Steiner trees in seconds. See [29] for details.
The dynamic programming idea by Dreyfus and Wagner has been used extensively to
obtain Steiner tree algorithms with fast theoretical worst-case behavior. However, in the
field of practical solving, it has rather been disregarded prior to this work. Compared to
other exact algorithms, our algorithm depends much less on effective preprocessing and
performs well on large graphs. Our approach is very general and not limited to the lower
bounds and pruning strategies proposed in this paper.

Bibliography

[1] 11th DIMACS implementation challenge (2014). URL http://dimacs11.cs.
princeton.edu/downloads.html
[2] de Aragão, M., Uchoa, E., Werneck, R.: Dual heuristics on the exact solution of
large Steiner problems. In: Proceedings of the Brazilian Symposium on Graphs,
Algorithms and Combinatorics GRACO’01. Fortaleza (2001)
[3] Beasley, J.: An algorithm for the Steiner problem in graphs. Networks 14, 147–159
(1984)
[4] Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In: F.V.
Fomin, R. Freivalds, M. Kwiatkowska, D. Peleg (eds.) Automata, Languages, and
Programming, Lecture Notes in Computer Science, vol. 7965, pp. 196–207. Springer
Berlin Heidelberg (2013)
[5] Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: Steiner tree approximation via
iterative randomized rounding. J. ACM 60(1), 6:1–6:33 (2013)
[6] Chlebı́k, M., Chlebı́ková, J.: The Steiner tree problem on graphs: Inapproximability
results. Theoretical Computer Science 406(3), 207–214 (2008)
[7] Chopra, S., Gorres, E., Rao, M.: Solving the Steiner tree problem on a graph using
branch and cut. ORSA Journal on Computing 4, 320–335 (1992)
[8] Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische
Mathematik 1, 269–271 (1959)
[9] Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1(3), 195–207
(1971)
[10] Duin, C., Volgenant, A.: An edge elimination test for the Steiner problem in graphs.
Operations Research Letters 8, 79–83 (1989)
[11] Erickson, R.E., Monma, C.L., Veinott Jr., A.F.: Send-and-split method for
minimum-concave-cost network flows. Math. Oper. Res. 12(4), 634–664 (1987)
[12] Fafianie, S., Bodlaender, H., Nederlof, J.: Speeding up dynamic programming with
representative sets. In: G. Gutin, S. Szeider (eds.) Parameterized and Exact Computation, Lecture Notes in Computer Science, vol. 8246, pp. 321–334. Springer International Publishing (2013)
[13] Fonseca, R., Brazil, M., Winter, P., Zachariasen, M.: Faster exact algorithms for
computing Steiner trees in higher dimensional euclidean spaces. 11th DIMACS
Implementation Challenge on Steiner Tree Problems (2014)
[14] Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network
optimization algorithms. J. ACM 34(3), 596–615 (1987)
[15] Fuchs, B., Kern, W., Mölle, D., Richter, S., Rossmanith, P., Wang, X.: Dynamic
programming for minimum Steiner trees. Theory of Computing Systems 41(3),
493–500 (2007)
[16] Hanan, M.: On Steiner’s problem with rectilinear distance. SIAM Journal on Applied
Mathematics 14(2), 255–265 (1966)
[17] Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination
of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics
SSC-4(2), 100–107 (1968)

23

[18] Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems.
Journal of the Society for Industrial and Applied Mathematics 10(1), 196–210
(1962). DOI 10.2307/2098806
[19] Held, M., Karp, R.M.: The traveling salesman problem and minimum spanning trees.
Operations Research 18, 1138–1162 (1970)
[20] Held, S., Korte, B., Rautenbach, D., Vygen, J.: Combinatorial optimization in VLSI
design. In: Combinatorial Optimization - Methods and Applications, pp. 33–96. IOS
Press (2011)
[21] Hwang, F.K.: On Steiner minimal trees with rectilinear distance. SIAM journal on
Applied Mathematics 30(1), 104–114 (1976)
[22] Karp, R.M.: Reducibility among combinatorial problems. In: R. Miller, J. Thatcher
(eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press (1972)
[23] Koch, T., Martin, A.: Solving Steiner tree problems in graphs to optimality. Networks 32, 207–232 (1998)
[24] Polzin, T.: Algorithms for the Steiner problem in networks. Ph.D. thesis (2004)
[25] Polzin, T., Vahdati, S.: Extending reduction techniques for the Steiner tree problem:
A combination of alternative- and bound-based approaches. Tech. Rep. MPI-I-20011-007, Max-Planck-Institut für Informatik (2001)
[26] Polzin, T., Vahdati Daneshmand, S.: Practical partitioning-based methods for the
Steiner problem. In: C. Àlvarez, M. Serna (eds.) Experimental Algorithms, Lecture Notes in Computer Science, vol. 4007, pp. 241–252. Springer Berlin Heidelberg
(2006)
[27] Polzin, T., Vahdati Daneshmand, S.: The Steiner Tree Challenge: An updated Study (2014).
URL http://dimacs11.cs.princeton.edu/papers/
PolzinVahdatiDIMACS.pdf
[28] Prim, R.C.: Shortest connection networks and some generalizations. Bell System
Technology Journal 36, 1389–1401 (1957)
[29] Silvanus, J.: Fast exact Steiner tree generation using dynamic programming. Master’s thesis, Research Institute for Discrete Mathematics, University of Bonn (2013)
[30] Snyder, T.L.: On the exact location of Steiner points in general dimension. SIAM
Journal on Computing 21(1), 163–180 (1992)
[31] Uchoa, E., de Aragão, M., Ribeiro, C.: Preprocessing Steiner problems from VLSI
layout. Tech. Rep. MCC 32/99, Catholic University of Rio de Janeiro, Rio de Janeiro
(1999)
[32] Vahdati Daneshmand, S.: Algorithmic approaches to the Steiner problem in networks. Ph.D. thesis (2004)
[33] Vygen, J.: Faster algorithm for optimum Steiner trees. Inf. Process. Lett. 111(2122), 1075–1079 (2011)
[34] Warme, D.M., Winter, P., Zachariasen, M.: Exact algorithms for plane Steiner tree
problems: A computational study. Springer (2000)
[35] Wong, R.: A dual ascent approach for Steiner tree problems on a directed graph.
Mathematical Programming 28(3), 271–287 (1984)
[36] Wulff-Nilsen, C.: Higher dimensional rectilinear Steiner minimal trees. Master’s
thesis, Department of Computer Science, University of Copenhagen (2006)

24

A

Results on Graphic DIMACS Instances

We present detailed computational results on DIMACS testsets. Our implementation
is limited to instances with less than 64 terminals, so we exclude instances with more
terminals.
The implementation of our algorithm is written in the C++ programming language
and compiled using the GCC 4.8.2 compiler.
The experiments were performed single-threaded on a machine with 3.33 GHz Intel
Xeon W5590 CPUs and 144 GB main memory which produced a score of 391.372724
using the DIMACS benchmark code.
For these experiments, we limited the memory consumption of the algorithm to
100 GB and set the time limit to 7200 s. The reported run times do not include the
time to read the instance file from disk.
Instance

|V |

|E|

|R|

Opt

Time [s]

alue2087
1244
1971
34
1049
1.075
alue2105
1220
1858
34
1032
0.204
alue7066
6405
10454
16
2256
0.068
alue7229
940
1474
34
824
0.036
Table 3: Results on the testset ALUE. Type: VLSI-derived grid
graphs with holes.

Instance

|V |

|E|

|R|

Opt

Time [s]

alut0787
1160
2089
34
982
1.769
alut0805
966
1666
34
958
0.258
alut2764
387
626
34
640
0.042
Table 4: Results on the testset ALUT. Type: VLSI-derived grid
graphs with holes.

Instance

|V |

|E|

|R|

Opt

Time [s]

diw0234
diw0250
diw0260
diw0313
diw0393
diw0445
diw0459
diw0460
diw0473
diw0487
diw0495
diw0513
diw0523
diw0540

5349
353
539
468
212
1804
3636
339
2213
2414
938
918
1080
286

10086
608
985
822
381
3311
6789
579
4135
4386
1655
1684
2015
465

25
11
12
14
11
33
25
13
25
25
10
10
10
10

1996
350
468
397
302
1363
1362
345
1098
1424
616
604
561
374

0.096
0.002
0.003
0.003
0.002
0.061
0.042
0.004
0.065
0.373
0.006
0.006
0.005
0.002

25

Instance

|V |

diw0559
3738
diw0778
7231
diw0779
11821
diw0795
3221
diw0801
3023
diw0819
10553
diw0820
11749
Table 5: Results on the
graphs with holes.

Instance

|V |

|E|

|R|

Opt

Time [s]

7013
18
1570
0.089
13727
24
2173
0.139
22516
50
4440
1.603
5938
10
1550
0.024
5575
10
1587
0.024
20066
32
3399
0.291
22384
37
4167
1.504
testset DIW. Type: VLSI-derived grid

|E|

|R|

Opt

Time [s]

dmxa0296
233
386
12
344
0.002
dmxa0368
2050
3676
18
1017
0.019
dmxa0454
1848
3286
16
914
0.012
dmxa0628
169
280
10
275
0.002
dmxa0734
663
1154
11
506
0.006
dmxa0848
499
861
16
594
0.041
dmxa0903
632
1087
10
580
0.008
dmxa1010
3983
7108
23
1488
0.104
dmxa1109
343
559
17
454
0.007
dmxa1200
770
1383
21
750
0.069
dmxa1304
298
503
10
311
0.002
dmxa1516
720
1269
11
508
0.003
dmxa1721
1005
1731
18
780
0.012
dmxa1801
2333
4137
17
1365
0.049
Table 6: Results on the testset DMXA. Type: VLSI-derived grid
graphs with holes.

Instance

|V |

gap1307
342
gap1413
541
gap1500
220
gap1810
429
gap1904
735
gap2007
2039
gap2119
1724
gap2740
1196
gap2800
386
gap2975
179
gap3036
346
gap3100
921
Table 7: Results on the
graphs with holes.

|E|

|R|

Opt

Time [s]

552
17
549
0.057
906
10
457
0.007
374
17
254
0.003
702
17
482
0.013
1256
21
763
0.042
3548
17
1104
0.051
2975
29
1244
0.460
2084
14
745
0.011
653
12
386
0.003
293
10
245
0.001
583
13
457
0.013
1558
11
640
0.007
testset GAP. Type: VLSI-derived grid

26

Instance

|V |

|E|

|R|

Opt

Time [s]

lin01
53
80
4
503
0.000
lin02
55
82
6
557
0.000
lin03
57
84
8
926
0.001
lin04
157
266
6
1239
0.001
lin05
160
269
9
1703
0.002
lin06
165
274
14
1348
0.004
lin07
307
526
6
1885
0.002
lin08
311
530
10
2248
0.002
lin09
313
532
12
2752
0.004
lin10
321
540
20
4132
0.017
lin11
816
1460
10
4280
0.013
lin12
818
1462
12
5250
0.017
lin13
822
1466
16
4609
0.017
lin14
828
1472
22
5824
0.023
lin15
840
1484
34
7145
0.088
lin16
1981
3633
12
6618
0.032
lin17
1989
3641
20
8405
0.051
lin18
1994
3646
25
9714
0.475
lin19
2010
3662
41
13268
10.966
lin20
3675
6709
11
6673
0.029
lin21
3683
6717
20
9143
0.062
lin22
3692
6726
28
10519
0.129
lin23
3716
6750
52
17560
11.080
lin24
7998
14734
16
15076
0.104
lin25
8007
14743
24
17803
0.291
lin26
8013
14749
30
21757
0.319
lin27
8017
14753
36
20678
1.577
lin29
19083
35636
24
23765
1.746
lin30
19091
35644
31
27684
0.681
lin31
19100
35653
40
31696
34.061
lin32
19112
35665
53
39832
150.201
lin34
38282
71521
34
45018
12.930
lin35
38294
71533
45
50559
26.904
lin36
38307
71546
58
55608
47.590
Table 8: Results on the testset LIN. Type: VLSI-derived grid graphs
with holes.

Instance
msm0580
msm0654
msm0709
msm0920
msm1008
msm1234
msm1477

|V |

|E|

|R|

Opt

Time [s]

338
1290
1442
752
402
933
1199

541
2270
2403
1264
695
1632
2078

11
10
16
26
11
13
31

467
823
884
806
494
550
1068

0.006
0.007
0.010
0.041
0.008
0.007
0.259

27

Instance

|V |

|E|

|R|

Opt

Time [s]

msm1707
278
478
11
564
0.001
msm1844
90
135
10
188
0.001
msm1931
875
1522
10
604
0.003
msm2000
898
1562
10
594
0.004
msm2152
2132
3702
37
1590
0.269
msm2326
418
723
14
399
0.003
msm2492
4045
7094
12
1459
0.035
msm2525
3031
5239
12
1290
0.016
msm2601
2961
5100
16
1440
0.042
msm2705
1359
2458
13
714
0.017
msm2802
1709
2963
18
926
0.028
msm3277
1704
2991
12
869
0.021
msm3676
957
1554
10
607
0.006
msm3727
4640
8255
21
1376
0.079
msm3829
4221
7255
12
1571
0.042
msm4038
237
390
11
353
0.003
msm4114
402
690
16
393
0.004
msm4190
391
666
16
381
0.005
msm4224
191
302
11
311
0.002
msm4312
5181
8893
10
2016
0.042
msm4414
317
476
11
408
0.003
msm4515
777
1358
13
630
0.013
Table 9: Results on the testset MSM. Type: VLSI-derived grid
graphs with holes.

Instance

|V |

taq0023
572
taq0365
4186
taq0431
1128
taq0631
609
taq0739
837
taq0741
712
taq0751
1051
taq0891
331
taq0910
310
taq0920
122
taq0978
777
Table 10: Results on the
graphs with holes.

|E|

|R|

Opt

Time [s]

963
11
621
0.007
7074
22
1914
0.079
1905
13
897
0.017
932
10
581
0.008
1438
16
848
0.019
1217
16
847
0.024
1791
16
939
0.032
560
10
319
0.003
514
17
370
0.010
194
17
210
0.003
1239
10
566
0.005
testset TAQ. Type: VLSI-derived grid

28

Instance

|V |

1r111
1250
1r112
1250
1r113
1250
1r121
1250
1r122
1250
1r123
1250
1r131
1250
1r132
1250
1r133
1250
1r211
1250
1r212
1250
1r213
1250
1r221
1250
1r222
1250
1r223
1250
1r231
1250
1r232
1250
1r233
1250
1r311
1250
1r312
1250
1r313
1250
1r321
1250
1r322
1250
1r323
1250
1r331
1250
1r332
1250
1r333
1250
Table 11: Results on

Instance
2r111
2r112
2r113
2r121
2r122
2r123
2r131
2r132
2r133
2r211
2r212
2r213
2r221
2r222
2r223

|E|
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
4704
the testset

|R|

Opt

6
28000
6
28000
6
26000
6
36000
6
45000
6
40000
6
43000
6
37000
6
36000
31
77000
30
81000
29
70000
31
79000
31
68000
31
77000
30
80000
29
86000
31
71000
56
–
60
113000
58
106000
59
–
60
113000
60
–
58
103000
58
109000
58
113000
1R. Type: 2D grid

Time [s]
0.006
0.005
0.005
0.004
0.006
0.004
0.005
0.005
0.004
0.344
0.066
0.720
0.147
0.059
0.097
0.146
0.307
1.551
timeout
1276.770
496.549
timeout
1612.443
timeout
1.107
50.351
1708.425
graphs.

|V |

|E|

|R|

Opt

Time [s]

2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000

11600
11600
11600
11600
11600
11600
11600
11600
11600
11600
11600
11600
11600
11600
11600

9
9
9
9
9
9
9
9
9
50
49
48
50
50
49

28000
32000
28000
28000
29000
25000
27000
33000
29000
–
80000
76000
–
–
–

0.015
0.013
0.011
0.011
0.011
0.009
0.012
0.016
0.011
memout
2819.259
3152.193
timeout
timeout
timeout

29

Instance

|V |

2r231
2000
2r232
2000
2r233
2000
Table 12: Results on

Instance

|V |

|E|

|R|

11600
11600
11600
the testset

|E|

Opt

Time [s]

50
–
timeout
49
–
timeout
47
–
timeout
2R. Type: 3D grid graphs.

|R|

Opt

Time [s]

es10fst01
18
20
10
22920745
0.000
es10fst02
14
13
10
19134104
0.000
es10fst03
17
20
10
26003678
0.000
es10fst04
18
20
10
20461116
0.000
es10fst05
12
11
10
18818916
0.000
es10fst06
17
20
10
26540768
0.000
es10fst07
14
13
10
26025072
0.000
es10fst08
21
28
10
25056214
0.000
es10fst09
21
29
10
22062355
0.000
es10fst10
18
21
10
23936095
0.000
es10fst11
14
13
10
22239535
0.000
es10fst12
13
12
10
19626318
0.000
es10fst13
18
21
10
19483914
0.000
es10fst14
24
32
10
21856128
0.000
es10fst15
16
18
10
18641924
0.000
Table 13: Results on the testset ES10FST. Type: Rectilinear instances after FST-preprocessing by GeoSteiner.

Instance

|V |

|E|

|R|

Opt

Time [s]

es20fst01
29
28
20
33703886
0.004
es20fst02
29
28
20
32639486
0.001
es20fst03
27
26
20
27847417
0.001
es20fst04
57
83
20
27624394
0.003
es20fst05
54
77
20
34033163
0.002
es20fst06
29
28
20
36014241
0.001
es20fst07
45
59
20
34934874
0.002
es20fst08
52
74
20
38016346
0.014
es20fst09
36
42
20
36739939
0.003
es20fst10
49
67
20
34024740
0.002
es20fst11
33
36
20
27123908
0.001
es20fst12
33
36
20
30451397
0.005
es20fst13
35
40
20
34438673
0.003
es20fst14
36
44
20
34062374
0.009
es20fst15
37
43
20
32303746
0.003
Table 14: Results on the testset ES20FST. Type: Rectilinear instances after FST-preprocessing by GeoSteiner.

30

Instance

|V |

|E|

|R|

Opt

Time [s]

es30fst01
79
115
30
40692993
0.037
es30fst02
71
97
30
40900061
0.029
es30fst03
83
120
30
43120444
0.019
es30fst04
80
115
30
42150958
0.010
es30fst05
58
71
30
41739748
0.007
es30fst06
83
119
30
39955139
0.053
es30fst07
53
64
30
43761391
0.007
es30fst08
69
93
30
41691217
0.008
es30fst09
43
44
30
37133658
0.010
es30fst10
48
52
30
42686610
0.009
es30fst11
79
112
30
41647993
0.007
es30fst12
46
48
30
38416720
0.013
es30fst13
65
84
30
37406646
0.005
es30fst14
53
58
30
42897025
0.021
es30fst15
118
188
30
43035576
0.070
Table 15: Results on the testset ES30FST. Type: Rectilinear instances after FST-preprocessing by GeoSteiner.

Instance

|V |

|E|

|R|

Opt

Time [s]

es40fst01
93
127
40
44841522
0.036
es40fst02
82
105
40
46811310
0.016
es40fst03
87
116
40
49974157
0.093
es40fst04
55
55
40
45289864
0.013
es40fst05
121
180
40
51940413
0.133
es40fst06
92
123
40
49753385
0.046
es40fst07
77
95
40
45639009
0.109
es40fst08
98
137
40
48745996
0.016
es40fst09
107
153
40
51761789
0.040
es40fst10
107
152
40
57136852
0.117
es40fst11
97
135
40
46734214
0.027
es40fst12
67
75
40
43843378
0.029
es40fst13
78
95
40
51884545
0.030
es40fst14
98
134
40
49166952
0.030
es40fst15
93
129
40
50828067
0.050
Table 16: Results on the testset ES40FST. Type: Rectilinear instances after FST-preprocessing by GeoSteiner.

Instance

|V |

|E|

|R|

Opt

Time [s]

es50fst01
es50fst02
es50fst03
es50fst04

118
125
128
106

160
177
182
138

50
50
50
50

54948660
55484245
54691035
51535766

0.053
0.474
0.075
0.348

31

Instance

|V |

|E|

|R|

Opt

Time [s]

es50fst05
104
135
50
55186015
0.280
es50fst06
126
182
50
55804287
0.539
es50fst07
143
211
50
49961178
0.049
es50fst08
83
96
50
53754708
0.089
es50fst09
139
202
50
53456773
0.538
es50fst10
139
207
50
54037963
3.006
es50fst11
100
131
50
52532923
0.019
es50fst12
110
149
50
53409291
0.172
es50fst13
92
116
50
53891019
0.032
es50fst14
120
167
50
53551419
0.082
es50fst15
112
147
50
52180862
0.105
Table 17: Results on the testset ES50FST. Type: Rectilinear instances after FST-preprocessing by GeoSteiner.

Instance

|V |

|E|

|R|

Opt

Time [s]

es60fst01
123
159
60
53761423
0.436
es60fst02
186
280
60
55367804
3.033
es60fst03
113
142
60
56566797
0.066
es60fst04
162
238
60
55371042
0.118
es60fst05
119
148
60
54704991
0.059
es60fst06
130
174
60
60421961
1.064
es60fst07
188
280
60
58978041
0.073
es60fst08
109
133
60
58138178
0.366
es60fst09
151
216
60
55877112
0.493
es60fst10
133
177
60
57624488
0.039
es60fst11
121
154
60
56141666
0.523
es60fst12
176
257
60
59791362
3.289
es60fst13
157
226
60
61213533
0.091
es60fst14
118
149
60
56035528
0.058
es60fst15
117
151
60
56622581
0.104
Table 18: Results on the testset ES60FST. Type: Rectilinear instances after FST-preprocessing by GeoSteiner.

Instance

|V |

|E|

|R|

Opt

Time [s]

att48fst
139
202
48
30236
0.453
berlin52fst
89
104
52
6760
33.108
eil51fst
181
289
51
409
513.690
Table 19: Results on the testset TSPFST. Type: Rectilinear instances after FST-preprocessing by GeoSteiner.

32

Instance

|V |

|E|

|R|

Opt

Time [s]

ind1
18
31
10
604
0.001
ind2
31
57
10
9500
0.001
ind3
16
23
10
600
0.000
ind4
74
146
25
1086
0.023
ind5
114
228
33
1341
0.021
rc01
21
35
10
25980
0.000
rc02
87
176
30
41350
0.029
rc03
109
202
50
54160
0.153
rt01
262
740
10
2146
0.002
rt02
788
1938
50
45852
0.703
Table 20: Results on the testset Copenhagen14. Type: Instances of
the Obstacle-avoiding rectilinear Steiner tree problem after FSTpreprocessing by ObSteiner and merging the FSTs into a single
graph.

Instance

|V |

|E|

|R|

Opt

Time [s]

wrp3-11
wrp3-12
wrp3-13
wrp3-14
wrp3-15
wrp3-16
wrp3-17
wrp3-19
wrp3-20
wrp3-21
wrp3-22
wrp3-23
wrp3-24
wrp3-25
wrp3-26
wrp3-27
wrp3-28
wrp3-29
wrp3-30
wrp3-31
wrp3-33
wrp3-34
wrp3-36
wrp3-37
wrp3-38
wrp3-39
wrp3-41

128
84
311
128
138
204
177
189
245
237
233
132
262
246
402
370
307
245
467
323
437
1244
435
1011
603
703
178

227
149
613
247
257
374
354
353
454
444
431
230
487
468
780
721
559
436
896
592
838
2474
818
2010
1207
1616
307

11
12
13
14
15
16
17
19
20
21
22
23
24
25
26
27
28
29
30
31
33
34
36
37
38
39
41

1100361
1200237
1300497
1400250
1500422
1600208
1700442
1900439
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–

0.099
0.123
20.014
3.780
51.156
11.622
422.079
1765.723
timeout
timeout
timeout
timeout
timeout
memout
memout
timeout
memout
memout
memout
timeout
memout
memout
memout
memout
timeout
memout
memout

33

Instance

|V |

|E|

|R|

Opt

Time [s]

wrp3-42
705
1373
42
–
memout
wrp3-43
173
298
43
–
memout
wrp3-45
1414
2813
45
–
memout
wrp3-48
925
1738
48
–
memout
wrp3-49
886
1800
49
–
memout
wrp3-50
1119
2251
50
–
memout
wrp3-52
701
1352
52
–
memout
wrp3-53
775
1471
53
–
memout
wrp3-55
1645
3186
55
–
memout
wrp3-56
853
1590
56
–
memout
wrp3-60
838
1763
60
–
memout
wrp3-62
670
1316
62
–
memout
Table 21: Results on the testset WRP3. Type: Group Steiner tree
instances arising from VLSI design modeled as Steiner tree instances by connecting each terminal to the vertices if its group
by edges of very high cost.

Instance

|V |

|E|

|R|

Opt

Time [s]

wrp4-11
wrp4-13
wrp4-14
wrp4-15
wrp4-16
wrp4-17
wrp4-18
wrp4-19
wrp4-21
wrp4-22
wrp4-23
wrp4-24
wrp4-25
wrp4-26
wrp4-27
wrp4-28
wrp4-29
wrp4-30
wrp4-31
wrp4-32
wrp4-33
wrp4-34
wrp4-35
wrp4-36
wrp4-37

123
110
145
193
311
223
211
119
529
294
257
493
422
396
243
272
247
361
390
311
304
314
471
363
522

233
188
283
369
579
404
380
206
1032
568
515
963
808
781
497
545
505
724
786
632
571
650
954
750
1054

11
13
14
15
16
17
18
19
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

1100179
1300798
1400290
1500405
1601190
1700525
1801464
1901446
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–

0.241
0.019
2.798
8.193
149.542
69.524
1212.777
0.925
timeout
timeout
memout
memout
memout
memout
memout
memout
memout
memout
memout
memout
timeout
memout
memout
memout
memout

34

Instance

|V |

|E|

|R|

Opt

Time [s]

wrp4-38
294
618
38
–
memout
wrp4-39
802
1553
39
–
memout
wrp4-40
538
1088
40
–
memout
wrp4-41
465
955
41
–
memout
wrp4-42
552
1131
42
–
memout
wrp4-43
596
1148
43
–
timeout
wrp4-44
398
788
44
–
memout
wrp4-45
388
815
45
–
memout
wrp4-46
632
1287
46
–
memout
wrp4-47
555
1098
47
–
memout
wrp4-48
451
825
48
–
timeout
wrp4-49
557
1080
49
–
memout
wrp4-50
564
1112
50
–
memout
wrp4-51
668
1306
51
–
memout
wrp4-52
547
1115
52
–
memout
wrp4-53
615
1232
53
–
memout
wrp4-54
688
1388
54
–
memout
wrp4-55
610
1201
55
–
memout
wrp4-56
839
1617
56
–
memout
wrp4-58
757
1493
58
–
memout
wrp4-59
904
1806
59
–
memout
wrp4-60
693
1370
60
–
memout
wrp4-61
775
1538
61
–
timeout
wrp4-62
1283
2493
62
–
memout
wrp4-63
1121
2227
63
–
memout
Table 22: Results on the testset WRP4. Type: Group Steiner tree
instances arising from VLSI design modeled as Steiner tree instances by connecting each terminal to the vertices if its group
by edges of very high cost.

Instance

|V |

|E|

|R|

Opt

Time [s]

I052a
160
237
23
13309487
0.013
I054a
540
817
25
15841596
0.021
I056a
290
439
34
14171206
0.086
Table 23: Results on the testset vienna-i-advanced. Type: Realworld telecommunication networks after an “advanced” preprocessing routine. We report the cost of an optimum solution in the original instance, computed as the sum of an optimum solution in the
reduced instance and the fixed cost induced by the reductions.

35

Instance

|V |

|E|

|R|

Opt

Time [s]

I052
2363
3761
40
–
timeout
I054
3803
6213
38
–
timeout
I056
1991
3176
51
–
timeout
Table 24: Results on the testset vienna-i-simple. Type: Real-world
telecommunication networks after a “simple” preprocessing routine.

Instance

|V |

|E|

|R|

Opt

Time [s]

berlin52
52
1326
16
1044
0.013
brasil58
58
1653
25
13655
0.005
Table 25: Results on the testset X. Type: Complete graphs with
Euclidean costs.

Instance

|V |

p455
100
p456
100
p457
100
p458
100
p459
100
p460
100
p461
100
p463
200
p464
200
p465
200
Table 26: Results on the
Euclidean costs.

Instance

|V |

p401
100
p402
100
p403
100
p404
100
p405
100
p406
100
p407
100
p408
100
p409
100
p410
100
Table 27: Results on the
random costs.

|E|

|R|

4950
4950
4950
4950
4950
4950
4950
19900
19900
19900
testset P4E.

|E|

5
5
10
10
20
20
50
10
20
40
Type:

|R|

Opt

Time [s]

1138
0.001
1228
0.001
1609
0.001
1868
0.002
2345
0.003
2959
0.005
4474
0.030
1510
0.005
2545
0.012
3853
0.066
Complete graphs with

Opt

Time [s]

4950
5
155
0.001
4950
5
116
0.001
4950
5
179
0.001
4950
10
270
0.001
4950
10
270
0.002
4950
10
290
0.003
4950
20
590
0.257
4950
20
542
0.154
4950
50
963
4350.849
4950
50
1010
245.304
testset P4Z. Type: Complete graphs with

36

Instance

|V |

p619
100
p620
100
p621
100
p622
100
p623
100
p624
100
p625
100
p626
100
p627
100
p628
100
p629
100
p630
200
p631
200
p632
200
Table 28: Results on the
Euclidean costs.

Instance

|V |

p602
100
p603
100
p604
100
p605
100
p606
100
p607
100
p608
100
p609
100
p610
100
p611
100
p612
100
p613
200
p614
200
p615
200
Table 29: Results on the
random costs.

Instance
b01
b02
b03
b04
b05
b06
b07

|E|

|R|

Opt

Time [s]

180
5
7485
0.001
180
5
8746
0.001
180
5
8688
0.001
180
10
15972
0.001
180
10
19496
0.002
180
20
20246
0.003
180
20
23078
0.003
180
20
22346
0.011
180
50
40647
0.023
180
50
40008
0.052
180
50
43287
0.043
370
10
26125
0.001
370
20
39067
0.010
370
40
56217
0.038
testset P6E. Type: Sparse graphs with

|E|

|R|

Opt

Time [s]

180
5
8083
0.001
180
5
5022
0.001
180
10
11397
0.001
180
10
10355
0.001
180
11
13048
0.001
180
21
15358
0.003
180
21
14439
0.002
180
20
18263
0.004
180
50
30161
0.034
180
50
26903
0.090
180
50
30258
0.107
370
10
18429
0.001
370
20
27276
0.017
370
40
42474
0.049
testset P6Z. Type: Sparse graphs with

|V |

|E|

|R|

Opt

Time [s]

50
50
50
50
50
50
75

63
63
63
100
100
100
94

9
13
25
9
13
25
13

82
83
138
59
61
122
111

0.001
0.003
0.136
0.001
0.008
0.256
0.005

37

Instance

|V |

b08
75
b09
75
b10
75
b11
75
b12
75
b13
100
b14
100
b15
100
b16
100
b17
100
b18
100
Table 30: Results on the
with random costs.

Instance

|V |

|E|
94
94
150
150
150
125
125
125
200
200
200
testset B.

|E|

|R|

Opt

Time [s]

19
104
0.004
38
220
1858.382
13
86
0.006
19
88
0.019
38
174
98.165
17
165
0.111
25
235
1.704
50
318
176.192
17
127
0.008
25
131
266.814
50
218
3228.991
Type: Random sparse graphs

|R|

Opt

Time [s]

c01
500
625
5
85
0.002
c02
500
625
10
144
0.005
c06
500
1000
5
55
0.003
c07
500
1000
10
102
0.024
c11
500
2500
5
32
0.004
c12
500
2500
10
46
0.012
c16
500
12500
5
11
0.005
c17
500
12500
10
18
0.011
Table 31: Results on the testset C. Type: Random sparse graphs
with random costs.

Instance

|V |

|E|

|R|

Opt

Time [s]

d01
1000
1250
5
106
0.004
d02
1000
1250
10
220
0.052
d06
1000
2000
5
67
0.004
d07
1000
2000
10
103
0.010
d11
1000
5000
5
29
0.007
d12
1000
5000
10
42
0.016
d16
1000
25000
5
13
0.011
d17
1000
25000
10
23
0.072
Table 32: Results on the testset D. Type: Random sparse graphs
with random costs.

38

Instance

|V |

e01
2500
e02
2500
e06
2500
e07
2500
e11
2500
e12
2500
e16
2500
e17
2500
Table 33: Results on the
with random costs.

|E|

|R|

Opt

Time [s]

3125
5
111
0.007
3125
10
214
0.045
5000
5
73
0.008
5000
10
145
0.230
12500
5
34
0.009
12500
10
67
0.161
62500
5
15
0.016
62500
10
25
0.124
testset E. Type: Random sparse graphs

Instance

|V |

|E|

|R|

Opt

Time [s]

i080-001
i080-002
i080-003
i080-004
i080-005
i080-011
i080-012
i080-013
i080-014
i080-015
i080-021
i080-022
i080-023
i080-024
i080-025
i080-031
i080-032
i080-033
i080-034
i080-035
i080-041
i080-042
i080-043
i080-044
i080-045
i080-101
i080-102
i080-103
i080-104
i080-105
i080-111
i080-112

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80

120
120
120
120
120
350
350
350
350
350
3160
3160
3160
3160
3160
160
160
160
160
160
632
632
632
632
632
120
120
120
120
120
350
350

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
8
8
8
8
8
8
8

1787
1607
1713
1866
1790
1479
1484
1381
1397
1495
1175
1178
1174
1161
1162
1570
2088
1794
1688
1862
1276
1287
1295
1366
1310
2608
2403
2603
2486
2203
2051
1885

0.001
0.000
0.000
0.000
0.001
0.001
0.001
0.001
0.001
0.001
0.004
0.004
0.004
0.004
0.004
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.002
0.002
0.001
0.008
0.006

39

Instance

|V |

|E|

|R|

Opt

Time [s]

i080-113
i080-114
i080-115
i080-121
i080-122
i080-123
i080-124
i080-125
i080-131
i080-132
i080-133
i080-134
i080-135
i080-141
i080-142
i080-143
i080-144
i080-145
i080-201
i080-202
i080-203
i080-204
i080-205
i080-211
i080-212
i080-213
i080-214
i080-215
i080-221
i080-222
i080-223
i080-224
i080-225
i080-231
i080-232
i080-233
i080-234
i080-235
i080-241
i080-242
i080-243
i080-244
i080-245
i080-301
i080-302
i080-303

80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80

350
350
350
3160
3160
3160
3160
3160
160
160
160
160
160
632
632
632
632
632
120
120
120
120
120
350
350
350
350
350
3160
3160
3160
3160
3160
160
160
160
160
160
632
632
632
632
632
120
120
120

8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
20
20
20

1884
1895
1868
1561
1561
1569
1555
1572
2284
2180
2261
2070
2102
1788
1708
1767
1772
1762
4760
4650
4599
4492
4564
3631
3677
3678
3734
3681
3158
3141
3156
3159
3150
4354
4199
4118
4274
4487
3538
3458
3474
3466
3467
5519
5944
5777

0.004
0.005
0.004
0.023
0.023
0.023
0.022
0.024
0.001
0.003
0.002
0.002
0.001
0.009
0.009
0.016
0.015
0.013
0.128
0.111
0.891
8.025
0.615
108.657
104.799
106.887
107.154
107.424
111.565
113.026
112.402
114.264
114.489
32.829
26.645
16.691
0.898
2.326
146.827
141.589
139.922
143.147
142.418
38.991
10.556
19.155

40

Instance

|V |

i080-304
80
i080-305
80
i080-311
80
i080-312
80
i080-313
80
i080-314
80
i080-315
80
i080-321
80
i080-322
80
i080-323
80
i080-324
80
i080-325
80
i080-331
80
i080-332
80
i080-333
80
i080-334
80
i080-335
80
i080-341
80
i080-342
80
i080-343
80
i080-344
80
i080-345
80
Table 34: Results on the
so-called incidence costs,

|E|

|R|

Opt

Time [s]

120
20
5586
6.392
120
20
5932
201.235
350
20
–
timeout
350
20
–
timeout
350
20
–
timeout
350
20
–
timeout
350
20
–
timeout
3160
20
–
timeout
3160
20
–
timeout
3160
20
–
timeout
3160
20
–
timeout
3160
20
–
timeout
160
20
5226
814.502
160
20
5362
902.230
160
20
5381
541.448
160
20
5264
920.974
160
20
4953
1004.156
632
20
–
timeout
632
20
–
timeout
632
20
–
timeout
632
20
–
timeout
632
20
–
timeout
testset I080. Type: Random graphs with
designed to defy preprocessing.

Instance

|V |

|E|

|R|

Opt

Time [s]

i160-001
i160-002
i160-003
i160-004
i160-005
i160-011
i160-012
i160-013
i160-014
i160-015
i160-021
i160-022
i160-023
i160-024
i160-025
i160-031
i160-032
i160-033

160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160

240
240
240
240
240
812
812
812
812
812
12720
12720
12720
12720
12720
320
320
320

7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7

2490
2158
2297
2370
2495
1677
1750
1661
1778
1768
1352
1365
1351
1371
1366
2170
2330
2101

0.004
0.001
0.002
0.002
0.002
0.007
0.008
0.005
0.008
0.009
0.055
0.057
0.056
0.058
0.054
0.003
0.003
0.005

41

Instance

|V |

|E|

|R|

Opt

Time [s]

i160-034
i160-035
i160-041
i160-042
i160-043
i160-044
i160-045
i160-101
i160-102
i160-103
i160-104
i160-105
i160-111
i160-112
i160-113
i160-114
i160-115
i160-121
i160-122
i160-123
i160-124
i160-125
i160-131
i160-132
i160-133
i160-134
i160-135
i160-141
i160-142
i160-143
i160-144
i160-145
i160-201
i160-202
i160-203
i160-204
i160-205
i160-211
i160-212
i160-213
i160-214
i160-215
i160-221
i160-222
i160-223
i160-224

160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160

320
320
2544
2544
2544
2544
2544
240
240
240
240
240
812
812
812
812
812
12720
12720
12720
12720
12720
320
320
320
320
320
2544
2544
2544
2544
2544
240
240
240
240
240
812
812
812
812
812
12720
12720
12720
12720

7
7
7
7
7
7
7
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
24
24
24
24
24
24
24
24
24
24
24
24
24
24

2083
2103
1494
1486
1549
1478
1554
3859
3747
3837
4063
3563
2869
2924
2866
2989
2937
2363
2348
2355
2352
2351
3356
3450
3585
3470
3716
2549
2562
2557
2607
2578
–
–
7243
–
–
–
–
–
–
–
–
–
–
–

0.003
0.004
0.013
0.013
0.016
0.011
0.015
0.082
0.205
0.093
0.014
0.034
1.430
2.304
1.575
1.949
1.436
5.395
5.355
5.418
5.330
5.459
0.306
0.205
0.345
0.095
0.286
3.398
3.434
2.955
3.238
3.451
timeout
timeout
4173.679
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout

42

Instance

|V |

i160-225
160
i160-231
160
i160-232
160
i160-233
160
i160-234
160
i160-235
160
i160-241
160
i160-242
160
i160-243
160
i160-244
160
i160-245
160
i160-301
160
i160-302
160
i160-303
160
i160-304
160
i160-305
160
i160-311
160
i160-312
160
i160-313
160
i160-314
160
i160-315
160
i160-321
160
i160-322
160
i160-323
160
i160-324
160
i160-325
160
i160-331
160
i160-332
160
i160-333
160
i160-334
160
i160-335
160
i160-341
160
i160-342
160
i160-343
160
i160-344
160
i160-345
160
Table 35: Results on the
so-called incidence costs,

|E|

|R|

Opt

Time [s]

12720
24
–
timeout
320
24
–
timeout
320
24
–
timeout
320
24
–
timeout
320
24
–
timeout
320
24
–
timeout
2544
24
–
timeout
2544
24
–
timeout
2544
24
–
timeout
2544
24
–
timeout
2544
24
–
timeout
240
40
–
memout
240
40
–
memout
240
40
–
memout
240
40
–
memout
240
40
–
memout
812
40
–
memout
812
40
–
memout
812
40
–
memout
812
40
–
memout
812
40
–
memout
12720
40
–
memout
12720
40
–
memout
12720
40
–
memout
12720
40
–
memout
12720
40
–
memout
320
40
–
memout
320
40
–
memout
320
40
–
memout
320
40
–
memout
320
40
–
memout
2544
40
–
memout
2544
40
–
memout
2544
40
–
memout
2544
40
–
memout
2544
40
–
memout
testset I160. Type: Random graphs with
designed to defy preprocessing.

Instance

|V |

|E|

|R|

Opt

Time [s]

i320-001
i320-002
i320-003
i320-004

320
320
320
320

480
480
480
480

8
8
8
8

2672
2847
2972
2905

0.003
0.004
0.004
0.007

43

Instance

|V |

|E|

|R|

Opt

Time [s]

i320-005
i320-011
i320-012
i320-013
i320-014
i320-015
i320-021
i320-022
i320-023
i320-024
i320-025
i320-031
i320-032
i320-033
i320-034
i320-035
i320-041
i320-042
i320-043
i320-044
i320-045
i320-101
i320-102
i320-103
i320-104
i320-105
i320-111
i320-112
i320-113
i320-114
i320-115
i320-121
i320-122
i320-123
i320-124
i320-125
i320-131
i320-132
i320-133
i320-134
i320-135
i320-141
i320-142
i320-143
i320-144
i320-145

320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320
320

480
1845
1845
1845
1845
1845
51040
51040
51040
51040
51040
640
640
640
640
640
10208
10208
10208
10208
10208
480
480
480
480
480
1845
1845
1845
1845
1845
51040
51040
51040
51040
51040
640
640
640
640
640
10208
10208
10208
10208
10208

8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17

2991
2053
1997
2072
2061
2059
1553
1565
1549
1553
1550
2673
2770
2769
2521
2385
1707
1682
1723
1681
1686
5548
5556
6239
5703
5928
4273
4213
4205
4104
4238
3321
3314
3332
3323
3340
5255
5052
5125
5272
5342
3606
3567
3561
3512
3601

0.006
0.031
0.023
0.039
0.035
0.040
0.366
0.414
0.373
0.360
0.360
0.011
0.010
0.010
0.005
0.007
0.061
0.050
0.059
0.067
0.056
16.131
10.289
178.463
108.739
84.748
1706.674
1872.720
1464.609
1581.733
1747.827
2381.939
2336.603
2379.991
2342.527
2353.655
343.942
33.234
44.197
374.938
211.986
2246.125
2305.369
2244.354
2244.792
2261.946

44

Instance

|V |

i320-201
320
i320-202
320
i320-203
320
i320-204
320
i320-205
320
i320-211
320
i320-212
320
i320-213
320
i320-214
320
i320-215
320
i320-221
320
i320-222
320
i320-223
320
i320-224
320
i320-225
320
i320-231
320
i320-232
320
i320-233
320
i320-234
320
i320-235
320
i320-241
320
i320-242
320
i320-243
320
i320-244
320
i320-245
320
Table 36: Results on the
so-called incidence costs,

|E|

|R|

Opt

Time [s]

480
34
–
memout
480
34
–
memout
480
34
–
memout
480
34
–
memout
480
34
–
memout
1845
34
–
memout
1845
34
–
memout
1845
34
–
memout
1845
34
–
memout
1845
34
–
memout
51040
34
–
memout
51040
34
–
memout
51040
34
–
memout
51040
34
–
memout
51040
34
–
memout
640
34
–
memout
640
34
–
memout
640
34
–
memout
640
34
–
memout
640
34
–
memout
10208
34
–
memout
10208
34
–
memout
10208
34
–
memout
10208
34
–
memout
10208
34
–
memout
testset I320. Type: Random graphs with
designed to defy preprocessing.

Instance

|V |

|E|

|R|

Opt

Time [s]

i640-001
i640-002
i640-003
i640-004
i640-005
i640-011
i640-012
i640-013
i640-014
i640-015
i640-021
i640-022
i640-023
i640-024
i640-025

640
640
640
640
640
640
640
640
640
640
640
640
640
640
640

960
960
960
960
960
4135
4135
4135
4135
4135
204480
204480
204480
204480
204480

9
9
9
9
9
9
9
9
9
9
9
9
9
9
9

4033
3588
3438
4000
4006
2392
2465
2399
2171
2347
1749
1756
1754
1751
1745

0.042
0.030
0.024
0.070
0.055
0.163
0.271
0.205
0.038
0.126
4.426
4.031
4.499
4.081
4.452

45

Instance

|V |

|E|

|R|

Opt

Time [s]

i640-031
i640-032
i640-033
i640-034
i640-035
i640-041
i640-042
i640-043
i640-044
i640-045
i640-101
i640-102
i640-103
i640-104
i640-105
i640-111
i640-112
i640-113
i640-114
i640-115
i640-121
i640-122
i640-123
i640-124
i640-125
i640-131
i640-132
i640-133
i640-134
i640-135
i640-141
i640-142
i640-143
i640-144
i640-145
i640-201
i640-202
i640-203
i640-204
i640-205
i640-211
i640-212
i640-213
i640-214
i640-215
i640-221

640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640
640

1280
1280
1280
1280
1280
40896
40896
40896
40896
40896
960
960
960
960
960
4135
4135
4135
4135
4135
204480
204480
204480
204480
204480
1280
1280
1280
1280
1280
40896
40896
40896
40896
40896
960
960
960
960
960
4135
4135
4135
4135
4135
204480

9
9
9
9
9
9
9
9
9
9
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
25
50
50
50
50
50
50
50
50
50
50
50

3278
3187
3260
2953
3292
1897
1934
1931
1938
1866
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–

0.065
0.056
0.062
0.015
0.033
0.957
0.811
0.889
0.975
0.403
timeout
timeout
timeout
timeout
timeout
memout
memout
memout
memout
memout
memout
memout
memout
memout
memout
timeout
timeout
timeout
timeout
timeout
memout
memout
memout
memout
memout
memout
memout
memout
memout
memout
memout
memout
memout
memout
memout
memout

46

Instance

|V |

|E|

|R|

Opt

Time [s]

i640-222
640
204480
50
–
memout
i640-223
640
204480
50
–
memout
i640-224
640
204480
50
–
memout
i640-225
640
204480
50
–
memout
i640-231
640
1280
50
–
memout
i640-232
640
1280
50
–
memout
i640-233
640
1280
50
–
memout
i640-234
640
1280
50
–
memout
i640-235
640
1280
50
–
memout
i640-241
640
40896
50
–
memout
i640-242
640
40896
50
–
memout
i640-243
640
40896
50
–
memout
i640-244
640
40896
50
–
memout
i640-245
640
40896
50
–
memout
Table 37: Results on the testset I640. Type: Random graphs with
so-called incidence costs, designed to defy preprocessing.

Instance

|V |

|E|

|R|

Opt

Time [s]

bipe2p
550
5013
50
–
memout
bipe2u
550
5013
50
–
memout
cc3-10p
1000
13500
50
–
memout
cc3-10u
1000
13500
50
–
memout
cc3-11p
1331
19965
61
–
memout
cc3-11u
1331
19965
61
–
memout
cc3-4p
64
288
8
2338
0.006
cc3-4u
64
288
8
23
0.008
cc3-5p
125
750
13
3661
3.450
cc3-5u
125
750
13
36
4.637
cc5-3p
243
1215
27
–
memout
cc5-3u
243
1215
27
–
memout
cc6-2p
64
192
12
3271
0.166
cc6-2u
64
192
12
32
0.279
hc6p
64
192
32
–
memout
hc6u
64
192
32
–
memout
Table 38: Results on the testset PUC. Type: Artificial instances
designed to be hard for existing solvers.

47

Instance

|V |

|E|

|R|

Opt

cc3-10n
1000
13500
50
cc3-11n
1331
19965
61
cc3-4n
64
288
8
cc3-5n
125
750
13
cc5-3n
243
1215
27
cc6-2n
64
192
12
Table 39: Results on the testset SPG-PUCN.
instances of the PUC testset, which contains
designed to be hard for existing solvers.

Instance

|V |

|E|

|R|

antiwheel5
10
15
design432
8
20
oddcycle3
6
9
oddwheel3
7
9
se03
13
21
Table 40: Results on the testset SP.

Instance

|V |

|E|

Time [s]

–
memout
–
memout
13
0.002
20
0.563
–
memout
18
0.047
Type: Unweighted
artificial instances

Opt

Time [s]

5
7
0.000
4
9
0.000
3
4
0.000
4
5
0.000
4
12
0.000
Type: Artificial instances.

|R|

Opt

Time [s]

mc2
120
7140
60
–
memout
mc3
97
4656
45
–
timeout
Table 41: Results on the testset MC. Type: Artificial instances.

Instance

|V |

|E|

|R|

Opt

Time [s]

csd02
3
2
1
0
0.000
csd03
6
6
3
4
0.000
csd04
10
12
6
8
0.000
csd05
15
20
10
13
0.007
csd06
21
30
15
19
2.724
csd07
28
42
21
26
6138.678
csd08
36
56
28
–
timeout
csd09
45
72
36
–
memout
csd10
55
90
45
–
memout
csd11
66
110
55
–
memout
Table 42: Results on the testset csd. Type: Artificial instances arising from generalizations of Steiner tree LP gap examples.

48

Instance
g01-00
g01-01
g01-02
g01-03
g01-04
g01-05
g01-06
g01-07
g01-08
g01-09
g01-10
g01-11
g01-12
g01-13
g01-14
g01-15
g02-00
g02-01
g02-02
g02-03
g02-04
g02-05
g02-06
g02-07
g02-08
g02-09
g02-10
g02-11
g02-12
g02-13
g02-14
g02-15
g03-00
g03-01
g03-02
g03-03
g03-04
g03-05
g03-06
g03-07
g03-08
g03-09
g03-10
g03-11
g03-12
g03-13

|V |

|E|

|R|

Opt

Time [s]

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
11
12
13
14
15
16
17
18
19
20
21
22
23
24

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
25
26
27
28
29
30
31
32
33
34
35
36
37
38

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
5
6
7
8
9
10
11
12
13
14
15
16
17
18

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
22
23
24
25
26
27
28
29
30
31
32
33
34
35

0.000
0.000
0.000
0.000
0.000
0.001
0.004
0.007
0.016
0.067
0.172
0.490
2.220
18.637
42.576
39.915
0.000
0.000
0.000
0.000
0.001
0.004
0.013
0.035
0.135
0.352
1.354
6.346
25.602
114.366
300.818
1171.010
0.000
0.000
0.000
0.001
0.004
0.016
0.067
0.145
0.417
1.536
6.411
28.536
106.674
407.020

49

Instance
g03-14
g03-15
g04-00
g04-01
g04-02
g04-03
g04-04
g04-05
g04-06
g04-07
g04-08
g04-09
g04-10
g04-11
g04-12
g04-13
g04-14
g04-15
g05-00
g05-01
g05-02
g05-03
g05-04
g05-05
g05-06
g05-07
g05-08
g05-09
g05-10
g05-11
g05-12
g05-13
g05-14
g05-15
g06-00
g06-01
g06-02
g06-03
g06-04
g06-05
g06-06
g06-07
g06-08
g06-09
g06-10
g06-11

|V |

|E|

|R|

Opt

Time [s]

25
26
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
17
18
19
20
21
22
23
24
25
26
27
28

39
40
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
64
65
66
67
68
69
70
71
72
73
74
75

19
20
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
8
9
10
11
12
13
14
15
16
17
18
19

36
37
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
–
44
45
46
47
48
49
50
51
52
53
54
55
56
57
–
–
58
59
60
61
62
63
64
65
66
67
68
69

1414.010
4935.897
0.000
0.001
0.002
0.007
0.022
0.062
0.155
0.424
1.571
6.114
26.880
103.263
379.413
1380.378
4854.754
timeout
0.001
0.002
0.007
0.023
0.065
0.164
0.417
1.502
5.839
22.368
89.853
331.230
1183.867
4559.627
timeout
timeout
0.002
0.006
0.022
0.061
0.150
0.403
1.441
5.374
20.749
80.435
307.301
1129.370

50

Instance
g06-12
g06-13
g06-14
g06-15
g07-00
g07-01
g07-02
g07-03
g07-04
g07-05
g07-06
g07-07
g07-08
g07-09
g07-10
g07-11
g07-12
g07-13
g07-14
g07-15
g08-00
g08-01
g08-02
g08-03
g08-04
g08-05
g08-06
g08-07
g08-08
g08-09
g08-10
g08-11
g08-12
g08-13
g08-14
g08-15
g09-00
g09-01
g09-02
g09-03
g09-04
g09-05
g09-06
g09-07
g09-08
g09-09

|V |

|E|

|R|

Opt

Time [s]

29
30
31
32
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
23
24
25
26
27
28
29
30
31
32

76
77
78
79
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
121
122
123
124
125
126
127
128
129
130

20
21
22
23
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
11
12
13
14
15
16
17
18
19
20

70
–
–
–
74
75
76
77
78
79
80
81
82
83
84
85
–
–
–
–
92
93
94
95
96
97
98
99
100
101
102
–
–
–
–
–
112
113
114
115
116
117
118
119
120
121

4294.387
timeout
timeout
timeout
0.003
0.011
0.037
0.112
0.390
1.370
5.032
19.383
76.224
276.931
1064.745
4173.155
timeout
timeout
timeout
timeout
0.009
0.032
0.108
0.383
1.309
4.942
18.081
68.314
262.768
1019.464
3956.305
timeout
timeout
timeout
timeout
timeout
0.028
0.150
0.383
1.291
4.625
17.479
66.582
240.706
939.553
3748.635

51

Instance
g09-10
g09-11
g09-12
g09-13
g09-14
g09-15
g10-00
g10-01
g10-02
g10-03
g10-04
g10-05
g10-06
g10-07
g10-08
g10-09
g10-10
g10-11
g10-12
g10-13
g10-14
g10-15
g11-00
g11-01
g11-02
g11-03
g11-04
g11-05
g11-06
g11-07
g11-08
g11-09
g11-10
g11-11
g11-12
g11-13
g11-14
g11-15
g12-00
g12-01
g12-02
g12-03
g12-04
g12-05
g12-06
g12-07

|V |

|E|

|R|

Opt

Time [s]

33
34
35
36
37
38
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
29
30
31
32
33
34
35
36

131
132
133
134
135
136
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
196
197
198
199
200
201
202
203

21
22
23
24
25
26
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
14
15
16
17
18
19
20
21

–
–
–
–
–
–
134
135
136
137
138
139
140
141
142
–
–
–
–
–
–
–
158
159
160
161
162
163
164
165
–
–
–
–
–
–
–
–
184
185
186
187
188
189
190
–

timeout
timeout
timeout
timeout
timeout
timeout
0.126
0.351
1.228
4.474
17.188
63.640
223.035
878.752
3612.406
timeout
timeout
timeout
timeout
timeout
timeout
timeout
0.369
1.147
4.529
16.525
61.300
216.074
845.014
3514.339
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
0.626
4.491
15.098
59.824
201.250
790.252
3361.075
timeout

52

Instance
g12-08
g12-09
g12-10
g12-11
g12-12
g12-13
g12-14
g12-15
g13-00
g13-01
g13-02
g13-03
g13-04
g13-05
g13-06
g13-07
g13-08
g13-09
g13-10
g13-11
g13-12
g13-13
g13-14
g13-15
g14-00
g14-01
g14-02
g14-03
g14-04
g14-05
g14-06
g14-07
g14-08
g14-09
g14-10
g14-11
g14-12
g14-13
g14-14
g14-15
g15-00
g15-01
g15-02
g15-03
g15-04
g15-05

|V |

|E|

|R|

Opt

Time [s]

37
38
39
40
41
42
43
44
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
35
36
37
38
39
40

204
205
206
207
208
209
210
211
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
289
290
291
292
293
294

22
23
24
25
26
27
28
29
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
17
18
19
20
21
22

–
–
–
–
–
–
–
–
212
213
214
215
216
217
–
–
–
–
–
–
–
–
–
–
242
243
244
245
246
–
–
–
–
–
–
–
–
–
–
–
274
275
276
277
–
–

timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
1.815
14.468
56.674
195.572
728.650
3214.443
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
6.512
53.631
189.942
696.400
2918.275
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
timeout
22.458
181.218
653.425
2738.780
timeout
timeout

53

Instance

|V |

|E|

|R|

Opt

Time [s]

g15-06
41
295
23
–
timeout
g15-07
42
296
24
–
timeout
g15-08
43
297
25
–
timeout
g15-09
44
298
26
–
timeout
g15-10
45
299
27
–
timeout
g15-11
46
300
28
–
timeout
g15-12
47
301
29
–
timeout
g15-13
48
302
30
–
timeout
g15-14
49
303
31
–
timeout
g15-15
50
304
32
–
timeout
Table 43: Results on the testset goemans. Type: Artificial instances
arising from generalizations of Steiner tree LP gap examples.

Instance

|V |

|E|

|R|

Opt

Time [s]

s1
15
35
8
10
0.003
s2
106
399
50
–
memout
Table 44: Results on the testset skutella. Type: Artificial instances
arising from generalizations of Steiner tree LP gap examples.

Instance

|V |

|E|

|R|

Opt

Time [s]

smc01
2
1
1
0
0.000
smc02
3
3
2
2
0.000
smc03
4
6
3
3
0.000
smc04
5
10
4
4
0.000
smc05
6
15
5
5
0.000
smc06
7
21
6
6
0.000
smc07
8
28
7
7
0.000
smc08
9
36
8
8
0.001
smc09
10
45
9
9
0.001
smc10
11
55
10
10
0.002
smc11
12
66
11
11
0.003
smc12
13
78
12
12
0.012
smc13
14
91
13
13
0.046
smc14
15
105
14
14
0.134
smc15
16
120
15
15
0.313
Table 45: Results on the testset smc. Type: Artificial instances
arising from generalizations of Steiner tree LP gap examples.

54

B

Results on Rectilinear Instances

For these experiments, the setup is identical to the one described in Appendix A. For each
instance, first, the Hanan grid was computed and written to an instance file describing
an instance of the Steiner tree problem in graphs. The latter instance was then solved.
The reported run times only include the time to solve the graphic instance, in particular,
the time needed to read in the Hanan grid is not included.
Instance
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3

11
11
11
11
11
12
12
12
12
12
13
13
13
13
13
14
14
14
14
14
15
15
15
15
15
16
16
16
16
16
17
17
17
17
17
18
18
18

01
02
03
04
05
01
02
03
04
05
01
02
03
04
05
01
02
03
04
05
01
02
03
04
05
01
02
03
04
05
01
02
03
04
05
01
02
03

|V |

|E|

|R|

Opt

Time [s]

1331
1331
1331
1331
1331
1728
1728
1728
1728
1728
2197
2197
2197
2197
2197
2744
2744
2744
2744
2744
3375
3375
3375
3375
3375
4096
4096
4096
4096
4096
4913
4913
4913
4913
4913
5832
5832
5832

3630
3630
3630
3630
3630
4752
4752
4752
4752
4752
6084
6084
6084
6084
6084
7644
7644
7644
7644
7644
9450
9450
9450
9450
9450
11520
11520
11520
11520
11520
13872
13872
13872
13872
13872
16524
16524
16524

11
11
11
11
11
12
12
12
12
12
13
13
13
13
13
14
14
14
14
14
15
15
15
15
15
16
16
16
16
16
17
17
17
17
17
18
18
18

311221222
466149453
439391117
413409501
387407782
494141224
443366694
429706282
486545112
444438614
452770450
462700327
474263794
442802506
547158862
438382690
495879854
480652934
473370979
408691456
603071413
528575469
490905559
540300331
535330648
527653658
500606262
468414684
539655260
540126099
555032119
527737314
562083809
589257703
612582645
556545528
549027056
649390363

0.020
0.019
0.058
0.054
0.009
0.032
0.024
0.083
0.031
0.016
0.037
0.238
0.153
0.019
0.032
0.150
0.136
0.048
0.097
0.048
0.352
0.279
0.154
0.201
0.126
0.181
0.213
0.130
0.239
0.140
0.236
0.936
0.405
0.230
3.852
0.291
1.392
0.710

55

|V |

Instance

|E|

|R|

Opt

Time [s]

carioca 3 18 04
5832
16524
18
554907444
0.800
carioca 3 18 05
5832
16524
18
509234906
0.408
6859
19494
19
561743715
6.788
carioca 3 19 01
carioca 3 19 02
6859
19494
19
608506796
1.957
6859
19494
19
574021347
0.398
carioca 3 19 03
carioca 3 19 04
6859
19494
19
630525105
0.342
carioca 3 19 05
6859
19494
19
650204402
6.354
8000
22800
20
638376617
1.613
carioca 3 20 01
carioca 3 20 02
8000
22800
20
477950448
0.148
carioca 3 20 03
8000
22800
20
746979341
8.890
carioca 3 20 04
8000
22800
20
653809733
10.096
8000
22800
20
678171940
1.649
carioca 3 20 05
Table 46: Results on the testset CARIOCA. Type: Random 3-d
rectilinear instances with coordinates scaled by 108 .

Instance
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca

4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4

11
11
11
11
11
12
12
12
12
12
13
13
13
13
13
14
14
14
14
14
15
15
15
15
15
16
16
16
16

01
02
03
04
05
01
02
03
04
05
01
02
03
04
05
01
02
03
04
05
01
02
03
04
05
01
02
03
04

|V |

|E|

|R|

Opt

Time [s]

14641
14641
14641
14641
14641
20736
20736
20736
20736
20736
28561
28561
28561
28561
28561
38416
38416
38416
38416
38416
50625
50625
50625
50625
50625
65536
65536
65536
65536

53240
53240
53240
53240
53240
76032
76032
76032
76032
76032
105456
105456
105456
105456
105456
142688
142688
142688
142688
142688
189000
189000
189000
189000
189000
245760
245760
245760
245760

11
11
11
11
11
12
12
12
12
12
13
13
13
13
13
14
14
14
14
14
15
15
15
15
15
16
16
16
16

627022001
636772154
607879790
638743359
545419447
641297479
619890840
618169838
573580734
690707456
668457902
732093506
667816953
618023300
816676045
678015050
770189931
774041179
753394327
668149161
867047412
747749078
797161324
682701539
816563142
877600183
840957543
769487137
883810994

0.425
0.223
1.779
1.166
1.883
0.350
1.143
1.152
0.791
0.907
1.776
5.151
1.369
1.465
9.274
1.967
32.560
7.656
15.256
6.908
3.505
2.624
41.344
9.475
5.407
53.440
11.185
7.469
40.603

56

|V |

Instance

|E|

|R|

Opt

carioca 4 16 05
65536
245760
16
844364805
carioca 4 17 01
83521
314432
17
778812798
83521
314432
17
885687619
carioca 4 17 02
carioca 4 17 03
83521
314432
17
866496021
83521
314432
17
961783573
carioca 4 17 04
carioca 4 17 05
83521
314432
17
926268906
carioca 4 18 01
104976
396576
18
951149709
104976
396576
18
842404966
carioca 4 18 02
carioca 4 18 03
104976
396576
18
848447422
carioca 4 18 04
104976
396576
18
956109307
carioca 4 18 05
104976
396576
18
893733310
130321
493848
19
917950857
carioca 4 19 01
carioca 4 19 02
130321
493848
19
825014078
carioca 4 19 03
130321
493848
19
945521812
carioca 4 19 04
130321
493848
19
912019383
carioca 4 19 05
130321
493848
19
963415391
160000
608000
20
889180827
carioca 4 20 01
carioca 4 20 02
160000
608000
20
822698792
carioca 4 20 03
160000
608000
20
884633836
carioca 4 20 04
160000
608000
20
948878450
carioca 4 20 05
160000
608000
20
984006649
Table 47: Results on the testset CARIOCA. Type: Random
rectilinear instances with coordinates scaled by 108 .

Instance
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5

11
11
11
11
11
12
12
12
12
12
13
13
13
13
13
14
14
14
14
14

01
02
03
04
05
01
02
03
04
05
01
02
03
04
05
01
02
03
04
05

Time [s]
26.792
46.322
96.926
345.275
22.303
107.808
99.353
98.723
1431.374
212.732
143.342
186.383
49.409
25.660
160.591
1625.465
82.724
101.107
125.995
2618.045
82.545
4-d

|V |

|E|

|R|

Opt

Time [s]

161051
161051
161051
161051
161051
248832
248832
248832
248832
248832
371293
371293
371293
371293
371293
537824
537824
537824
537824
537824

732050
732050
732050
732050
732050
1140480
1140480
1140480
1140480
1140480
1713660
1713660
1713660
1713660
1713660
2497040
2497040
2497040
2497040
2497040

11
11
11
11
11
12
12
12
12
12
13
13
13
13
13
14
14
14
14
14

925163690
844673618
867510918
906103201
795198510
953491398
985601088
844385082
879014839
815604529
881473517
873559091
1005775838
922258018
879174698
1080307930
1082279116
931463937
1037634219
1072793454

34.547
13.019
6.297
14.043
30.521
59.408
102.106
57.499
93.151
15.595
132.662
177.287
184.838
237.882
46.431
1038.209
150.913
284.221
821.468
1224.013

57

|V |

Instance
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca
carioca

|E|

|R|

Opt

Time [s]

5 15 01
759375
3543750
15
1011895745
1046.361
5 15 02
759375
3543750
15
1067623193
888.808
5 15 03
759375
3543750
15
1093631593
1258.172
5 15 04
759375
3543750
15
890715927
66.472
5 15 05
759375
3543750
15
1112392828
638.515
5 16 01
1048576
4915200
16
1140155635
3259.377
5 16 02
1048576
4915200
16
1114675222
2047.700
5 16 03
1048576
4915200
16
1097447396
464.254
5 16 04
1048576
4915200
16
–
timeout
5 16 05
1048576
4915200
16
1034250551
815.794
5 17 01
1419857
6681680
17
1084906998
803.613
5 17 02
1419857
6681680
17
–
memout
5 17 03
1419857
6681680
17
1030965254
845.502
5 17 04
1419857
6681680
17
1154984533
3195.596
5 17 05
1419857
6681680
17
–
timeout
5 18 01
1889568
8922960
18
–
memout
5 18 02
1889568
8922960
18
–
memout
5 18 03
1889568
8922960
18
1177091608
1081.015
5 18 04
1889568
8922960
18
–
timeout
5 18 05
1889568
8922960
18
–
memout
Table 48: Results on the testset CARIOCA. Type: Random 5-d
rectilinear instances with coordinates scaled by 108 . Instances with
19 and 20 terminals omitted.

Instance
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3

21
21
21
22
22
22
23
23
23
24
24
24
25
25
25
26
26
26
27
27

1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2

|V |

|E|

|R|

Opt

Time [s]

8820
8820
8820
10648
10648
10164
12167
12167
11638
13824
13248
13248
15625
15625
15625
17576
17576
16900
18252
19683

25179
25179
25179
30492
30492
29084
34914
34914
33373
39744
38064
38064
45000
45000
45000
50700
50700
48724
52676
56862

21
21
21
22
22
22
23
23
23
24
24
24
25
25
25
26
26
26
27
27

6217
6729
5738
6681
6797
6941
6195
6094
6398
6622
7136
7014
6928
7249
7504
8184
7172
7732
7504
7032

1.542
1.944
0.948
842.792
3.242
4.239
1.530
2.275
12.394
4.948
14.769
7.010
12.241
9.195
36.022
11.849
6.536
7.608
12.941
20.365

58

Instance
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn
bonn

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3

27
28
28
28
29
29
29
30
30
30
31
31
31
32
32
32
33
33
33
34
34
34
35
35
35
36
36
36
37
37
37
38
38
38
39
39
39
40
40
40
45
45
45
50
50
50

3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3

|V |

|E|

|R|

Opt

Time [s]

18954
21168
21168
21952
22736
23548
22736
26100
26100
26100
27869
28830
28830
31744
31744
31744
33792
35937
31744
37026
38148
37026
41650
40460
40460
42768
45360
44100
49284
47915
49284
53428
52022
52022
54834
54834
57798
64000
57798
59280
89100
89100
85140
110544
117600
112800

54729
61208
61208
63504
65800
68179
65800
75660
75660
75660
80848
83669
83669
92224
92224
92224
98240
104544
92224
107745
111044
107745
121345
117844
117844
124632
132264
128555
143819
139786
143819
156028
151885
151885
160171
160171
168909
187200
168909
173278
261315
261315
249613
324721
345598
331394

27
28
28
28
29
29
29
30
30
30
31
31
31
32
32
32
33
33
33
34
34
34
35
35
35
36
36
36
37
37
37
38
38
38
39
39
39
40
40
40
45
45
45
50
50
50

7688
8106
7774
7307
8231
8542
8053
8141
7897
8527
8664
8409
7583
9483
8828
8261
9588
9658
8902
9045
9664
9105
–
9372
9803
9353
9118
–
9379
9596
8768
–
9895
–
9757
–
–
9024
9633
10696
–
–
–
–
–
–

21.094
1795.931
384.240
22.964
248.490
37.717
23.270
181.245
25.814
63.451
16.913
328.879
45.304
59.047
2371.743
8.539
46.329
465.676
83.404
410.333
1822.087
959.836
timeout
513.599
528.187
2906.588
87.813
timeout
811.912
1602.806
113.704
timeout
317.967
timeout
581.362
timeout
timeout
25.440
710.092
1183.496
timeout
timeout
timeout
memout
timeout
memout

59

Instance

|V |

|E|

|R|

Opt

Time [s]

bonn 3 55 1
160380
472284
55
–
timeout
bonn 3 55 2
151470
445881
55
–
timeout
154548
455004
55
12138
6201.104
bonn 3 55 3
bonn 3 60 1
198417
585044
60
–
timeout
201898
595369
60
–
timeout
bonn 3 60 2
bonn 3 60 3
198476
585220
60
–
memout
Table 49: Results on the testset bonn-3d. Type: Random 3-d rectilinear instances. Coordinates were chosen uniformly at random
from {0, 1, . . . , 999}.

