Open Problems

Of course, there are probably about a zillion open problems related to Steiner trees, but here are a few I've thought about.

• Full trees. Hwang's theorem allows us to construct an optimal rectilinear Steiner tree of a full set in linear time. I know of no other metric or type of graph in which computing the optimal Steiner tree of a full set is polynomial-time solvable but computing a general Steiner tree is NP-hard. Note that there isn't even a sufficiently strong analogue of Hwang's theorem for rectilinear Steiner trees in three dimensions.
• Multidimensional rectilinear Steiner ratio. What is the rectilinear Steiner ratio in arbitrary dimension d? It is at least 2-1/d, as the d-dimensional analogue of the "cross" has this ratio. It is obviously at most 2. It is generally believed that the lower bound is correct, but this hasn't been proven. Even an upper bound lower than 2 would be interesting.
• Rectilinear Steiner arborescence. These are Steiner-like trees on points in the (first quadrant of the) plane, in which every segment in the tree is directed left to right or bottom to top. It is unknown whether computing an RSA is NP-complete. (A good reference to start with is Rao, Sadayappan, Hwang, and Shor.) SOLVED! J.-D. Cho published a paper in which a purported polynomial-time algorithm is presented for the problem. I was notified, however, by both Adil Erzin and Andrew Kahng, that it turns out the network flow problem to which Cho reduced the RSA problem is, itself, NP-complete. SOLVED! Shi and Su, in a paper in the 2000 Symposium on Discrete Algorithms, have proven that the RSA problem is (as suspected) NP-complete. It's a very pretty proof, too!
• Line separators. Smith proves that there exists a separator of length O(sqrt(n)) in the Hanan grid graph that cuts an optimal rectilinear Steiner tree in at most O(sqrt(n)) places. On the other hand, Deneen, Shute, and Thomborson prove that with high probability, a horizontal or vertical line bisecting the terminal set is crossed at most O(sqrt(n)) times by some optimal RST. I conjecture that there always exists a horizontal or vertical line that separates the terminal set into two subsets, each of size at most pn for p<1, such that the line is crossed by some optimal RST at most O(sqrt(n)) times. A proof of this would lead to a more implementable version of Smith's exact algorithm (or a non-randomized version of Deneen, Shute, and Thomborson's). SOLVED! Warren Smith has come up with a counterexample consisting of a spiral of points such that every line that separates the points into two O(n)-sized subsets intersects the optimal RST O(n) times, disproving the conjecture. He has also proven a number of related results, including a slightly restricted version of the original conjecture. Details will appear here once Warren has written them up.
• Bounding the number of rectilinear full sets. The best known bound on the worst-case number of full sets on n terminals is O(n1.384ⁿ) [Fößmeier and Kaufmann]. However, empirically the number of full sets seems quite polynomial -- perhaps O(n log n) [Salowe and Warme]. These bounds might be narrowed from either side.