Name
Abstract | ||
|---|---|---|
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 perspec- tive. 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(nd4(2d + 1)2d) time 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. 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ùadoiu et al. (SODA 2005) that has a running time of O(n4d+2dO(1)). • 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)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. • 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 |. |
Year | Venue | Keywords |
|---|---|---|
2008 | Clinical Orthopaedics and Related Research | tree,metric space,parameterized complexity,maximum degree,algorithms,data structure,computational complexity,metric spaces,shortest path |
Field | DocType | Volume |
Integer,Discrete mathematics,Combinatorics,Parameterized complexity,Embedding,Vertex (geometry),Shortest path problem,Graph embedding,Degree (graph theory),Metric space,Mathematics | Journal | abs/0804.3 |
Citations | PageRank | References |
5 | 0.78 | 12 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael R. Fellows | 1 | 4138 | 319.37 |
| Fedor V. Fomin | 2 | 3139 | 192.21 |
| Daniel Lokshtanov | 3 | 1438 | 110.05 |
| Elena Losievskaja | 4 | 21 | 2.59 |
| Frances A. Rosamond | 5 | 97 | 7.77 |
| Saket Saurabh | 6 | 2023 | 179.50 |