An exact algorithm for minimum distortion embedding

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5 n + o ( n ). This is the first algorithm breaking the trivial n! -barrier.

Authors

• Fedor V. Fomin
• Daniel Lokshtanov
• Saket Saurabh

Keywords

• Exact algorithm
• Metric embedding
• Distortion