Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Incremental directed graph inputs and legal insertion prefixes

Definition
DecrAlmostLinearSSSP_Decremental_Supplement_Input

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-shortest-pathsgraph-theoryincrementalp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let V={0,…,n−1}V=\{0,\ldots,n-1\}V={0,…,n−1} be a finite nonempty vertex set, let s∈Vs\in Vs∈V be the source, and give each original directed edge its own identifier in {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}. Its tail, head and real weight w(e)w(e)w(e) are fixed. The initial graph is a duplicate-free list E0E_0E0​; a legal insertion list e1,…,ete_1,\ldots,e_te1​,…,et​ has no repeated identifier and is disjoint from E0E_0E0​. At that prefix the active graph and its distance are

Et=E0∪{e1,…,et},dt(v)=inf⁡P:s⇝v, P⊆Et∑e∈Pw(e).E_t=E_0\cup\{e_1,\ldots,e_t\},\qquad d_t(v)=\inf_{P:s\leadsto v,\ P\subseteq E_t}\sum_{e\in P}w(e).Et​=E0​∪{e1​,…,et​},dt​(v)=P:s⇝v, P⊆Et​inf​e∈P∑​w(e).

Validity means n,k≤mn,k\le mn,k≤m, W≥1W\ge1W≥1, 0<ϵ≤10<\epsilon\le10<ϵ≤1, and 1≤w(e)≤W1\le w(e)\le W1≤w(e)≤W for every identifier. A separate integrality predicate requires integer edge weights only when used; the numerical upper bound WWW remains real. Source membership supplies nonemptiness. Parallel edges, loops, edges entering the source, arbitrary initial reachability and empty insertion lists remain admissible.

These incremental wrappers reuse the published general directed graph, walk, extended distance and reachability definitions. They do not use any deletion-specific legality or live-edge convention. Extended nonnegative distances give infinity exactly when no walk exists for valid finite weights. The full future graph is specification data; the execution protocol exposes only initially active edges and then the current inserted edge.

Definition code
import Definitions.Def_DecrAlmostLinearSSSP_Decremental_Graph

set_option autoImplicit false
open scoped ENNReal NNReal

namespace DecrAlmostLinearSSSP.Decremental.Supplement

/-- Specification of an incremental instance. The graph includes potential future identifiers,
but the initialization tape below exposes only `initial`. Parallel edges and loops are allowed.
Real weights are needed by the black-box Lemma 5.1. -/
structure Instance where
  n : ℕ
  k : ℕ
  graph : Digraph n k
  source : Fin n
  weight : Fin k → ℝ
  initial : List (Fin k)
  size : ℕ
  W : ℝ
  accuracy : ℝ

def Instance.Valid (i : Instance) : Prop :=
  i.n ≤ i.size ∧ i.k ≤ i.size ∧ i.initial.Nodup ∧ 1 ≤ i.W ∧
  0 < i.accuracy ∧ i.accuracy ≤ 1 ∧ ∀ e, 1 ≤ i.weight e ∧ i.weight e ≤ i.W

/-- Integrality concerns edge lengths only; the numerical upper bound W may be real. -/
def Instance.Integral (i : Instance) : Prop :=
  ∀ e, ∃ w : ℕ, i.weight e = (w : ℝ)

def Instance.Legal (i : Instance) (es : List (Fin i.k)) : Prop :=
  (i.initial ++ es).Nodup

def Instance.active (i : Instance) (es : List (Fin i.k)) : Finset (Fin i.k) :=
  (i.initial ++ es).toFinset

noncomputable def Instance.dist (i : Instance) (es : List (Fin i.k)) (v : Fin i.n) : ℝ≥0∞ :=
  distance i.graph (i.active es) (fun e => ENNReal.ofReal (i.weight e)) i.source v

def Instance.reachable (i : Instance) (es : List (Fin i.k)) (v : Fin i.n) : Prop :=
  Reachable i.graph (i.active es) i.source v

end DecrAlmostLinearSSSP.Decremental.Supplement
Source
Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang, STOC 2027 submission #912 (October 2026), pp.1, 3–4, 18, 31, incremental graph convention and Lemmas 4.1, 5.1

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me