¹  Ñëàéä  Òåêñò 
1 

Steiner treesAlgorithms and Networks 
2 

TodaySteiner trees: what and why? NPcompleteness Approximation algorithms Preprocessing 2 Steiner Trees 
3 

Steiner treeGiven: connected undirected graph G=(V,E), length for each edge l(e) ? N, set of vertices N: terminals Question: find a subtree T of G, such that each vertex of N is on T and the total length of T is as small as possible Steiner tree spanning N 3 Steiner Trees 
4 

VariantsPoints in the plane Vertex weights Directed graphs 4 Steiner Trees 
5 

ApplicationsWire routing of VLSI Customer’s bill for renting communication networks in the US Other network design and facility location problems 5 Steiner Trees 
6 

Special casesN = 1: trivial N = 2: shortest path N = V: minimum spanning tree 6 Steiner Trees 
7 

NPcompletenessDecision version is NPcomplete Vertex cover = terminal 7 Steiner Trees 
8 

Proof of reductionMembership of ST in NP: trivial Hardness: take instance G=(V,E), k of Vertex Cover Build G’ by subdividing each edge Set N = set of new vertices All edges length 1 G’ has Steiner Tree with E+k – 1 edges, if and only if G has vertex cover with k vertices 8 Steiner Trees 
9 

Approximation algorithmsSeveral different algorithms that guarantee ratio 2 (or, more precise: 2 – 2/n). Shortest paths heuristic Ration 2 – 2/n (no proof here) Bases on Prim’s minimum spanning tree algorithm 9 Steiner Trees 
10 

Shortest paths heuristicStart with a subtree T consisting of one terminal While T does not span all terminals Select a terminal x not in T that is closest to a vertex in T. Add to T the shortest path that connects x with T. 10 Steiner Trees 
11 

Improving the shortest paths heuristicTake the solution T from the heuristic Build the subgraph of G, induced by the vertices in T Compute a minimum spanning tree of this subgraph Repeat Delete nonterminals of degree 1 from this spanning tree Until there are no such nonterminals 11 Steiner Trees 
12 

Distance networksDistance network of G=(V,E) (induced by X) Take complete graph with vertex set X Cost of edge {v,w} in distance network is length shortest path from v to w in G. For set of terminals N, the minimum cost of a Steiner tree in G equals the minimum cost of a Steiner tree in the distance network of G (induced by V). 12 Steiner Trees 
13 

Distance network heuristicConstruct the distance network DG(N) (induced by N) Determine a minimum spanning tree of DG(N) Replace each edge in the minimum spanning tree by a corresponding shortest path. Let TD be the corresponding subgraph of G It can be done such that TD is a tree Make the subgraph of G induced by the vertices in TD Compute a minimum spanning tree of this subgraph Remove nonterminals of degree 1 from this spanning tree, until there are no such nonterminals. 13 Steiner Trees 
14 

Distance network heuristic has ratio 2Look at optimal Steiner tree T* Take closed walk L around T* visiting each edge twice See this as a collection of paths between successive terminals Delete the longest of these, and we get a walk L’; cost of L’ ? cost(T*) * (2 – 2/r) cost(TD) ? cost(L’). L’ is a spanning tree in DG(N) Final network has cost at most cost(TD). 14 Steiner Trees 
15 

Example where bound is met2e 2e 2e 1 1 = terminal 1 1 2e 2e 1 1 1 1 2e 2e 2e 15 Steiner Trees 
16 

Upgrading heuristicW = ? ; w = maxint; D = DG(N) repeat Identify set of three terminals A={a,b,c} such that w= cost(TD(N)) – cost(TD’(N’)) – cost(TG(A)) is as large as possible D’ (N’) is obtained from D (N) by contracting A to one vertex TD(N) denotes min spanning tree of D TG(A) denotes min steiner tree in G with terminals A if (w = = 0) then apply distance network heuristic with terminal set W ? N; stop else add to W the nonterminal of degree 3 in TG(A); D=D’ 16 Steiner Trees 
17 

