1
$\begingroup$

Question: The Euclidean Steiner Tree problem (https://en.wikipedia.org/wiki/Steiner_tree_problem) is NP hard. Are there non-trivial (constrained) variants of this question that are known to have polynomial time solutions?

What one has in mind are situations like say, all input points lie on a circle, convex polygon or some conic or (in 3D) on a spherical surface.

Note: A similar question can be asked about the traveling salesman as well.

Improve this question
$\endgroup$
2
  • $\begingroup$ FWIW, the metric traveling salesman problem is NP-complete, which may address the implicit question in your "Note". $\endgroup$
    – Bill Bradley
    Commented Jun 21, 2023 at 13:45
  • $\begingroup$ Thanks. However, some constrained (and still nontrivial) versions of the tsp could be in P. And I guess TSP has received a lot more attention than the Steiner tree. $\endgroup$
    – Nandakumar R
    Commented Jun 21, 2023 at 18:14

2 Answers 2

Reset to default
1
$\begingroup$

A new paper was just posted to the arXiv that develops a polynomial algorithm for some cases of "2-concentric parallel regular polygons." Here are Figs. 1(a) and 5:

Dhar, Anubhav, Soumita Hait, and Sudeshna Kolay. "Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets." arXiv:2307.00254 (2023).

They also obtain results for "$f(n)$-almost convex sets."

Improve this answer
$\endgroup$
2
$\begingroup$

Du, D. Z., F. K. Hwang, and S. C. Chao. “Steiner Minimal Tree for Points on a Circle.” Proceedings of the American Mathematical Society 95, no. 4 (1985): 613–18. https://doi.org/10.2307/2045853 write,

We show that the Steiner minimal tree for a set of points on a circle is the shortest path connecting them if at most one distance between two consecutive points is "large".

The definition of "large" is a little complicated – see the paper for details.

Also, Du, Hwang, and Weng, Steiner minimal trees for regular polygons, Discrete Comput. Geom. 2:65-84 (1987), give references to papers on various other special cases of the Euclidean Steiner problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the reference. As far as I could make out from it, although some results have proved (or conjecture) that under rather strong conditions, the steiner tree is the minimum spanning tree itself, not much is known about point distributions where one needs to actually use steiner points (iow, the steiner tree is not the spanning tree) and still achieve P complexity with some other algorithm. The full set of circumstances under which the min spanning tree gives the steiner tree also seems unknown. $\endgroup$
    – Nandakumar R
    Commented Jun 22, 2023 at 17:19
  • $\begingroup$ Note that the references I found are from over 35 years ago. It's quite possible more is known by now. It might be worthwhile to try to find more recent papers that cite the ones I found. $\endgroup$
    – Gerry Myerson
    Commented Jun 22, 2023 at 22:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .