Linear-time word-RAM construction of a spanning in-tree
OpenDirKECC1549.Main.hitting_in_tree_programdirected-graphsgraph-algorithmsword-ram
There exist a fixed multiplication word-RAM program and a positive absolute constant c that construct a spanning in-tree rooted at r in at most c(m+n) ticks whenever every vertex reaches r. The input is the graph layout with n≥2, k≥2, Δ≥1 and the root in parameter cells. The output stores each vertex's parent in cell 6B+v, preserving the graph layout and parameter cells. The contract covers every sufficiently wide word and arbitrary remaining initial memory.
Preamble
import Definitions.Def_DirKECC1549_Main_HittingSet import Definitions.Def_DirKECC1549_Main_Machine set_option autoImplicit false open WordRAM
Formal statement
namespace DirKECC1549.Main
theorem hitting_in_tree_program :
∃ (A : Complexity.Algorithm .multiplication) (c : ℝ), 0 < c ∧
∀ (n m : ℕ) (G : Fin m → Fin n × Fin n) (k Δ : ℕ) (r : Fin n),
2 ≤ k → 1 ≤ Δ → 2 ≤ n → (∀ v, Reach G v r) →
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, IsSpanningInTree G r par ∧
∀ v : Fin n, (mem (arrayCell n m v)).toNat = par v)) := by sorry
end DirKECC1549.Main
Source
Derived implementation obligation for Georgiadis, Kipouridis, Kosinas, Papadopoulos and Pergaminelis, STOC 2027 submission #1549, Section 3.2.1, Algorithm 2 and Lemma 2, pp. 13–14.