Linear-time Word-RAM reverse search with a local discovery certificate
OpenDirKECC1549.Main.reverse_search_discovery_programFor a finite directed multigraph with n vertices and m edges, and a root r, a single multiplication Word-RAM program returns parent pointers and admits a finite discovery-list certificate L. The list is a mathematical witness; it need not be stored in the output.
The parent of r is r. The list has no repeated vertices, contains r, and is closed under incoming edges:
For every vertex v in L other than r, its parent occurs strictly before the first occurrence of v in L and is joined to it by an original graph edge:
Every vertex, including those outside L, has a valid parent identifier written into the designated parent array. No claim involving graph reachability or an externally supplied rank function is assumed in this certificate.
One fixed program, one polynomial capacity function, and one positive absolute constant c work for all graphs, roots, arbitrary natural parameters k and Delta, and all admissible word widths. The program halts within c(m+n) ticks, preserves the graph layout and all three scalar parameters, and tolerates arbitrary initial contents of other cells. The input-size parameter is 8(n+2m+3)+k+Delta, exactly as in the parent forest contract.
This local discovery certificate separates the machine implementation of reverse exploration from the graph-theoretic proof of reachability and decreasing parent ranks.
import Definitions.Def_DirKECC1549_Main_Machine set_option autoImplicit false open WordRAM
namespace DirKECC1549.Main
theorem reverse_search_discovery_program :
∃ (A : Complexity.Algorithm .multiplication) (c : ℝ), 0 < c ∧
∀ (n m : ℕ) (G : Fin m → Fin n × Fin n) (k Δ : ℕ) (r : Fin n),
Implements A (8 * blk n m + k + Δ)
(fun _ mem => GraphLayout G mem ∧ (mem (paramCell n m 0)).toNat = k ∧
(mem (paramCell n m 1)).toNat = Δ ∧ (mem (paramCell n m 2)).toNat = r)
(c * ((m + n : ℕ) : ℝ))
(fun _ mem => (GraphLayout G mem ∧ (mem (paramCell n m 0)).toNat = k ∧
(mem (paramCell n m 1)).toNat = Δ ∧ (mem (paramCell n m 2)).toNat = r) ∧
∃ (par : Fin n → Fin n) (order : List (Fin n)), par r = r ∧
order.Nodup ∧ r ∈ order ∧
(∀ e : Fin m, (G e).2 ∈ order → (G e).1 ∈ order) ∧
(∀ v ∈ order, v ≠ r →
(∃ e, G e = (v, par v)) ∧ par v ∈ order.take (order.idxOf v)) ∧
∀ v : Fin n, (mem (arrayCell n m v)).toNat = par v) := by sorry
end DirKECC1549.Main