EUVIMEDEUVIMED entdecken
Crossref

Multivariate Exploration of Metric Dilation

Aritra Banik, Fedor Fomin, Petr Golovach, Tanmay Inamdar, Satyabrata Jana, Saket Saurabh

ACM Transactions on Computation Theory · 21.07.2026

DOI: 10.1145/3833215 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, online erschienen am 21.07.2026. Verfasst von Aritra Banik und 5 weiteren Autor:innen. Die Arbeit nennt 20 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 Γ .

Zitieren

APA

Banik, A., Fomin, F., Golovach, P., Inamdar, T., Jana, S., & Saurabh, S. (2026). Multivariate Exploration of Metric Dilation. ACM Transactions on Computation Theory. https://doi.org/10.1145/3833215

Vancouver

Banik A, Fomin F, Golovach P, Inamdar T, Jana S, Saurabh S. Multivariate Exploration of Metric Dilation. ACM Transactions on Computation Theory. 2026. doi:10.1145/3833215

BibTeX
@article{Banik2026,
  author = {Banik, Aritra and Fomin, Fedor and Golovach, Petr and Inamdar, Tanmay and Jana, Satyabrata and Saurabh, Saket},
  title = {Multivariate Exploration of Metric Dilation},
  journal = {ACM Transactions on Computation Theory},
  year = {2026},
  doi = {10.1145/3833215}
}
Kostenlos starten →