On upgrading heuristicCorrectness: when no nonterminal vertex of degree 3 in TG(A), then w=0 TD(N) can be constructed using edges of the other two Ratio: 11/7 Other method: + 1.55 (Robins, Zelikowsky, 2000) 17 Steiner Trees 
18 

Small number of terminalsSuppose N= r is small. Compute distance network DG(V) There is a minimum cost Steiner tree in DG(V) that contains at most r – 2 nonterminals. Any Steiner tree has one that is not longer without nonterminal vertices of degree 1 and 2 A tree with r leaves and internal vertices of degree at least 3 has at most r – 2 internal vertices Polynomial time algorithm for Steiner tree when we have O(1) terminals. 18 Steiner Trees 
19 

Solving O(1) terminalsPolynomial time algorithm for Steiner tree when we have O(1) terminals: Enumerate all sets W of at most r – 2 nonterminals For each W, find a minimum spanning tree in the distance network of N ? W Take the best over all these solutions Takes polynomial time for fixed r. Heuristics to do this more clever? 19 Steiner Trees 
20 

Simple preprocessingSteiner tree can be solved separately on each biconnected component Non terminals of degree at most 2: Reduce graph: Delete nonterminal of degree 1 Connect neighbors of nonterminals of degree 2 Edge length is sum of lengths of 2 edges Long edges can be deleted If l(v,w) > d(v,w) then delete edge {v,w}. 20 Steiner Trees 
21 

Bottleneck Steiner distancePath between v and w can be seen as number of successive elementary paths Pieces ending/starting at v, w or terminal Steiner distance of path: length of largest elementary path Bottleneck Steiner distance: minimum Steiner distance over all paths between v and w Can be computed with modification of shortest paths algorithm 21 Steiner Trees 
22 

Reducing nonterminalsConsider nonterminal z. Consider network B(z), with vertex set N[z] and lengths the bottleneck Steiner distances. Write B(z)[W] for subnetwork of B(z) induced by W. Lemma. If for every subset W of N(z) of size at least 3, the cost of the minimum spanning tree of B(z)[W] is at most the cost of the edges {z,w} over all w ? W, then z has degree at most 2 in at least one minimum cost Steiner Tree 22 Steiner Trees 
23 

Use of lemmaRemove z For pairs of neighbors v, w of z If {v,w} ? E, set length of edge to minimum of cost(v,w), cost(v,z)+cost(z,w) Otherwise, add edge {v,w} with cost cost(v,z)+cost(z,w) 23 Steiner Trees 
24 

Long edgesIf d(v,w) < cost(v,w), then edge {v,w} can be removed. If d(v,w) = cost(v,w), and there is a shortest path not via edge {v,w}, then edge can be removed. 24 Steiner Trees 
25 

Paths with one terminalSuppose {v,w} is an edge, and there is a terminal z with cost(v,w) > max(d(v,z),d(w,z)) then {v,w} can be removed. A Steiner tree with {v,w} can be improved: how can we repair a Steiner tree – {v,w}? 25 Steiner Trees 
26 

PTmtest (paths with many terminals)Let b(v,w) the bottleneck Steiner distance from v to w. If cost(v,w) > b(v,w) then edge {v,w} can be removed. Proof. Consider Steiner tree T1 with such edge {v,w}. Look at T1 – {v,w}. Splits in two trees T2 and T3. Consider bottleneck shortest path from v to w. Take elementary path P0 with one edge in T2 and T3. Length of P0 at most b(v,w). T1 – {v,w}+ P0 has length less than T1 and spans all terminals Take subgraph of P0 that spans all terminals and is a tree 26 Steiner Trees 
27 

Polynomial solvable casesWhen bounded treewidth E.g., for series parallel graphs Compute for part with terminals s and t Minimum cost subtree in part spanning s and t Minimum cost subtree in part spanning s, but not t Minimum cost subtree in part spanning t, but not s Minimum cost subtree in part spanning neither s and t Minimum cost of two subtrees, one spanning s and one spanning t Strongly chordal graphs with unit costs 27 Steiner Trees 
«Algorithms and Networks» 