pith. sign in

arxiv: 2511.20111 · v2 · submitted 2025-11-25 · 💻 cs.DS · cs.DM

Greedy Algorithms for Shortcut Sets and Hopsets

Ben Bals , Joakim Blikstad , Greg Bodwin , Daniel Dadush , Sebastian Forster , Yasamin Nazari This is my paper

Pith reviewed 2026-05-17 05:15 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords greedy algorithmsshortcut setshopsetsgraph sparsificationmetric augmentationhopbound tradeoffexistential optimalitygraph algorithms
0
0 comments X

The pith

A simple greedy algorithm matches the best known size-hopbound tradeoffs for shortcut sets up to log n factors and is existentially optimal for matching hopsets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that greedy methods, already successful for spanners and emulators, can be extended to shortcut sets and hopsets in graphs. A basic greedy procedure selects additional edges to achieve the current optimal tradeoff between the number of shortcuts added and the maximum hops needed to approximate all pairwise distances. An extra preprocessing phase yields subpolynomial size savings for some parameter settings. The same procedure is also shown to be optimal in an existential sense for the matching hopset variant, where the added edges are limited to roughly the number of original edges.

Core claim

A simple greedy algorithm for shortcut sets achieves the state-of-the-art size/hopbound tradeoff recently proved by Kogan and Parter (2022), up to O(log n) factors in the size. Moreover, with an additional preprocessing step, the greedy algorithm subpolynomially improves on the previous size bounds in some range of parameters. The same greedy algorithm is also existentially optimal (up to O(log n) factors) for the matching hopset problem, in which one has a budget of roughly O(m) additional edges for an m-edge input graph.

What carries the argument

The greedy algorithm that iteratively adds the edge providing the greatest improvement to hop-distance properties in the current graph.

If this is right

  • The greedy method reaches the known optimal size versus hopbound tradeoff for shortcut sets, up to an O(log n) size overhead.
  • A preprocessing step produces subpolynomial size savings over prior bounds in certain parameter ranges.
  • The identical greedy rule is existentially optimal up to O(log n) factors for the matching hopset problem with an O(m) edge budget.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The results indicate that the greedy paradigm may extend to other graph augmentation tasks that add edges to control distance or connectivity properties.
  • Different analyses of the same greedy rule can establish both upper bounds matching prior work and existential optimality for related objects.

Load-bearing premise

The greedy selection rule must accurately reflect the necessary distance and hop reductions without depending on hidden properties of particular graph families or edge-weight distributions.

What would settle it

A concrete graph family where the greedy shortcut set exceeds the Kogan-Parter size bound by more than an O(log n) factor for a fixed hopbound would falsify the main tradeoff claim.

Figures

Figures reproduced from arXiv: 2511.20111 by Ben Bals, Daniel Dadush, Greg Bodwin, Joakim Blikstad, Sebastian Forster, Yasamin Nazari.

Figure 1
Figure 1. Figure 1: The (red) valid path 𝑃 passes through 𝐿 chains in the ℓ-chain cover. The shortcut edge between 𝑣 2 𝐿/3 and 𝑣 1 2𝐿/3 reduces the normalized distance between the first 𝐿/3 vertices on the path to the last 𝐿/3 chains on the path by 𝐿/3. • 𝑃 ∩ 𝐶 forms a contiguous segment on the path 𝑃, and • if 𝑤 is the earliest node on 𝐶 that 𝑢 can reach in 𝐺, the segment 𝑃 ∩ 𝐶 must start at 𝑤. We consider the normalized dis… view at source ↗
Figure 2
Figure 2. Figure 2: The short path constructed in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Result of computing 𝜑 𝐶 (𝑣) for the nodes in 𝑇 𝐶 3 . Observe that multiple nodes from the chain 𝐶 ′ appear in 𝑇 𝐶 3 and only those occurrences that are not a descendant of another node from 𝐶 ′ in 𝑇 𝐶 3 are assigned non-zero values. Observe that in this counting all the prefixes originating on a specific chain 𝐶 are counted within 𝜑 𝐶 (𝑣1) where 𝑣1 is the first node on 𝐶. While Theorem 7.10 will help us co… view at source ↗
read the original abstract

For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentially optimal tradeoffs between size and quality. The goal of this paper is to develop and analyze comparable greedy algorithms for nearby objects in graph metric augmentation. We show the following: - A simple greedy algorithm for shortcut sets achieves the state-of-the-art size/hopbound tradeoff recently proved by Kogan and Parter (2022), up to $O(\log n)$ factors in the size. Moreover, with an additional preprocessing step, the greedy algorithm subpolynomially improves on the previous size bounds in some range of parameters. - The same greedy algorithm was already known to be existentially optimal for the size/hopbound tradeoff for hopsets, by an analysis of Berman, Raskhodnikova, and Ruan (2010) introduced for transitive-closure spanners. We provide a completely different analysis showing that the algorithm is also existentially optimal (up to $O(\log n)$ factors) for the matching hopset problem, in which one has a budget of roughly $O(m)$ additional edges (for an $m$-edge input graph).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript presents greedy algorithms for shortcut sets and hopsets. It claims that a simple greedy algorithm for shortcut sets matches the state-of-the-art size/hopbound tradeoff of Kogan and Parter (2022) up to O(log n) factors in size; with an added preprocessing step it subpolynomially improves prior size bounds in some parameter ranges. The same greedy algorithm is shown via a new analysis (distinct from Berman et al. 2010) to be existentially optimal up to O(log n) factors for the matching hopset problem under an O(m)-edge budget.

