Lemma 5 — Algorithm 3 runs in O(k^{3k}(m+n)n^{1−ε_k}) time
ProvedDirKECC1549.Main.lemma_5directed-graphsedge-connectivitygraph-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1word-ram
There are one word-RAM program and one absolute constant such that for every integer and every directed multigraph with vertices and edges, the program, started on the encoding of , halts within
ticks, and its output labels form a partition that is an output of a run of Algorithm 3 on .
This is the running-time half of Theorem 1, with the dependence on explicit.
Formalization Note is stored in cell , the encoded length is , and the label of is in cell ; is the real power.
Differences from the source:
- generalization: directed graph with parallel edges (p.9) → self-loops also allowed; reason: a loop leaves no vertex set and can be deleted from any path, so it changes no out_D, no λ_D and no component; on loop-free multigraphs the statement is exactly the source's
- 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: running time on the word-RAM (p.25) → ticks of the published word-RAM WordRAM.run (Hagerup's model, multiplication instruction set, one tick per instruction, no native constants); reason: the paper's model is the standard word-RAM; every instruction costs one tick
- encoding: O(·) with explicit dependence on k → one program for all k (k read from memory) and one absolute constant c fixed before every input; reason: an O(·) without subscript hides an absolute constant; the k-dependence is written out
- generalization: O(k^{3k} m n^{1−ε_k}) under the standing assumption that every vertex has an outgoing edge, so m ≥ n (p.9) → c · k^{3k} · (m + n) · n^{1−ε_k} for every multigraph with n ≥ 1; reason: on the paper's domain m + n ≤ 2m, so the bound implies the printed one with constant 2c; it also covers graphs with sinks and repairs the proof's treatment of singleton strongly connected components, which have m_i = 0
- encoding: "Algorithm 3 runs in … time" → one program whose output is the output of some run of Algorithm 3 (the run relation); reason: a running-time claim about an algorithm with free choices, stated for a concrete word-RAM implementation
- encoding: the input graph and k → the edge-list encoding with k in cell 2m + 2, length N = n + 2m + k + 3, remaining cells 0, labels in cells N + v; reason: input/output convention; reading k costs at most k ≤ k^{3k} ticks
- encoding: a directed graph → n ≥ 1; reason: nondegeneracy: Algorithm 3 picks a root r ∈ V (line 9) and the bound vanishes at n = 0
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
/-- Lemma 5, p.18: Algorithm 3 runs in `O(k^{3k}·m·n^{1−ε_k})` time, `ε_k = 2^{−(k−1)}`. One
word-RAM program with `k` in the input and one absolute constant `c`: for every `k ≥ 1` and every
multigraph with `n ≥ 1` vertices and `m` edges, started on the encoding of `(n, m, edges, k)` it
halts within `c·k^{3k}·(m + n)·n^{1−ε_k}` ticks, and its output labels form a partition `P` that
is an output of a run of Algorithm 3 on `(G, k)`. -/
theorem lemma_5 :
∃ (A : Complexity.Algorithm .multiplication) (c : ℝ), 0 < c ∧
∀ (k n m : ℕ) (G : Fin m → Fin n × Fin n), 1 ≤ k → 1 ≤ n →
HaltsWithin A.code (A.width (kInputLength n m k)) (kInput _ n m k G)
(c * (k : ℝ) ^ (3 * k) * ((m + n : ℕ) : ℝ) * (n : ℝ) ^ (1 - eps k))
(fun mem => Alg3Run n m G k (labelRel mem (kInputLength n m k))) := by sorry
end DirKECC1549.Main
Source
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis, STOC 2027 submission #1549 (October 2026), Section 3.3, Lemma 5, p.18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.