Parameterized low-distortion embeddings: graph metrics into lines and trees

We revisit the issue of low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective. Let M = M(G) be the shortest path metric of an edge weighted graph G = (V,E) on n vertices. We describe algorithms for the problem of finding a low distortion non-contracting embedding of M into line and tree metrics. ; We give an O(nd⁴(2d + 1)²d) time algorithm that for an unweighted graph metric Mand integer d either constructs an embedding of M into the line with distortion at most d, or concludes that no such embedding exists. We find the result surprising, because the considered problem bears a strong resemblance to the notoriously hard Bandwidth Minimization problem which does not admit any FPT algorithm unless an unlikely collapse of parameterized complexity classes occurs. The running time of our algorithm is a significant improvement over the best previous algorithm of Bădoiu et al. [SODA 2005] that has a running time of O(n⁴d⁺²dO⁽¹⁾). ; We show that our algorithm can also be applied to construct small distortion embeddings of weighted graph metrics. The running time of our algorithm is O(n(dW)⁴(2d+1)²dW) where W is the largest edge weight of the input graph. To complement this result, we show that the exponential dependence on the maximum edge weight is unavoidable. In particular, we show that deciding whether a weighted graph metric M(G) with maximum weight W < |V (G)| can be embedded into the line with distortion at most d is NP-Complete for every fixed rational d ≥ 2. This rules out any possibility of an algorithm with running time O((nW)h⁽d⁾) where h is a function of d alone. ; We generalize the result on embedding into the line by proving that for any tree T with maximum degree ∆, embedding of M into a shortest path metric of T is FPT, parameterized by (∆, d). This result can also be viewed as a generalization (albeit with a worse running time) of the previous FPT algorithm due to Kenyon, Rabani and Sinclair [STOC 2004] that was limited to the situation where |G| = |T|.