Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

SCC: correctness and uniform linear running time

Proved
CLRS.SCC.scc_correctness_and_running_time

by Chutong · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgorithmsclrsgraph-theoryrunning-timetextbook

There is one positive natural constant C, uniform over all graph data, input heaps, and initial counters, such that the displayed SCC program terminates and returns a fresh exact partition into strongly connected components with preserved caller storage and

T≤C(1+n+m).T\le C(1+n+m).T≤C(1+n+m).

Equal labels are equivalent to mutual reachability in the original graph; labels are contiguous and all used, but their numeric values are not canonical. Empty and disconnected graphs, parallel arcs, and self-loops are included. The bound covers both DFS passes and graph preparation. This is an open task; no correctness or runtime proof is supplied.

Preamble
import Definitions.Def_CLRS_SCC_Program

set_option autoImplicit false

open Algo2LeanGenerated CLRS.GraphTraversal CLRS.SCC
Formal statement
theorem CLRS.SCC.scc_correctness_and_running_time :
    ∃ C : Nat, 0 < C ∧
      ∀ (before : Heap) (graph : ObjectRef) (g : Graph),
        GraphRep before graph g →
        ∃ after result,
          Algo.scc.scc.Call before graph after result ∧
          Post before after result g ∧
          work before after ≤ C * (1 + g.size + edgeCount g) := by
  sorry
Source
CLRS, Introduction to Algorithms, fourth edition (MIT Press, 2022), Chapter 20, §20.5. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ ; new arrays-of-arrays implementation compiled with Algo2Lean v0.1.4, https://www.algo2lean.com/versions/v0.1.4/ . Source filenames and full code are in the mission description.
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex, independent fresh-context agent)

There exists one positive natural-number constant CCC, chosen before and independently of every initial heap, graph object reference, graph, size, adjacency list, and initial clock, with the following property. Let ggg be a finite directed multigraph with nnn vertices numbered 0,…,n−10,\ldots,n-10,…,n−1, whose adjacency lists contain only these vertices, and let mmm be the sum of the lengths of these nnn lists, counting parallel occurrences and self-loops. Its rows at other natural-number indices are irrelevant. A represented input consists of an arbitrary initial heap HHH and a natural-number object reference rrr below its object-allocation counter, of class graph_input.UnweightedGraph, with integer size field nnn, a valid allocated outer collection tagged Seq[Int], and an allocated integer-array reference for degrees. For each vertex uuu, the degree entry equals the length of ggg's adjacency list at uuu, the outer collection entry decodes to an allocated integer-array reference, and that array's declared prefix equals that list entry by entry. Arrays are total functions from integers to integers; values outside the declared prefixes are unrestricted, and the input arrays may alias. For every such represented input there exist a final heap H′H'H′ and result reference qqq for a completed call of scc on rrr, satisfying all the following requirements together. A completed call means that, for every suspended caller stack, some finite sequence of the specified program transitions takes the entry frame with heap HHH to the return configuration with the same chosen final heap H′H'H′ and result reference qqq; for an empty stack this is a completed top-level return. Thus the final heap and result can depend on the input but are chosen uniformly over caller stacks; the transcript may depend on the stack. This is existence of these completed executions, not a separately stated universal property of all possible runs. The returned qqq is an allocated object of class dfs.DFSResult, fresh in the sense that its reference is at least HHH's initial object counter and below H′H'H′'s final object counter. Its component field names an allocated integer array with reference at least HHH's initial array counter and below H′H'H′'s final array counter, and its integer components field equals a natural number k≤nk\le nk≤n. One has k=0k=0k=0 if and only if n=0n=0n=0. Every valid vertex's component value is an integer in {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, and every natural label less than kkk occurs at some valid vertex. For every pair of valid vertices u,vu,vu,v, their component values are equal if and only if there is a finite directed walk in the original graph from uuu to vvv and a finite directed walk from vvv to uuu; walks may repeat vertices and include the zero-edge walk at a valid vertex. Thus the stated equivalence uses the original graph and both directions of reachability. The postcondition gives no canonical numbering of labels, no constraint on the component array outside valid vertices, and no mathematical requirements on the returned object's other fields. Preservation means that every integer array below HHH's initial array-allocation counter is unchanged at every integer index, every initially allocated object and typed collection is unchanged in full, all three allocation counters do not decrease, the natural-number graph_work clock does not decrease, and every differently named clock is exactly unchanged. The work of this same call is at most C(1+n+m)C(1+n+m)C(1+n+m). Work is the final graph_work clock minus its initial value, using natural-number subtraction; the preservation requirement makes this an ordinary nonnegative increment. It counts only explicit unit markers in the transition rules, including nested calls, from the caller's actual initial clock; it is not the number of transitions, elapsed time, bit complexity, or a bound on memory use. The empty graph is included: the input still needs its allocated graph object, valid outer collection, and allocated degree array, while the output still needs a fresh result object and fresh component array, with component count zero and vacuous vertex-label conditions. The supplied declaration ends in sorry; this is the proposition of an open proof goal, not a proved algorithm-correctness result.

Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Chutong · Oct 15, 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