TY - JOUR

T1 - Distortion is Fixed Parameter Tractable

AU - Fellows, Michael

AU - Fomin, Fedor

AU - Lokshtanov, Daniel

AU - Losievskaja, Elena

AU - Rosamond, Frances

AU - Saurabh, Saket

PY - 2013

Y1 - 2013

N2 - 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(nd4(2d + 1)2d) time which is a significant improvement over the best previous algorithm that runs in time O(n4d+2dO(1)). Because of its apparent similarity to the notoriously hard BANDWIDTH MINIMIZATION problem, we find it surprising that this problem turns out to be fixed parameter tractable. We extend our results on embedding unweighted graph metric into the line in two ways. First, we give an algorithm to construct small-distortion embeddings of weighted graph metrics. The running time of our algorithm is O(n(dW)4(2d + 1)2dW), 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. Second, we consider more general host metrics for which analogous results hold. In particular, we prove that for any tree T with maximum degree ?, embedding M into a shortest path metric of T is fixed parameter tractable, parameterized by (Δ, d).

AB - 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(nd4(2d + 1)2d) time which is a significant improvement over the best previous algorithm that runs in time O(n4d+2dO(1)). Because of its apparent similarity to the notoriously hard BANDWIDTH MINIMIZATION problem, we find it surprising that this problem turns out to be fixed parameter tractable. We extend our results on embedding unweighted graph metric into the line in two ways. First, we give an algorithm to construct small-distortion embeddings of weighted graph metrics. The running time of our algorithm is O(n(dW)4(2d + 1)2dW), 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. Second, we consider more general host metrics for which analogous results hold. In particular, we prove that for any tree T with maximum degree ?, embedding M into a shortest path metric of T is fixed parameter tractable, parameterized by (Δ, d).

KW - Bandwidth minimization problem

KW - Edge-weighted graph

KW - Embedding

KW - Exponential dependence

KW - Fixed-parameter tractable algorithms

KW - Parameterized algorithm

KW - Parameterized complexity

KW - Tree

KW - Algorithms

KW - Distortion (waves)

KW - Graphic methods

KW - Graph theory

U2 - 10.1145/2489789

DO - 10.1145/2489789

M3 - Article

SN - 1942-3454

VL - 5

SP - 16:1-16:20

JO - ACM Transactions on Computation Theory

JF - ACM Transactions on Computation Theory

IS - 4

M1 - 16

ER -