Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A fixed charged-interpreter program for induced connected components

Proved
StableMSR.Recovery.Compiler.ComponentProgram.component_traversal_program

by lreyzin · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmsformal-verificationgraph-theory

There is a single deterministic program with 46 instructions that computes an induced connected component from an ordinary encoded graph input. Let GGG be a simple graph on nnn vertices, let AAA be an allowed vertex set, and let s∈As\in As∈A be a seed. The input contains a directed edge list of length mmm representing all adjacencies in both orientations, a zero–one bitmap for AAA, the relevant array addresses and counts, and the seed index. The writable reached bitmap is disjoint from the read-only input arrays, and its initial contents are arbitrary.

The program clears the reached bitmap, marks the seed, and scans the edge array nnn times. Its exact charged running time, including initialization, branches, loop tests, and halt, is

T(n,m)=n(17m+11)+15.T(n,m)=n(17m+11)+15.T(n,m)=n(17m+11)+15.

At termination, the reached cell for a vertex vvv is exactly 111 if there is a walk from sss to vvv whose support is contained in AAA, and 000 otherwise. Every integer cell outside this bitmap is preserved, as are all real registers and real memory, the input address/count/seed registers, the oracle-query count, and the random-tape position. The theorem holds for every oracle and tape, even when the initial work counter is nonzero.

The edge order is arbitrary and repeated arcs are allowed. For a representation with m≤n2m\le n^2m≤n2, the exact formula is at most 43n343n^343n3 (a valid seed implies n≥1n\ge1n≥1). This is a verified internal component subroutine for decomposition search. Building the graph from metric input, composing the search and dynamic program, and proving the full clustering recovery program remain separate obligations. No component or solution certificate is supplied as input.

Preamble
import Definitions.Def_StableMSR_ComponentGraphMemory
import Mathlib.Combinatorics.SimpleGraph.Walk.Basic
open scoped Classical
open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.ComponentMemory
Formal statement
theorem StableMSR.Recovery.Compiler.ComponentProgram.component_traversal_program :
    ∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 46 ∧
    ∀ (n : ℕ) (d : Point n → Point n → ℝ) (G : SimpleGraph (Fin n))
      (A : Finset (Fin n)) (es : List (Fin n × Fin n)) (seed : Fin n) (s : Store),
      GraphInput s A es seed → seed ∈ A →
      (∀ e ∈ es, G.Adj e.1 e.2) →
      (∀ u v, G.Adj u v → (u,v) ∈ es) →
      ∀ (ω : ℕ → ℝ) (work : ℕ),
      let result := (MinSumFPT.step P d ω)^[n*(17*es.length+11)+15] (s.state 0 work)
      result.halted = true ∧ result.work = work+(n*(17*es.length+11)+15) ∧
      result.queries = s.queries ∧ result.tapePos = s.tapePos ∧
      result.cfg.mem = s.mem ∧ result.cfg.regs = s.regs ∧
      (∀ v : Fin n, result.imem (address (s.ptrs 4) v) =
        if (∃ p : G.Walk seed v, ∀ z ∈ p.support, z ∈ A) then 1 else 0) ∧
      (∀ v : Fin n, 0 < result.imem (address (s.ptrs 4) v) ↔
        ∃ p : G.Walk seed v, ∀ z ∈ p.support, z ∈ A) ∧
      (∀ x : ℤ, (∀ v : Fin n, x ≠ address (s.ptrs 4) v) → result.imem x = s.imem x) ∧
      (∀ j : ℕ, (2 ≤ j ∧ j ≤ 6 ∨ j = 17) → result.cfg.ptrs j = s.ptrs j) := by sorry
Source
Exact Sum-of-Radii Clustering under Any Constant Stability, Prove2Me mission 11d3e3d6-df23-4c6a-8fd7-fbb629791a9b; executable graph primitive supporting rational_recovery_program (c2468a82-f9f1-431f-bb25-e0e414912c4f).

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