Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — k-edge-connected components in O_k(m n^{1−ε_k}) time, ε_k = 2^{−(k−1)}

Proved
DirKECC1549.Main.theorem_1

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

directed-graphsedge-connectivitygraph-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1word-ram

Let k≥1k\ge1k≥1 be a fixed integer and εk=2−(k−1)\varepsilon_k=2^{-(k-1)}εk​=2−(k−1). There are a deterministic word-RAM program and a constant C>0C>0C>0, both depending only on kkk, such that for every directed multigraph GGG with nnn vertices and mmm edges, started on the encoding of GGG the program halts within

C (m+n+1) (n+1)1−εkC\,(m+n+1)\,(n+1)^{1-\varepsilon_k}C(m+n+1)(n+1)1−εk​

ticks, and its output assigns to every vertex a label such that two vertices receive the same label if and only if they are kkk-edge-connected in GGG.

For m≥n≥1m\ge n\ge1m≥n≥1 the bound is at most 6C m n1−εk6C\,m\,n^{1-\varepsilon_k}6Cmn1−εk​, so this is the paper's Ok(mn1−εk)O_k(mn^{1-\varepsilon_k})Ok​(mn1−εk​) algorithm for the kkk-edge-connected components, the first improvement on O(mn)O(mn)O(mn) for every fixed k≥5k\ge5k≥5 (for k=1k=1k=1 it is the linear-time computation of strongly connected components).

Formalization Note The input is the edge-list encoding (nnn, mmm, then tail and head of each edge; every other cell 000) of length N=n+2m+3N=n+2m+3N=n+2m+3, the word width is the program's width at NNN, and the label of vvv is the word in cell N+vN+vN+v. (n+1)1−εk(n+1)^{1-\varepsilon_k}(n+1)1−εk​ is the real power.

Differences from the source:

  • generalization: m · n^{1−ε_k} and the standing assumption "every vertex has at least one outgoing edge, and thus m ≥ n" (p.9) → (m + n + 1) · (n + 1)^{1−ε_k} for every multigraph; reason: for n ≥ 1 and m ≥ n we have m + n + 1 ≤ 3m and (n + 1)^{1−ε_k} ≤ 2n^{1−ε_k}, so the Lean bound implies the printed one with constant 6C; it also covers graphs with sinks, isolated vertices and n = 0
  • generalization: directed graph with parallel edges (p.9) → self-loops also allowed; reason: a loop leaves no set, so it changes no λ and no component; on loop-free multigraphs the statement is exactly the source's
  • encoding: "computed" → returns component labels, equal iff k-edge-connected; reason: the paper's own meaning (§5.3, p.26: "returns, for every vertex, a component label, such that two vertices receive the same label if and only if they belong to the same k-edge-connected component")
  • encoding: "time" → ticks of the published word-RAM (WordRAM.run), multiplication model, word width ⌊log₂(C′(N+1)^D + N + 16)⌋ + 1 for the program's own constants C′, D; reason: the paper's model is the word-RAM (p.25, "in the word-RAM model"), and every instruction costs one tick
  • encoding: vertex set V and edge multiset E → vertices Fin n, edge ids Fin m, an edge map Fin m → Fin n × Fin n; reason: Lean convention; parallel edges are distinct ids, so every count includes multiplicities as on p.9; same instances
  • encoding: edge-disjoint directed paths; λ_D(u,v) ≥ k → pairwise edge-disjoint trails (walks using no edge id twice); λ ≥ k as "k such trails exist"; reason: edge-disjoint walks shorten to edge-disjoint paths, so the counts agree
  • encoding: O_k(·) → a program and a constant C chosen after k and before the graph; reason: O_k hides a factor depending only on k (p.9)
  • encoding: the input graph (no encoding fixed by the paper) → cell 0 = n, cell 1 = m, cells 2 + 2e and 3 + 2e = tail and head of edge e, every other cell 0, input length N = n + 2m + 3, label of v in cell N + v; reason: input/output convention of the word-RAM statement; it holds every instance and counts n so vertex ids fit a word
Preamble
import Mathlib
import Definitions.Def_DirKECC1549_Main_Machine
import Definitions.Def_DirKECC1549_Main_Alg3

set_option autoImplicit false

open WordRAM
Formal statement
namespace DirKECC1549.Main

/-- Theorem 1, p.19 (also p.2): for every fixed integer `k ≥ 1` the `k`-edge-connected components
of a directed multigraph with `n` vertices and `m` edges can be computed in `O_k(m·n^{1−ε_k})`
time, `ε_k = 2^{−(k−1)}`. For each `k` there are one word-RAM program and one constant `C`
(depending only on `k`) such that, on the encoding of any `(n, m, edges)`, the program halts
within `C·(m + n + 1)·(n + 1)^{1−ε_k}` ticks with labels in cells `N + v` (`N = n + 2m + 3`)
that are equal exactly for `k`-edge-connected vertices. -/
theorem theorem_1 (k : ℕ) (hk : 1 ≤ k) :
    ∃ (A : Complexity.Algorithm .multiplication) (C : ℝ), 0 < C ∧
      ∀ (n m : ℕ) (G : Fin m → Fin n × Fin n),
        HaltsWithin A.code (A.width (inputLength n m)) (goalInput _ n m G)
          (C * ((m + n + 1 : ℕ) : ℝ) * ((n + 1 : ℕ) : ℝ) ^ (1 - eps k))
          (fun mem => ∀ u v : Fin n,
            labelRel mem (inputLength n m) u v ↔ KEdgeConnected k G u v) := by sorry

end DirKECC1549.Main
Source
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis, STOC 2027 submission #1549 (October 2026), Theorem 1, p.19 (also stated on p.2); output convention of Section 5.3, p.26
Human review
  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

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