Zero Skew Tree Problem

• INSTANCE: Metric space $(M,d)$ , set of sinks $S \subseteq M$ , edge costs $cost: E \rightarrow\mathbb{R}^+$ .
• SOLUTION: A stretched tree $T=(V_T, E_T, \pi, c)$ consisting of an arborescence $(V_T,E_T)$ , a mapping $\pi: V_T \rightarrow M$ such that $\pi$ is a one-to-one mapping between the leaves of $T$ and $S$ and a cost function $c\colon E_T\to \mathbb{R}_+$ such that for every edge $(u,v)$ of $T$ , $c(u,v)\geq d(\pi(u),\pi(v))$ and furthermore, for each pair $P,P'$ of root-to-leaf paths in $T$ , $c(P)=c(P')$ .
• COST FUNCTION: $\sum_{(u,v)\in E_T}c(u,v)$
• OBJECTIVE: Minimize.
• Approx.: Approximable within approximation ratio 4 when the root is not fixed as a part of the instance [110]. Approximable within approximation ratio $2e$ if the root is fixed [28].
• Hardness: NP-hard [28].
• Comment: The complexity of the rectilinear zero skew tree problem is not known. For a fixed tree topology, the problem can be solved in linear time by using the Deferred-Merge Embedding (DME) [17], [26], [43].