Skip to main content
1 of 6
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 points lie on a circle or some conic.

Nandakumar R
  • 6k
  • 3
  • 7
  • 20