Return to Question

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.

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.

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. And I have no answer for the seemingly simple case of the input points all lying on two parallel lines.

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

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.

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

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

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. And I have no answer for the seemingly simple case of the input points all lying on two parallel lines.

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