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$
    – user114966
    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
1
$\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$
0
$\begingroup$

There is actually an even faster implementation of the metric closure heuristic than that of Wu et. al. See the paper "A faster approximation algorithm for the Steiner problem in graphs" by Kurt Mehlhorn.

Improve this answer
$\endgroup$
7
  • $\begingroup$ That's confusing! "A faster approximation algorithm for the Steiner problem in graphs" is also the exact title of the article by Wu, Widmayer and Wong (1986). Acta Informatica 23(2), 223-229, doi:10.1007/bf00289500. But indeed the same title is also used by Kurt Mehlhorn (1988), Information Processing Letters 27, 125-128. $\endgroup$
    – Thomas
    Nov 7 '21 at 12:03
  • $\begingroup$ Just read the article by Mehlhorn. Good stuff! I wonder if it gives different output from Wu et al., which seems a bit more "greedy" even though the upper bound of 2 - 2/t is the same... I'll need to sleep on this. $\endgroup$
    – Thomas
    Nov 7 '21 at 12:23
  • $\begingroup$ ...another remark: if you are interested in implementing the algorithm, I would recommend: "A note on “A faster approximation algorithm for the Steiner problem in graphs” by R. Floren, and also the PhD thesis of Tobias Polzin ("Algorithms for the Steiner problem in networks"), who was one of Mehlhorn's students. He discusses the practical performance of the shortest-path heuristic (with several start points) and the metric closure heuristic. $\endgroup$
    – Dan
    Nov 8 '21 at 8:56
  • $\begingroup$ Thank you for the pointers! Those are definitely going to come in handy! $\endgroup$
    – Thomas
    Nov 8 '21 at 12:38
  • $\begingroup$ One last remark: If you want to find minimum Steiner trees (so best possible ones), you can use scipjack.zib.de $\endgroup$
    – Dan
    Nov 9 '21 at 10:40

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.