Multivariate Exploration of Metric Dilation

Let G be a weighted graph embedded in a metric space ( M , d M ). The vertices of G correspond to the points in M , with the weight of each edge uv being the distance d M ( u , v ) between their respective points in M . The dilation (or stretch) of G is defined as the minimum factor t such that, for any pair of vertices u , v , the distance between u and v —represented by the weight of a shortest u , v -path—is at most t · d M ( u , v ). We study Dilation t -Augmentation , where the objective is, given a metric M , a graph G , and numerical values k and t , to determine whether G can be transformed into a graph with dilation t by adding at most k edges. Our primary focus is on the scenario where the metric M is the shortest path metric of an unweighted graph Γ . Even in this specific case, Dilation t -Augmentation remains computationally challenging. In particular, the problem is W[2] -hard parameterized by k when Γ is a complete graph, already for t = 2. Our main contribution lies in providing new insights into the impact of combinations of various parameters on the computational complexity of the problem. We establish the following. • The parameterized dichotomy of the problem with respect to dilation t , when the graph G is sparse: Parameterized by k , the problem is FPT for graphs excluding a biclique K d , d as a subgraph for t ≤ 2 and the problem is W[1] -hard for t ≥ 3 even if G is a forest consisting of disjoint stars. • The problem is FPT parameterized by the combined parameter k + t + Δ , where Δ is the maximum degree of the graph G or Γ .