pith. sign in

arxiv: 2602.10747 · v2 · submitted 2026-02-11 · 💻 cs.DS

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness

Bernhard Haeupler , Antti Roeyskoe , Zhijun Zhang This is my paper

Pith reviewed 2026-05-16 03:27 UTC · model grok-4.3

classification 💻 cs.DS
keywords shortcutcertifiedconstructionsdiameterefficientbestcriteriongraph
0
0 comments X

The pith

Certified shortcuts are precisely the ones constructible in near-linear time, and no almost-linear-size certified shortcut can reduce diameter below n^{1/4-o(1)}.

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

In parallel computing, many algorithms for finding paths in huge directed graphs work by adding shortcut edges that skip over long paths, shrinking the graph's diameter so that fewer rounds of communication are needed. The authors introduce a simple check called certification: an added shortcut edge (u to v) is certified only if some intermediate vertex w already connects u to w and w to v using existing edges or other shortcuts. They prove that a shortcut set can be built efficiently by repeatedly finding and shortcutting paths of length ell in ell time if and only if there exists a certified superset of roughly the same size. All previously known efficient constructions can be made certified, while constructions that resisted efficient implementation cannot be certified at all. Using this lens they also prove stronger lower bounds: any certified shortcut set of near-linear size must leave some pairs at distance at least roughly the fourth root of n.

Core claim

A shortcut H can be constructed in t time by repeatedly spending ℓ time on shortcutting a path of length ℓ, if and only if, there exists a certified shortcut H' ⊇ H of size Õ(t). Furthermore, no certified shortcut construction with almost-linear size can reduce a graph's diameter below n^{1/4-o(1)}.

Load-bearing premise

The model of constructibility is restricted to repeatedly shortcutting a single path of length ℓ in exactly ℓ time; if more powerful parallel or batched construction primitives are allowed, the equivalence to certification may fail.

Figures

Figures reproduced from arXiv: 2602.10747 by Antti Roeyskoe, Bernhard Haeupler, Zhijun Zhang.

