3
$\begingroup$

I keep encountering citations of the following article:

Takahashi and A. Matsuyama, “An approximate solution for the Steiner problem in graphs,” Math. Japonica, vol. 24, no. 6, pp. 573–577, 1980

For example, Yahui Sun refers to it here as "a widely-used Steiner tree approximation algorithm".

But... what is the actual algorithm?

The website of Mathematica Japonica only goes back to 1994, and I can't find the article anywhere else either.

Wikipedia contains this description, but without a citation:

The general graph Steiner tree problem can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of the graph induced by the terminal vertices. The metric closure of a graph G is the complete graph in which each edge is weighted by the shortest path distance between the nodes in G. This algorithm produces a tree whose weight is within a 2 − 2/t factor of the weight of the optimal Steiner tree where t is the number of leaves in the optimal Steiner tree; this can be proven by considering a traveling salesperson tour on the optimal Steiner tree. The approximate solution is computable in polynomial time by first solving the all-pairs shortest paths problem to compute the metric closure, then by solving the minimum spanning tree problem.

Is this the algorithm that Sun and others refer to?

Improve this question
$\endgroup$
2
  • $\begingroup$ I've found this, hope it helps $\endgroup$ – Dmitry Dec 7 '20 at 20:42
  • $\begingroup$ @Dmitry It sure helps, thanks a ton! However, it also adds to the confusion: in the introduction (last paragraph on the first page), Takahashi and Matsuyama seem to refer to the algorithm sketched on Wikipedia, citing Gilbert and Pollak, 1968, but with a factor of 2. The actual algorithm by Takahashi and Matsuyama does achieve the 2 - 2/t bound, but it's a different algorithm that doesn't rely on the metric closure. $\endgroup$ – Thomas Dec 8 '20 at 11:22
0
$\begingroup$

Let G = (V, E) be our graph, and S be the set of vertices that must be in the Steiner tree. Let t be the number of leaves in the optimal Steiner tree.

It seems that Takahashi and Matsuyama's algorithm (1980) is indeed the "shortest path heuristic" since it actually uses shortest-path searches. Starting from a single vertex, it simply grows the tree T by finding the closest vertex v in S \ T that hasn't been added yet, and adding the shortest path from T to v until all vertices have been added, similar to Prim's algorithm for the minimum spanning tree.

The algorithm I cited from Wikipedia, based on the metric closure, is due to Kou, Markowsky and Berman (1981), and boils down to: compute the metric closure, find the minimum spanning tree of the metric closure, turn this back into a subgraph (not necessarily a tree) of the original graph, find the minimum spanning tree of that subgraph, then repeatedly remove leaves that are not in S.

I didn't read Gilbert and Pollak (1968) fully (it's mostly about the geometry of Steiner trees in the plane). I presume they did something similar to Kou et al., but without the final pruning step, which might explain why they only got within a factor 2 from the optimal cost, rather than the 2 - 2/t by Kou et al..

I made some edits to Wikipedia to record all this, and added a summary of an algorithm by Wu, Widmayer and Wong (1986), which is more efficient and also easier to implement than both of the above, while retaining the same optimality bound.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.