Theorem 1 — k-edge-connected components in O_k(m n^{1−ε_k}) time, ε_k = 2^{−(k−1)}
ProvedDirKECC1549.Main.theorem_1Let be a fixed integer and . There are a deterministic word-RAM program and a constant , both depending only on , such that for every directed multigraph with vertices and edges, started on the encoding of the program halts within
ticks, and its output assigns to every vertex a label such that two vertices receive the same label if and only if they are -edge-connected in .
For the bound is at most , so this is the paper's algorithm for the -edge-connected components, the first improvement on for every fixed (for it is the linear-time computation of strongly connected components).
Formalization Note The input is the edge-list encoding (, , then tail and head of each edge; every other cell ) of length , the word width is the program's width at , and the label of is the word in cell . 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
import Mathlib import Definitions.Def_DirKECC1549_Main_Machine import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false open WordRAM
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.