Figure 1
Figure 1. Figure 1: An illustration of the graph construction for [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of the graph construction for [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An illustration of the graph construction for [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of the graph construction for [PITH_FULL_IMAGE:figures/full_fig_p024_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Two treaps on sequences ABCDE and FGHIJ respectively, with the priorities represented [PITH_FULL_IMAGE:figures/full_fig_p034_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The treap resulting from a join operation on the two treaps of [PITH_FULL_IMAGE:figures/full_fig_p035_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The two treaps resulting from a split operation on the treap of [PITH_FULL_IMAGE:figures/full_fig_p035_7.png] view at source ↗
read the original abstract

All parallel algorithms for directed reachability and shortest paths crucially rely on efficient shortcut constructions. These constructions find directed paths and shortcut them by adding edges, with the goal to reduce the diameter of the graph. A long sequence of works has studied (efficient) shortcut constructions as well as impossibility results on the best diameter and therefore the best parallelism that can be achieved via this approach. This paper introduces a new conceptual tool for this line of research in the form of a simple and natural structural criterion: A shortcut $H$ for a graph $G$ is certified if for any shortcut edge $(u, v) \in H$, there exists a vertex $w$ such that the edges $(u, w)$ and $(w, v)$ are also in $G \cup H$. We show that this criterion captures constructiveness in the following sense: A shortcut $H$ can be constructed in $t$ time by repeatedly spending $\ell$ time on shortcutting a path of length $\ell$, if and only if, there exists a certified shortcut $H' \supseteq H$ of size $\tilde{O}(t)$. Furthermore, all known shortcut constructions with efficient algorithms can be extended to produce certified shortcuts of size $\tilde{O}(m)$. On the other hand, for shortcut constructions for which attempts to find efficient implementations have failed, we can show that this is impossible. We also obtain stronger diameter lower bounds for certified shortcuts and hopsets. For example, no certified shortcut construction with almost-linear size can reduce a graph's diameter below $n^{1/4-o(1)}$. This seems to be the best bound one can hope for with current techniques.

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.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The paper introduces the certified shortcut as a new structural property rather than deriving it from prior axioms. No free parameters are fitted; the work relies on standard directed-graph definitions and the explicit construction model of repeatedly shortcutting single paths.

axioms (2)
  • standard math The underlying graph is a directed graph with m edges and n vertices; standard adjacency-list representation is assumed.
    Invoked throughout the definition of shortcuts and diameter.
  • domain assumption Construction time is measured by the number of rounds in which a single path of length ℓ can be shortcut in exactly ℓ time.
    This is the explicit model used for the if-and-only-if characterization.
invented entities (1)
  • certified shortcut no independent evidence
    purpose: A structural property that exactly captures shortcuts constructible by repeated single-path shortcutting.
    Newly defined in the paper; no independent evidence outside the equivalence proof is provided.

pith-pipeline@v0.9.0 · 5613 in / 1566 out tokens · 178016 ms · 2026-05-16T03:27:11.405705+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.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers , booktitle =

    URL:https://doi.org/10.1137/1.9781611977554.ch9,doi:10.1137/1. 9781611977554.CH9. 4, 5, 6, 12, 14, 15, 18 [LVWX22] Kevin Lu, Virginia Vassilevska Williams, Nicole Wein, and Zixuan Xu. Better lower bounds for shortcut sets and additive spanners via an improved alternation product. In Joseph (Seffi) Naor and Niv Buchbinder, editors,Proceedings of the 2022 A...

    work page doi:10.1137/1.9781611977554.ch9 2022

  2. [2]

    , Hk ofk=O(logn) shortcuts of total size P i |Hi|=O(|H|logn) such that •H⊆E∪H 1 ∪ · · · ∪H k

    5, 6, 7 A Extending a Certified Shortcut to have Low Certification Depth In this section, we show the following: Lemma A.1.For anyn-vertex DAGG= (V, E) and certified shortcutHonG, there exists a sequenceH 1, H2, . . . , Hk ofk=O(logn) shortcuts of total size P i |Hi|=O(|H|logn) such that •H⊆E∪H 1 ∪ · · · ∪H k. •For every edgee= (u, v)∈H i, there is a pair...

    work page

  3. [3]

    Each tree has asymptotically optimal depthO(log|P e|)

    work page

  4. [4]

    The total number ofdistinctsubtrees over all the treesT e (e∈H) is at mostO(|H|logn). Such an assignment can be achieved by using a standard persistent balanced binary tree structure such as a treap [AS89] that supports the join-operation on two trees (this operation combines the two input trees so that in the resulting tree, every node of the first tree ...

    work page

  5. [5]

    It hasn= Θ(dD d+1rd+1) vertices andm= Θ(n∆) edges, where ∆ = Θ(r 2/3) is the maximum degree

    work page

  6. [6]

    backtracing

    It has a setPof Θ(n∆ d/(dD)) critical paths such that: (a) Each path hasdDedges. (b) Each path is the unique shortest path between its endpoints. (c) The intersection between any two paths is a subpath with at mostd−1 edges. Proof.The graphGis constructed as follows. For simplicity, we first consider the directed setting by constructing DAGs for anyd >0. ...

    work page

  7. [7]

    for somev ′ 1 ∈ V(r) in the forward direction, or traverses an edge corresponding toe 2(v′

    work page

  8. [8]

    In the former case, ⟨e1(v′ 1),v ′⟩>0 andv ′ 1 =v 1 is the unique maximizer due to strict convexity

    for somev ′ 2 ∈ V(r) in the backward direction. In the former case, ⟨e1(v′ 1),v ′⟩>0 andv ′ 1 =v 1 is the unique maximizer due to strict convexity. In the latter case, we always have⟨−e 2(v′ 2),v ′⟩<0 becausev ′ 2 ∈ V(r) can only have positive coordinates by definition. Thus,P ′ can maximize⟨u ′′ −u,v ′⟩only if it traverses the edge corresponding toe 1(v1...

    work page

  9. [9]

    It hasD=n 1/7−Θ(ε) layers

    work page

  10. [10]

    The first and the last layers each haven 3/7+Θ(ε) ≤n 1/2 vertices

    work page

  11. [11]

    (b) Each path is the unique path between its endpoints

    It has a setPof Θ(n 1+2ε/D) critical paths such that: (a) Each path is from the first layer to the last layer. (b) Each path is the unique path between its endpoints. (c) The intersection between any two paths is at most one edge. Proof.The starting point is a construction of [Bod21], originally introduced in the context of reachability and distance prese...

    work page

  12. [12]

    Suppose this is the root of the left treap

    Set the root of the result to be the lower-priority root of the two input treaps. Suppose this is the root of the left treap

    work page

  13. [13]

    Recursivelyjointhe right subtree of the left treap’s root and the right treap, to form the treap for the subsequence right of the root

    work page

  14. [14]

    Thesplitoperation on a treap and a split pointkcan be performed as follows:

    Set the right subtree of the root to be the result of this merge. Thesplitoperation on a treap and a split pointkcan be performed as follows:

    work page

  15. [15]

    If the left subtree has size at leastk, recursively split it, set the right tree of the recursive split to be the new left subtree, and return the left tree of the recursive split and the old root

    work page

  16. [16]

    Set the left tree of the recursive split to be the new right subtree, and return the old root and the right tree of the recursive split

    Otherwise, if the left subtree has size strictly less thank, recursively split the right subtree atk−size of the left subtree−1. Set the left tree of the recursive split to be the new right subtree, and return the old root and the right tree of the recursive split. The subtree sizes can be maintained by updating the size whenever a child is changed or rec...

    work page