Significance. If the central claims hold, the work is significant for demonstrating that elementary greedy selection suffices to match or exceed recent optimal tradeoffs for these metric-augmentation objects, thereby unifying the greedy paradigm across spanners, preservers, shortcut sets, and hopsets. The new optimality proof for matching hopsets and the preprocessing-based improvement are concrete strengths. The stress-test concern about unstated weight or family assumptions does not appear to land on the manuscript as written; the analyses are presented in the standard setting of directed graphs with non-negative weights and no negative cycles, consistent with the Kogan-Parter benchmark.

major comments (1)
  1. §4 (preprocessing step): the subpolynomial improvement is asserted but the precise exponent, the exact range of parameters (e.g., hopbound vs. size), and the quantitative size reduction relative to Kogan-Parter are not stated explicitly; without these the improvement claim cannot be verified as load-bearing for the central tradeoff result.
minor comments (2)
  1. Abstract and §1: the phrase 'subpolynomially improves on the previous size bounds in some range of parameters' should be accompanied by a concrete statement of the improvement (e.g., n^{o(1)} factor) to aid readers.
  2. Notation section: the definition of the greedy selection criterion should include a short remark confirming it is independent of any particular graph family beyond the standard directed non-negative-weight model.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the positive recommendation for minor revision. We address the major comment below.

read point-by-point responses

  1. Referee: [—] §4 (preprocessing step): the subpolynomial improvement is asserted but the precise exponent, the exact range of parameters (e.g., hopbound vs. size), and the quantitative size reduction relative to Kogan-Parter are not stated explicitly; without these the improvement claim cannot be verified as load-bearing for the central tradeoff result.

    Authors: We agree that the details should be stated more explicitly to facilitate verification. In the revised manuscript we will expand the discussion in Section 4 to specify the precise exponent of the subpolynomial improvement, the exact parameter range (including the relevant hopbound and size regimes) in which the improvement holds, and a direct quantitative comparison of the resulting size bound to that of Kogan and Parter (2022). These additions will make clear how the preprocessing step relates to the central size/hopbound tradeoff. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on independent analysis of greedy algorithm

full rationale

The paper introduces a greedy algorithm for shortcut sets and hopsets and provides a new analysis showing it matches the Kogan-Parter (2022) tradeoff up to logarithmic factors, with an optional preprocessing step for subpolynomial improvement in some regimes. It also supplies a distinct analysis (separate from Berman et al. 2010) establishing existential optimality for the O(m)-budget matching hopset problem. These steps are presented as direct algorithmic constructions and proofs rather than reductions to fitted parameters, self-definitions, or load-bearing self-citations. The cited prior results function as external benchmarks, and no equations or selection criteria are shown to collapse by construction into the claimed outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work is a proof-based analysis of a combinatorial algorithm; it relies on standard graph-theoretic definitions of distance, hops, and existential optimality rather than fitted parameters or new postulated entities.

axioms (1)
  • standard math Standard definitions of shortest-path distances and hop distance in undirected graphs
    Invoked throughout the definitions of shortcut sets, hopsets, and hopbounds.

