Faster Directed Hopsets, Distance Preservers, and Deterministic Shortcut Sets

1 Introduction

• For eO(n)-size hopsets with O(n^1/3) hopbound, construction takes eO(mn^2/3), improving on Bernstein and Wein’s O(mn) time while matching their size/hopbound tradeoff.The DAG construction extends to general graphs up to n^o(1) factors using the DAG projection result of [HJS26].Source: §1 · p. 4
• For β=O(n^1/3), a deterministic eO(m·n/β)-time algorithm constructs eO(n^2/β^3)-size O(β)-shortcut sets.For linear-size shortcut sets with hopbound eO(n^1/3), the stated running time is eO(mn^2/3).Source: §1 · p. 4
• For p≤n, preservers have size eO(np^1/3+(np)^2/3) and running time eO(p^2/3m+σ(m+p)+np^1/3).For p≥n, the stated running time is eO((np)^1/3m+σ(m+p)+(np)^2/3), with the same size bound.Source: §1 · p. 5
• For p≥n^3/4, the preserver construction recovers state-of-the-art size bounds with faster construction time, avoiding the hop-bounded APSP cost of the black-box reduction.For suitably small σ and p, the construction takes O(mn^α) time for α<1.Source: §1 · p. 5

1.1 Summary of Technical Contributions

• A greedy shortest-chain cover supplies the hopset algorithm’s core, with sampling reducing its running time to eO(nm/β).The shortest-chain constraint makes the min-cost max-flow reduction used for shortcut sets inapplicable.Source: §1 · p. 4, §1.1 · p. 5
• The deterministic shortcut-set method avoids vertex sampling and implicitly solves a tolerable-approximation set-cover problem using canonical paths and fast updates to candidate-chain contributions.The path structure enables efficient dynamic updates during greedy selection.Source: §1.1 · p. 6
• The preserver algorithm white-boxes the hopset-to-preserver reduction and builds a data structure that returns approximate low-hop witnesses for hierarchy edges in near-linear output time.The construction transforms sampled-vertex and sampled-chain rerouting into a height-reduced shortest-path tree.Source: §1.1 · p. 6

2 Preliminaries

• A DAG is a directed graph with no directed cycle.Source: §2 · p. 6
• DAG single-source shortest paths compute all out-distances and a shortest-path tree in O(n + m) time.Source: §2 · p. 6
• An ℓ-chain cover uses at most ℓ vertex-disjoint chains so every path has at most 2n/ℓ vertices outside them.This formalizes the output of DisjointChains.Source: §2 · p. 6
• SuperShort adds O(n log* n) edges so vertices ordered along each covered chain have distance at most four.It can be computed in O(|H|) time; the construction applies the path-graph shortcut result to each chain.Source: §2 · p. 7

3 Greedy Lightest Chain Cover in eO(𝑛/𝛽· 𝑚)

• The hopset construction samples vertices, forms well-behaved chains, super-shortcuts them, samples chains, then connects sampled vertices to reachable sampled chains.The section focuses on computing the chain family quickly; the remaining steps use the existing routing and implementation lemmas.Source: §3 · p. 7
• For the sampled vertex set, the target cover has lightest chains of weight at most ηL, O(n/β) members, and pairwise vertex-disjointness.The cover also controls uncovered vertices on relevant lightest paths from sampled vertices.Source: §3 · p. 7
• eO(n/β · m) time suffices to compute a set satisfying the lightest-chain-cover conditions.For integer weights the algorithm encodes distance and uncovered-vertex count in modified weights; for real weights, the DAG dynamic program compares (distance, −number of uncovered vertices) lexicographically.Source: §3 · p. 7
• When the algorithm finds a qualifying path, it adds its negative-weight vertices as a chain and resets their weights to zero.The supplied algorithm steps describe this greedy selection and reset procedure.Source: §3 · p. 8

11 end

• A perturbation of magnitude below 1/2 keeps modified shortest paths lightest in the original graph while favoring paths with more uncovered vertices.The edge weights are positive integers and each vertex weight is either 0 or −1/(2n).Source: §11 · p. 8
• At most n/β successful iterations are needed, and truncation increases the chain count by only an Oη(1) factor.The resulting chains remain lightest, have weight at most ηL, and are pairwise vertex-disjoint.Source: §11 · p. 8
• eO(n/β · m) time bounds the chain-cover computation, including successful and final failed SSSP computations.Each successful iteration covers at least β previously uncovered vertices; each sampled source contributes at most one final failed computation.Source: §11 · p. 8

