FPT Algorithms for Embedding into Low-Complexity Graphic Metrics
Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra · ACM Transactions on Computation Theory · 2019
Given metric spaces ( X , D X ) and ( Y , D Y ), an embedding F : X → Y is an injective mapping from X to Y . Expansion e F and contraction c F of an embedding F : X → Y are defined as e F = max x ; 1 , x 2 (≠ x 1 ) ∈ X D Y ( F ( x 1 ), F ( x 2 ))/ D X ( x 1 , x 2 ) and c F = max x 1 , x 2 (≠ x 1 ) ∈ X D X ( x 1 , x 2 )/ D Y ( F ( x 1 ), F ( x 2 )), respectively, and distortion d F is defined as d F = e F ⋅ c F . Observe that d F ≥ 1. An embedding F : X → Y is noncontracting if c F ≤ 1. When d =1, then F is isometry . The M etric E mbedding problem takes as input two metric spaces ( X , D X ) and ( Y , D Y ), and a positive integer d . The objective is to determine whether there is an embedding F : X → Y such that d F ≤ d . Such an embedding is called a distortion d embedding . The bijective M etric E mbedding problem is a special case of the M etric E mbedding problem where ∣ X ∣ = ∣ Y ∣. In parameterized complexity, the M etric E mbedding problem, in full generality, is known to be W-hard and, therefore, not expected to have an FPT algorithm. In this article, we consider the G en -G raph M etric E mbedding problem, where the two metric spaces are graph metrics. We explore the extent of tractability of the problem in the parameterized complexity setting. We determine whether an unweighted graph metric ( G , D G ) can be embedded, or bijectively embedded, into another unweighted graph metric ( H , D H ), where the graph H has low structural complexity. For example, H is a cycle, or H has bounded treewidth or bounded connected treewidth. The parameters for the algorithms are chosen from the upper bound d on distortion, bound Δ on the maximum degree of H , treewidth α of H , and connected treewidth α c of H . Our general approach to these problems can be summarized as trying to understand the behavior of the shortest paths in G under a low-distortion embedding into H , and the structural relation the mapping of these paths has to shortest paths in H .