Steiner points in tree metrics don't (really) help

Consider an edge-weighted tree T = (V, E, w : E →tl; R+), in which a subset R of the nodes (called the required nodes) are colored red and the remaining nodes in S = V\R are colored black (and called the Steiner nodes). The shortest-path distance according to the edge-weights defines a metric dT on the vertex set V. We now ask the following question: Is it possible to define another weighted tree T* = (R, E*, w* : E* →tl; R+), this time on just the red vertices so that the shortest-path metric dT* induced by T* on the vertices in R is “close” to the metric dT restricted to the red vertices? I.e., does there exist a weighted tree T* = (R, E*, c*) and a (small) constant &agr; such that dT(u, v) ≤ dT* (u, v) ≤ &agr; dT(u, v) for any two red vertices u, v ∈ R? We answer this question in the affirmative, and give a linear time algorithm to obtain a tree T* with &agr; ≤ 8. We also give two applications of this result: an upper bound, in which we show that emulating multicasts using unicasts can be almost as good as general multicasts for certain performance measures; and a lower bound, in which we give a simple combinatorial proof of the fact that the metric generated by a graph of girthg must suffer a distortion of at least &OHgr;(g) when approximated by a tree.