4 Near Linear-Time Deterministic √𝑛-Shortcut Sets

• The chain-cover approach directly gives deterministic eO(n)-size shortcut sets for D = O(√n) in the same time.Source: §4 · p. 9
• O(m1+o(1)) time constructs a deterministic O(n log* n)-size shortcut set with O(√n) hopbound for any DAG.Source: §4 · p. 9
• The construction computes a √n-chain cover, then super-shortcuts every chain.This combines the deterministic chain-cover algorithm with the chain-shortcutting result.Source: §4 · p. 9
• A shortest path in the shortcut graph uses at most 7√n nodes under the stated chain-cover and super-shortcut properties.The bound follows from at most 2√n nodes outside chains, at most √n chains visited, and at most five nodes from each chain.Source: §4 · p. 9

5 Deterministic 𝑛1/3-Shortcut Sets using Greedy Set Cover

• For β=O(n^1/3), a deterministic eO(m·n/β)-time algorithm computes eO(n^2/β^3)-size O(β)-shortcut sets; at β=n^1/3, the bounds are eO(mn^2/3) time and eO(n) size.The construction is a deterministic version of the shortcut-set algorithm of [KP22c].Source: §5 · p. 9
• In O(ℓm) time, one subtree per chain represents its outgoing reachability, with paths intersecting any other chain consecutively and sharing the same suffix as that chain’s tree.The union of the tree paths forms a path complex for the chains’ outgoing reachability.Source: §5 · pp. 10–11
• Instead of sampling chains, an implicit greedy set-cover instance selects chains that hit normalized-length-β prefixes and suffixes of paths in the reachability path complex.The construction also avoids sampling vertices by selecting vertices on the chosen chains.Source: §5 · pp. 9, 11
• If selected chains hit every relevant subpath, adding edges from each selected-chain vertex to the first reachable vertex in each selected chain yields O(β)-shortcut sets of size O(nlog*n + |C′|^2·β).The construction adds these edges to SuperShort(C).Source: §5 · p. 12
• Greedy coverage potentials can be initialized in O(ℓm) time, and a series of k chain-selection updates takes O(ℓn + kβn) time.The potentials count uncovered relevant subpaths covered by nodes and chains.Source: §5 · pp. 13–14
• For β = O(n^1/3), a deterministic algorithm computes O(β)-shortcut sets of size eO(n^2/β^3) in eO(mn/β) time.The running time is O(mn/β) when β = Ω(log n) and m = Ω(n log n).Source: §5 · p. 15
• Greedy set cover selects O(n/β^2 log n) chains: assigning each chain fractional value β^-1 gives a feasible solution of weight O(n/β^2).Each relevant subpath contains exactly β different chains, and there are at most n^2 relevant subpaths, so the greedy logarithmic factor is at most 2 log n.Source: §5 · p. 15
• Processing all updates takes O(mn/β + n^2 log n/β) time after substituting the greedy chain count into the covering-potential update bound.Greedy repeatedly chooses a chain with maximal potential and updates node and chain potentials until no chain has positive potential.Source: §5 · p. 15
• The running time matches asymptotically, including log factors, and the authors conjecture—but do not prove—that their techniques can derandomize for β = Ω(n^1/3).Source: §5 · p. 15

6 Fast Sourcewise Approximate Distance Preservers

• The preserver has eO(np^(1/3)+(np)^(2/3)) edges; construction takes eO(p^(2/3)m+σ(m+p)+np^(1/3)) time for p≤n, or eO((np)^(1/3)m+σ(m+p)+(np)^(2/3)) for p≥n.The theorem assumes an n-vertex DAG with nonnegative edge weights and polynomial aspect ratio.Source: §6 · pp. 15–16
• The reduction replaces its hop-bounded APSP call with fast witness-path reporting for hopset edges and rooted hop-bounded shortest paths for each source.The sourcewise reduction is based on Kogan and Parter [KP22b].Source: §6 · p. 16
• A hopset hierarchy expands each used hopset edge into a low-hop approximate path one level lower, until only original graph edges remain.Each witness path has at most β_(i−1) edges and weight at most (1+δ)d_G(u,v).Source: §6 · pp. 16–17
• For each source, rooted retrieval computes paths to reachable vertices with at most β edges and weight at most (1+δ)d_G(r,v) in eO(m+|H|) time.The resulting demand-pair routes are expanded and their original graph edges collected into the preserver.Source: §6 · pp. 16–17
• The proof bounds approximation after recursively expanding the hierarchy, then chooses hopbounds in two phases when p≥n.The hierarchy has O(log log n) levels in the stated constructions.Source: §6 · pp. 17–19

