Special Cases Only two required vertices,
just a shortest path. Every vertex is required,
just a minimum spanning tree. The general problem is NP-complete.
Useless Edges Would I ever use an edge of weight 10 (an expensive edge)? 10 10 10 1 1 1 We must use Steiner vertices in order to construct a good solution, because edges connecting required vertices could be very expensive (or even don’t exist). The purpose of using such an edge is to connect two required vertices,
but we can always use a path of length 2 (which passes through
the Steiner vertices and has a total cost of 2) for the same purpose! 2 2 2
Metric Closure 10 10 10 1 1 1 2 2 2 In general, we can always replace the cost of an edge
by the cost of a cheapest (shortest) path. We call the resulting graph the metric closure of the original graph.
Metric Closure Claim. In the metric closure, the edge costs satisfy triangle inequalities. c(uv) c(vw) c(uw) u w v (Proof by contradiction:)
Suppose c(vw) < c(uv) + c(uw). There is a path P(uv) between u and v with cost c(uv), and a path P(uw) between u and w with cost c(uw).
The union of P(uv) and P(uw) contains a path P* from v to w with cost at most c(uv) + c(uw). This contradicts that c(vw) represents the cost of a shortest path from v to w (since P* is shorter). Note that the metric
closure is a complete graph.
Metric Closure Lemma The cost of a minimum Steiner tree in a graph G =
the cost of a minimum Steiner tree in its metric closure. First The cost of a minimum Steiner tree in a graph G ≥
the cost of a minimum Steiner tree in its metric closure. in G Just take the same tree
in the metric closure (Proof): Let T be a minimum Steiner tree in G. For each edge uv,
The cost of uv in the metric closure is at most the cost of uv in G.
So, the same T in the metric closure is no more expensive.
Metric Closure Next The cost of a minimum Steiner tree in a graph G ≤
the cost of a minimum Steiner tree in its metric closure. in metric closure take the union of the shortest paths (Proof): Let T be a minimum Steiner tree in the metric closure. Consider the union U of the shortest paths in the original graph G. The union U has cost at most the cost of T. Clearly, U connects all the required vertices. So, U contains a Steiner tree T*. Hence, T* has cost at most the cost of T. in G
Metric Steiner Tree Problem:
Given a complete graph with edge costs satisfying triangle inequalities,
find a minimum Steiner tree (which connect all the required vertices). Metric Steiner Tree Lemma The cost of a minimum Steiner tree in a graph G =
the cost of a minimum Steiner tree in its metric closure. Without loss of generality, we can consider the metric TSP problem. Claim. In the metric closure, the edge costs satisfy triangle inequalities.
Metric Steiner Tree 10 10 10 1 1 1 2 2 2 A Steiner tree connects all the required vertices. Can we just find a minimum spanning tree
connecting all the required vertices? In other words, forget about all Steiner vertices! How bad can it be?
Spanning Tree and Steiner Tree a b c d e MST ≤ a + b + b + c + c + d + d + e ≤ 2a + 2b + 2c + 2d + 2e = 2(a +b + c + d + e) Cost of a minimum Steiner tree MST ≤ 2OPT
Spanning Tree and Steiner Tree How to formalize the idea? Let the cost of this Steiner tree be OPT.
Key idea: double all the edges and find an Eulerian tour. This graph has cost 2OPT. How to formalize the idea? Spanning Tree and Steiner Tree
Key idea: double all the edges and find an Eulerian tour. This graph has cost 2OPT. Spanning Tree and Steiner Tree How to formalize the idea?
Strategy: shortcut this Eulerian tour. Spanning Tree and Steiner Tree
By triangle inequalites, the shortcut tour is not longer than the Eulerian tour. So, the cost of MST ≤ the cost of Eulerian graph ≤ 2OPT. Spanning Tree and Steiner Tree
A 2-Approximation for Metric Steiner Tree (Metric Steiner Tree – Factor 2)
Compute the metric closure G* of G.
Find a minimum spanning tree T* of G*.
Construct the union U of the shortest paths in G which
correspond to edges in T*.
4. Output the Steiner tree T contained in U. Analysis: cost(T) ≤ cost(U) (because T is contained in U)
cost(U) ≤ cost(T*) (because G* is the metric closure of G)
cost(T*) ≤ 2OPT (because of triangle inequalities, shortcutting)
So, cost(T) ≤ 2OPT
Better approximation? (Robin Zelikovsky)
There is a 1.55 approximation algorithm for minimum Steiner tree. Just for fun 1: Show that the 2-approximation algorithm is equivalent to the following algorithm:
Find a cheapest path that connects two required vertices which are not yet connected.
- Repeat until all required vertices are connected. Just for fun 2: Design a polynomial time algorithm to find a
minimum Steiner tree for k required vertices, when k is fixed.
Comments