Distortion Is Fixed Parameter Tractable

Abstract

We study 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, with the vertex set V(G) and the edge set E(G), on n vertices. We give the first fixed parameter tractable algorithm that for an unweighted graph metric M and integer d either constructs an embedding of M into the line with distortion at most d, or concludes that no such embedding exists. Our algorithm requires O(nd⁴(2d+1)^2d) time which is a significant improvement over the best previous algorithm of Bădoiu et al. that runs in time O(n^4d+2d^O(1)). We find it surprising that this problem turns out to be fixed parameter tractable, because of its apparent similarity to the notoriously hard Bandwidth Minimization problem.