New Separations and Reductions for Directed Hopsets and Preservers
Gary Hoppenworth, Yinzhan Xu, Zixuan Xu
2025Year
2Citations
3Top-tier citations
Abstract
We study distance preservers, hopsets, and shortcut sets in n-node, m-edge directed graphs, and show improved bounds and new reductions for various settings for these problems.
Ask about this paper
Ask your agent about it.
Lune has read the top-tier papers around this one, so every answer names the papers it rests on.
Your agent calls
Lunesearch_papers
Free to start. No credit card required.
Terminal
Install the CLIlune papers get 4ec3a8cb-d375-424e-8489-03e41321876cCited by top-tier papers3
- DAG Projections: Reducing Distance and Flow Problems to DAGsBernhard Haeupler, Yonggang Jiang, Thatchaphol SaranurakSTOC 2026 · 2 citations
- Covering Approximate Shortest Paths with DAGsSepehr Assadi, Gary Hoppenworth, Nicole WeinSTOC 2025 · 1 citation
- Reviving Thorup's Shortcut ConjectureAaron Bernstein, Henry L. Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler et al.STOC 2026 · 1 citation
Related papers
- Having Hope in Hops: New Spanners, Preservers and Lower Bounds for HopsetsShimon Kogan, Merav ParterFOCS 2022 · 5 citations
- Closing the Gap Between Directed Hopsets and Shortcut SetsAaron Bernstein, Nicole WeinSODA 2023 · 3 citations
- Simpler and Higher Lower Bounds for Shortcut SetsVirginia Vassilevska Williams, Yinzhan Xu, Zixuan XuSODA 2024 · 2 citations
- Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n BarrierGreg Bodwin, Gary HoppenworthFOCS 2023 · 2 citations
- Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation ProductKevin Lu, Virginia Vassilevska Williams, Nicole Wein, Zixuan XuSODA 2022 · 6 citations
