Output of FindOutPaths after all blocks
ProvedDirKECC1549.Asm.fopRun_outalgorithm-implementationdirected-graphsedge-connectivityprogram-verificationword-ram
If all blocks completed without stopping, the slots satisfy the output guarantee FopOut.
Context. This lemma belongs to the machine-checked word-RAM implementation of Lemma 1 (p.11): Algorithm 1 refining by small -out sets, with the deterministic local search of [GKK+26, Proposition 6] (FindOutPaths and recursive path reversals). The program is written in the structured language Stmt compiled to the published word-RAM; Run E s mem Q states that the statement s, started on mem, reaches its end in a state satisfying Q t mem' within t ticks. The input cells double as registers; they are saved at SV and read through the image ImgAt. All definitions are in the Definitions.Def_DirKECC1549_Impl_* modules.
Preamble
import Definitions.Def_DirKECC1549_Impl_L1Fop4
set_option autoImplicit false
open WordRAM Classical Finset
open DirKECC1549.Main DirKECC1549.Main.CostAux
open DirKECC1549 DirKECC1549.Asm
variable {w : Width} {n m : ℕ}Formal statement
theorem DirKECC1549.Asm.fopRun_out (hm : 0 < m) (P : LP) (B : Fin m → Fin n × Fin n) (perm : Equiv.Perm (Fin m))
(F : Finset (Fin m)) (v s : Fin n) (pe0 : Fin n → Fin m) (adj : Fin n → List (Fin m)) (D nb j SA : ℕ)
(tb : ℕ → ℕ) (mm : Memory w) (hA : AdjOK (flipEdges B F) adj)
(hR : FopRun hm P B perm F v s pe0 adj D SA (n + 1) mm nb tb) :
FopOut P (flipEdges B F) v s D nb j SA mm := by sorrySource
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis, STOC 2027 submission #1549 (October 2026), Section 3.1, Lemma 1 and Algorithm 1 (pp.10–12), using Proposition 6 of [GKK+26] (deterministic local search); word-RAM model of Hagerup (p.25). Implementation-level lemma of the verified program for Lemma 1.