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).
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^{n})
[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.