pith-pipeline@v0.9.0 · 5535 in / 1252 out tokens · 48664 ms · 2026-05-17T05:15:09.486211+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth

    cs.DS 2026-05 unverdicted novelty 7.0

    New parallel algorithms achieve Õ(m) work and o(√n) depth for reachability and shortest paths on directed graphs whenever m ≥ n^{1+o(1)}, improving on the prior Ω(√n) depth barrier.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · cited by 1 Pith paper

  1. [1]

    Multi-level weighted additive spanners.arXiv preprint arXiv:2102.05831,

    [ABS+21] Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, and Richard Spence. Multi-level weighted additive spanners.arXiv preprint arXiv:2102.05831,

    work page arXiv

  2. [2]

    Optimal vertex fault tolerant spanners (for fixed stretch)

    [BDPW18] Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams. Optimal vertex fault tolerant spanners (for fixed stretch). InProceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1884–1900. Society for Industrial and Applied Mathematics,

    work page 1900

  3. [3]

    Deterministic decre- mental SSSP and approximate min-cost flow in almost-linear time

    [BPGS21] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decre- mental SSSP and approximate min-cost flow in almost-linear time. In62 Annual IEEE Symposium on Foundatios of Computer Science (FOCS 2022),

    work page 2022

  4. [4]

    Finding sparser directed spanners

    [BRR10] Piotr Berman, Sofya Raskhodnikova, and Ge Ruan. Finding sparser directed spanners. InIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), pages 424–435. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik,

    work page 2010

  5. [5]

    Closing the gap between directed hopsets and shortcut sets

    [BW23] Aaron Bernstein and Nicole Wein. Closing the gap between directed hopsets and shortcut sets. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 163–182. SIAM,

    work page 2023

  6. [6]

    [CF23] NairenCaoandJeremyTFineman

    arXiv:2305.02166 [cs]. [CF23] NairenCaoandJeremyTFineman. Parallelexactshortestpathsinalmostlinearworkandsquareroot depth. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4354–4372. SIAM,

    work page arXiv 2023

  7. [7]

    Fineman, and Katina Russell

    [CFR20b] Nairen Cao, Jeremy T. Fineman, and Katina Russell. Efficient construction of directed hopsets and parallel approximate shortest paths. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 336–349, New York, NY, USA,

    work page 2020

  8. [8]

    Shortcuts and transitive-closure spanners approximation.arXiv preprint arXiv:2502.08032,

    [CJMN25] Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, and Danupon Nanongkai. Shortcuts and transitive-closure spanners approximation.arXiv preprint arXiv:2502.08032,

    work page arXiv

  9. [9]

    Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication

    [EN22] Michael Elkin and Ofer Neiman. Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication. In Petra Berenbrink and Benjamin Monmege, editors,39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), volume 219 ofLeibniz International Proceedings in Informatics (LI...

    work page 2022

  10. [10]

    The greedy spanner is existentially optimal

    [FS16] Arnold Filtser and Shay Solomon. The greedy spanner is existentially optimal. InProceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 9–17,

    work page 2016

  11. [11]

    Lower Bounds on Sparse Spanners, Emulators, and Diameter- reducing shortcuts

    21 [HP18] Shang-En Huang and Seth Pettie. Lower Bounds on Sparse Spanners, Emulators, and Diameter- reducing shortcuts. In David Eppstein, editor,16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), volume 101 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:12, Dagstuhl, Germany,

    work page 2018

  12. [12]

    [HXX24] Gary Hoppenworth, Yinzhan Xu, and Zixuan Xu

    Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. [HXX24] Gary Hoppenworth, Yinzhan Xu, and Zixuan Xu. New separations and reductions for directed preservers and hopsets.arXiv preprint arXiv:2411.08151,

    work page arXiv

  13. [13]

    Faster and Unified Algorithms for Diameter Re- ducing Shortcuts and Minimum Chain Covers

    [KP] Shimon Kogan and Merav Parter. Faster and Unified Algorithms for Diameter Re- ducing Shortcuts and Minimum Chain Covers. InProceedings of the 2023 An- nual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 212–239. _eprint: https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch9. [KP22a] Shimon Kogan and Merav Parter. Beating Matrix Multipli...

    work page doi:10.1137/1.9781611977554.ch9 2023

  14. [14]

    New diameter-reducing shortcuts and directed hopsets: Breaking the barrier

    [KP22c] Shimon Kogan and Merav Parter. New diameter-reducing shortcuts and directed hopsets: Breaking the barrier. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1326–1341. SIAM,

    work page 2022

  15. [15]

    New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the 𝑂( √𝑛) Barrier

    [KP22d] Shimon Kogan and Merav Parter. New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the 𝑂( √𝑛) Barrier. InProceedings of the 2022 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 1326–1341

    work page 2022

  16. [16]

    [KP24a] Shimon Kogan and Merav Parter

    _eprint: https://epubs.siam.org/doi/pdf/10.1137/1.9781611977073.55. [KP24a] Shimon Kogan and Merav Parter. The Algorithmic Power of the Greene-Kleitman Theorem.LIPIcs, Volume 308, ESA 2024, 308:80:1–80:14,

    work page doi:10.1137/1.9781611977073.55 2024

  17. [17]

    [KP24b] Shimon Kogan and Merav Parter

    Artwork Size: 14 pages, 722270 bytes ISBN: 9783959773386 Medium: application/pdf Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [KP24b] Shimon Kogan and Merav Parter. Giving some slack: Shortcuts and transitive closure compressions. In32nd Annual European Symposium on Algorithms (ESA 2024), pages 79–1. Schloss Dagstuhl– Leibniz-Zentrum für ...

    work page 2024

  18. [18]

    Near-optimal decremental hopsets with applications

    [ŁN22] Jakub Łącki and Yasamin Nazari. Near-optimal decremental hopsets with applications. In49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik,

    work page 2022

  19. [19]

    Simpler and higher lower bounds for shortcut sets

    22 [WXX24] Virginia Vassilevska Williams, Yinzhan Xu, and Zixuan Xu. Simpler and higher lower bounds for shortcut sets. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2643–2656. SIAM,

    work page 2024