Definition 3 — -pivot -hop -stretch approximate distance oracles
DefinitionPivotADO_OneHop_Supplement_HopOracleLet be an undirected, unweighted simple graph with shortest-path distance . Let be integers and . An -pivot -hop -stretch ADO for consists of
- a weighted undirected graph with for every , where by convention and for with ;
- a set of at most pivots for every , with ,
such that for all ,
Here is the minimum of
over all , all vertices , and all pivots , and , where and . This is the weight of the walk with stored hops; the pivot jumps do not count as hops. The space of the oracle is .
This model is the object of Theorem 2; for it is the one-hop model of the mission's goal.
Formalization Note reuses the published WeightedGraph (a simple graph with symmetric edge weights) and its weight, which supplies the conventions and off stored edges. With , , the cost is written as , which equals (5.5) because is symmetric; the vertices and pivots are indexed by , and the unused entries , range over the (nonempty) pivot sets. The minimum is an infimum in over this finite family. Stored edges may carry weight ; they are counted in the space.
import Definitions.Def_PivotADO_OneHop_WeightedGraph
set_option autoImplicit false
open scoped Classical ENNReal
noncomputable section
namespace PivotADO.OneHop.Supplement
open PivotADO.OneHop
/-! Definition 3 (r-pivot β-hop k-stretch ADO), Kadria–Roditty, STOC 2027 submission
#584 (October 2026), p.20 (PDF 21), equation (5.5). -/
/-- The weight (5.5) of the walk
`u = x₀ → p'_{x₀} → p_{x₁} → x₁ → p'_{x₁} → ⋯ → p_{x_j} → x_j = v`
with `j` stored hops `p'_{x_i} → p_{x_{i+1}}`. Here `pout i = p'_{x_i}` and
`pin i = p_{x_i}`; the values `pin 0` and `pout (Fin.last j)` are not used.
Every summand uses the stored weight `w_H` (zero on the diagonal, `⊤` off stored edges).
Since `w_H` is symmetric, this is exactly the sum (5.5). -/
def hopWalkCost {V : Type*} (H : WeightedGraph V) {j : ℕ}
(x pin pout : Fin (j + 1) → V) : ℝ≥0∞ :=
∑ i : Fin j, (H.weight (x i.castSucc) (pout i.castSucc) +
H.weight (pout i.castSucc) (pin i.succ) + H.weight (pin i.succ) (x i.succ))
/-- `d^{≤β}_{H,P}(u, v)`: the minimum of (5.5) over `1 ≤ j ≤ β`, intermediate vertices
`x₁, …, x_{j−1}` and pivots `p_{x_i}, p'_{x_i} ∈ P(x_i)` (which may differ), with
`x₀ = u`, `x_j = v`. -/
def hopEstimate {V : Type*} (H : WeightedGraph V) (pivots : V → Finset V) (β : ℕ)
(u v : V) : ℝ≥0∞ :=
⨅ (j : ℕ) (_ : 1 ≤ j ∧ j ≤ β) (x : Fin (j + 1) → V)
(_ : x 0 = u ∧ x (Fin.last j) = v) (pin : Fin (j + 1) → V) (pout : Fin (j + 1) → V)
(_ : ∀ i, pin i ∈ pivots (x i) ∧ pout i ∈ pivots (x i)),
hopWalkCost H x pin pout
/-- An r-pivot β-hop k-stretch ADO for `G` (Definition 3). The space of the oracle is
`edgeCount storage.graph`, counting every stored edge (including any of weight `⊤`). -/
structure HopOracle {V : Type*} (G : SimpleGraph V) (r β : ℕ) (k : ℝ) where
storage : WeightedGraph V
pivots : V → Finset V
self_mem : ∀ v, v ∈ pivots v
card_le : ∀ v, (pivots v).card ≤ r
dominates : ∀ u v, storage.graph.Adj u v → distance G u v ≤ storage.weight u v
bounds : ∀ u v, distance G u v ≤ hopEstimate storage pivots β u v ∧
hopEstimate storage pivots β u v ≤ ENNReal.ofReal k * distance G u v
end PivotADO.OneHop.Supplement