7 Data Structure for Reporting Hopset Witnesses

• For any root, the retrieval structure computes paths to all reachable vertices using at most β edges and weight at most (1+δ)d_G(r,v), in eO(m+|H|) time.The construction rehanges parts of a shortest-path tree using chain shortcuts and sampled-vertex-to-chain shortcuts.Source: §7 · p. 20
• Rooted paths are recovered by following stored links upward from each vertex, with links encoding tree edges or shortcut paths to ancestors.The link rules prioritize a sampled-chain jump for sufficiently deep nodes; the proof bounds the resulting hop count by O(β).Source: §7 · pp. 20–21
• A hopset edge can be expanded into a path using original-graph and lower-level hopset edges, with at most β_(i−1) edges and weight at most (1+δ)d_G(u,v).Preprocessing takes eO((n/β_i)m) time, and queried witness paths can be reported in output-sensitive time.Source: §7 · p. 21

8 Reductions to DAGs due to [HJS26]

• A DAG (1+ε)-hopset algorithm yields a randomized directed-graph (1+3ε)-hopset algorithm with size and time parameters evaluated at m^(1+o(1)) and n^(1+o(1)).The hopbound remains β, with an additional m^(1+o(1)) term in the running time.Source: §8 · p. 22
• A DAG (1+ε)-approximate distance-preserver algorithm similarly yields a randomized directed-graph (1+3ε)-approximate preserver with n^(1+o(1)) size and time parameters.The reduction retains p and σ as demand-pair and source-count parameters and adds m^(1+o(1)) time.Source: §8 · p. 22

• For an n-vertex DAG with nonnegative weights and polynomial aspect ratio, the construction gives a (1+ε)-hopset of size eO(ε^-2 n) and hopbound eO(ε^-1 n^1/3).Source: §9 · pp. 22, 26
• With high probability, the sampled vertex set has size eO(n/β) and hits the first β vertices of every longer fixed shortest path.For sampled chains, earliest-bucket edges from sampled vertices provide a route into the chain.Source: §9 · pp. 22, 24
• At each distance scale, the algorithm forms a maximal family of pairwise vertex-disjoint lightest chains, where lightest chains are shortest paths in the metric closure.The scale-specific families cover nearly all vertices of any sufficiently short lightest chain.Source: §9 · pp. 22–23
• Exact shortcuts add O(h log h) edges per chain and give every pair of its vertices an exact-distance route using at most two hops.Across the disjoint chains, these shortcuts contribute O(n log n) edges per scale.Source: §9 · p. 23
• With chain-sampling probability p = min{1, C log n/β} and κ ≥ β, with high probability the rerouted path has O(κ) hops and weight at most (1+ε+η(1+ε))d_G(s,t).Source: §9 · p. 25
• Once sampled vertices and a disjoint chain family are fixed, one scale's hopset can be generated in eO(|V′|·m+|H_L|) time.The implementation uses one shortest-path computation per sampled source, then scans sampled chains to emit bucket edges.Source: §9 · pp. 25–26

• For the O(n^1/3) hopbound regime, the construction replaces the chain-cover step with a light-chain-cover procedure while retaining the earlier hopset framework.For larger hopbounds, it uses randomly selected portals and subsampling; exact portal shortcuts join portal pairs in at most two hops.Source: §10 · pp. 26–28
• For β∈[n^1/3,n], the section also states a construction with o(n) edges and hopbound β.Source: §10 · p. 27
• The resulting (1+ε)-hopset has hopbound at most O(β) and is computed in eO_ε(n/β·m) time.Source: §10 · p. 29

• The initial version was prepared without AI; AI was later used for reviewer feedback implementation and minor fixes.Source: AI Use Declaration · p. 30