2026-07-20T05:27:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22839 2025-10-02T13:35:08Z ddc:004 open_access

Multivariate Exploration of Metric Dilation Banik, Aritra Fomin, Fedor V. Golovach, Petr A. Inamdar, Tanmay Jana, Satyabrata Saurabh, Saket Metric dilation geometric spanner fixed-parameter tractability 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 Γ. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aritra Banik and Fedor V. Fomin and Petr A. Golovach and Tanmay Inamdar and Satyabrata Jana and Saket Saurabh 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.14 urn:nbn:de:0030-drops-228395 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.14 eng https://creativecommons.org/licenses/by/4.0/legalcode