Edge connectivity measures how robust a network is against link failures. In a directed graph, two vertices are -edge-connected when pairwise edge-disjoint directed paths run from each to the other; this relation is an equivalence, and its classes, the -edge-connected components, describe which groups of vertices survive the deletion of any edges with mutual reachability intact. Computing them is a basic primitive in network reliability and in decomposition-based graph algorithms; for they are the strongly connected components.
Timeline, as summarized in the source paper (pp.2–3):
A directed multigraph has vertex set and edges with identities ; edge goes from its tail to its head. Parallel edges are distinct, so every count includes multiplicities. The reverse graph reverses every edge.
For , is the number of edges leaving , and the out-volume is the sum of the out-degrees of the vertices of . A -out set satisfies and . A -cut is a set containing and not .
For distinct , is the maximum number of pairwise edge-disjoint directed paths from to . Then
and is the partition into its classes. Two vertices are -connected if no -out set of out-volume at most , in or in , contains exactly one of them.
Two vertices are -vertex-connected if deleting any set of fewer than other vertices leaves them mutually reachable. The -vertex-connected components are nonempty inclusion-maximal pairwise -vertex-connected sets; -blocks additionally have size at least . For the undirected results, replace mutual reachability by connectivity.
The algorithm of the paper (Algorithm 3) is recursive: it handles and directly, recurses on strongly connected components, and otherwise combines a recursive call for , a refinement by small cuts (Lemma 1), a deterministic hitting set for large cuts (Lemma 2), and bounded Ford–Fulkerson flows with recursive calls on residual graphs (Lemma 3).
Running time is measured on the word-RAM: memory cells hold -bit words with for input length , and every instruction (addition, subtraction, multiplication, shifts, bitwise operations, comparisons, direct and indirect loads and stores, jumps) costs one tick.
The introduction presents five main results: general edge components (refTheorem 1), the stronger four-edge bound (refTheorem 2), witness cuts (refTheorem 3), vertex components (refTheorem 4), and a vertex-connectivity oracle (refTheorem 5). The platform allows one goal, so Theorem 1 is the goal and Theorems 2–5 are milestones of equal standing.
For every fixed integer there are a deterministic word-RAM program and a constant such that, on every directed multigraph with vertices and edges, the program halts within
steps and labels every vertex so that two labels agree exactly when the vertices are -edge-connected. On the paper's domain () this is .
§3.2.1 — Four-edge connectivity
§4 — Witness cuts
§5 — Vertex-connectivity oracles
§6.1–6.4 — Blocks and vertex-connected components
§6.5 — Undirected component bounds
The theorem gives the first deterministic algorithm for -edge-connected components of directed graphs for every fixed , and the first deterministic bound for follows from Lemma 2 (Theorem 2 of the paper). The same machinery yields the paper's oracle for witness -out sets and its algorithms for -vertex-connected components, all downstream of Theorem 1.
The result is proved in the source but has no machine-checked proof. This mission produces a formal library of edge connectivity in directed multigraphs (edge-disjoint paths, cuts, out-volumes, Menger's theorem in its edge version, components, induced subgraphs), a precise word-RAM complexity statement built on the published word-RAM model of the platform, and a checked analysis of a recursive algorithm whose correctness and running time are proved by joint induction on .
The obvious approach, testing all pairs with rounds of augmenting paths, costs per root and gives no improvement. Algorithm 3 calls itself on , on residual graphs with parameter , and on strongly connected components, and a single level already costs more than linear time; the total must still stay below . The exponent arises only from this recursion, so every piece must carry its exact dependence on , , and .
The formal difficulty is equally concrete. The time bounds are statements about one fixed program on a concrete machine, not about an abstract algorithm with a cost function. Lemma 1 and the local search run in time sublinear in , so they presuppose adjacency arrays and constant-time access to uninitialized memory. The local search is cited from [GKK+26] and must be formalized from that source.
The graph is an edge map Fin m → Fin n × Fin n; parallel edges and self-loops are allowed. Paths are lists of edge ids forming walks without repeated edge ids; "" means that pairwise edge-disjoint such paths exist. A partition is its equivalence relation, and the common refinement is the conjunction.
The machine is the published word-RAM (WordRAM_Complexity_Programs over WordRAMEquivalence_Foundation1), multiplication instruction set, one tick per instruction, no native constants, word width for the program's own constants. The input stores , and the tail and head of every edge, with every other cell , and has length ; the label of vertex is the word in cell . Subroutine statements (Lemmas 1–3, local search) assume a fixed graph layout already in memory (edge list, sorted out- and in-adjacency arrays with offsets), arbitrary content elsewhere, and hold at every sufficiently large word width.
Constants are explicit. without subscript is one absolute constant fixed before every input, with read from memory; is a constant chosen after and before the graph. Algorithm 3 is an inductive run relation following lines 1–14, nondeterministic in the root, in the outputs of Lemmas 1 and 2 (any output meeting their guarantees) and in the augmenting paths.
The goal cannot be trivialized: it asserts the existence of a program whose actual tick count is bounded and whose labels are correct in both directions. A correct labeling without a time bound, a bound without correctness, a cost supplied by the prover, or an oracle instruction does not prove it. Lemma 4 quantifies over all runs, and Lemma 5's existence clause guarantees that runs exist.
Contributions are welcome at every level: the edge-connectivity library (reusable for any flow or cut statement on multigraphs), word-RAM implementations of depth-first search, strongly connected components and radix sort with proved tick bounds (reusable for any algorithmic mission on the published word-RAM), and the formalization of the [GKK+26] local search.
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
Let 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:
No open leaves. Every sub-goal is proved or awaiting decomposition.