Lune

FOCS2021Top-tier venue

Hop-Constrained Metric Embeddings and their Applications

Arnold Filtser

Abstract

In network design problems, such as compact routing, the goal is to route packets between nodes using the (approximated) shortest paths. A desirable property of these routes is a small number of hops, which makes them more reliable, and reduces the transmission costs. Following the overwhelming success of stochastic tree embeddings for algorithmic design, Haeupler, Hershkowitz, and Zuzic (STOC'21) studied hop-constrained Ramsey-type metric embeddings into trees. Specifically, embeddingf:G(V,E)→Tf: G(V, E)\rightarrow Thas Ramsey hop-distortion (t,M,β,ht, M,\beta, h), (heret,β,h≥1t, \beta, h\geq 1andM⊆V)M\subseteq V)if∀u∈M,v∈V, dG(β⋅h)(u,v)≤dT(u,v)≤t⋅dG(h)(u,v).t\forall u\in M, v\in V,\ d_{G}^{(\beta\cdot h)}(u, v)\leq d_{T}(u, v)\leq t\cdot d_{G}^{(h)}(u, v). tis called the distortion,β\betais called the hop-stretch, anddG(h)(u,v)d_{G}^{(h)}(u, v)denotes the minimum weight of au−vu-vpath with at mosthhhops. Haeupler et al. constructed embedding whereMMcontains1−ϵ1-\epsilonfraction of the vertices andβ=t=O(log⁡2nϵ)\beta=t=O(\frac{\log^{2}n}{\epsilon}). They used their embedding to obtain multiple bicriteria approximation algorithms for hop-constrained network design problems. In this paper, we first improve the Ramsey-type embedding to obtain parameterst=β=O~(log⁡n)ϵt=\beta=\frac{\tilde{O}(\log n)}{\epsilon}, and generalize it to arbitrary distortion parametertt(in the cost of reducing the size ofMM). This embedding immediately implies polynomial improvements for all the approximation algorithms from Haeupler et al.. Further, we construct hop-constrained clan embeddings (where each vertex has multiple copies), and use them to construct bicriteria approximation algorithms for the group Steiner tree problem, matching the state of the art of the non constrained version. Finally, we use our embedding results to construct hop constrained distance oracles, distance labeling, and most prominently, the first hop constrained compact routing scheme with provable guarantees. All our metric data structures almost match the state of the art parameters of the non-constrained versions.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

10 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings cites On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
  • Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings cites Clan embeddings into trees, and low treewidth graphs
  • Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings cites Low Treewidth Embeddings of Planar and Minor-Free Metrics
  • Clan embeddings into trees, and low treewidth graphs cites On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
  • How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs cites Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
  • How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs cites On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
  • How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs cites Clan embeddings into trees, and low treewidth graphs
  • How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs cites One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
  • How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs cites Locality-sensitive orderings and applications to reliable spanners
  • One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree cites Clan embeddings into trees, and low treewidth graphs
  • One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree cites Locality-sensitive orderings and applications to reliable spanners
  • Low Treewidth Embeddings of Planar and Minor-Free Metrics cites On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
  • Low Treewidth Embeddings of Planar and Minor-Free Metrics cites Clan embeddings into trees, and low treewidth graphs
  • Locality-sensitive orderings and applications to reliable spanners cites On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
  • Locality-sensitive orderings and applications to reliable spanners cites Clan embeddings into trees, and low treewidth graphs
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers10

  1. How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free GraphsJonathan Conroy, Arnold FiltserSTOC 2025 · 11 citations
  2. Low Treewidth Embeddings of Planar and Minor-Free MetricsArnold Filtser, Hung LeFOCS 2022 · 8 citations
  3. Locality-sensitive orderings and applications to reliable spannersArnold Filtser, Hung LeSTOC 2022 · 8 citations
  4. Online Duet between Metric Embeddings and Minimum-Weight Perfect MatchingsSujoy Bhore, Arnold Filtser, Csaba D. TóthSODA 2024 · 4 citations
  5. One Tree to Rule Them All: Poly-Logarithmic Universal Steiner TreeCostas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock et al.FOCS 2023 · 4 citations

Builds on11

  1. Parallel approximate undirected shortest paths via low hop emulatorsAlexandr Andoni, Clifford Stein, Peilin ZhongSTOC 2020 · 50 citations
  2. On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free GraphsVincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung LeFOCS 2020 · 25 citations
  3. Hop-constrained oblivious routingMohsen Ghaffari, Bernhard Haeupler, Goran ZuzicSTOC 2021 · 15 citations
  4. Clan embeddings into trees, and low treewidth graphsArnold Filtser, Hung LeSTOC 2021 · 11 citations
  5. Low Treewidth Embeddings of Planar and Minor-Free MetricsArnold Filtser, Hung LeFOCS 2022 · 8 citations

Related papers

  1. Tree embeddings for hop-constrained network designBernhard Haeupler, D. Ellis Hershkowitz, Goran ZuzicSTOC 2021 · 1 citation
  2. Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michal PilipczukFOCS 2023 · 5 citations
  3. Having Hope in Hops: New Spanners, Preservers and Lower Bounds for HopsetsShimon Kogan, Merav ParterFOCS 2022 · 5 citations
  4. Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent BoundsYair Bartal, Nova Fandina, Seeun William UmbohSODA 2020 · 5 citations
  5. Cost-Distance Steiner Trees for Timing-Constrained Global RoutingStephan Held, Edgar PernerDAC 2025
Dusk over the sea between two cliffs drawn in fine vertical lines