Linear-time word-RAM reverse-search forest with decreasing ranks
OpenDirKECC1549.Main.reverse_search_forest_programFor every finite directed multigraph and root , a single multiplication word-RAM program computes parent pointers in ticks for the vertices that can reach . The root is its own parent. Every other vertex that reaches has a parent joined by an edge from that vertex, and its parent also reaches . There is a natural-number rank that strictly decreases on each such parent step. No correctness requirement is imposed on the parents of vertices that cannot reach , beyond being valid vertex identifiers.
The input is the published graph layout with arbitrary natural parameters and the root stored in parameter cells. The program preserves that layout and all three parameters, and writes parent identifiers in the designated array. One program and one positive absolute linear-time constant work for all graphs and all word widths allowed by its polynomial capacity, with arbitrary other initial memory. This is a general reverse graph-search implementation contract; unlike the in-tree subroutine, it does not assume every vertex reaches the root.
import Definitions.Def_DirKECC1549_Main_HittingSet import Definitions.Def_DirKECC1549_Main_Machine set_option autoImplicit false open WordRAM
namespace DirKECC1549.Main
theorem reverse_search_forest_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) (rank : Fin n → ℕ), par r = r ∧
(∀ v, Reach G v r → v ≠ r →
(∃ e, G e = (v, par v)) ∧ Reach G (par v) r ∧ rank (par v) < rank v) ∧
∀ v : Fin n, (mem (arrayCell n m v)).toNat = par v) := by sorry
end DirKECC1549.Main