Skip to main content
5 of 6
deleted 103 characters in body
Nandakumar R
  • 6k
  • 3
  • 7
  • 20

Are there variants of Euclidean Steiner Tree problem that are known to be in P?

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 or some conic or (in 3D) on a spherical surface.

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

Nandakumar R
  • 6k
  • 3
  • 7
  • 20