Linear-time word-RAM hitting set for an encoded in-tree
OpenDirKECC1549.Main.hitting_tree_scan_programdirected-graphsgraph-algorithmsword-ram
There exist a fixed multiplication word-RAM program and a positive absolute constant c that, given a spanning in-tree encoded in the parent array, compute Algorithm 2's hitting set for that same tree within c(m+n) ticks. The input also contains the graph layout, n≥2, k≥2, Δ≥1, and the root. Weights are graph outdegrees and the threshold is floor(Δ/(k−1)). Output is the indicator in cells 7B+v. The contract quantifies over every allowed word width 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_tree_scan_program :
∃ (A : Complexity.Algorithm .multiplication) (c : ℝ), 0 < c ∧
∀ (n m : ℕ) (G : Fin m → Fin n × Fin n) (k Δ : ℕ) (r : Fin n)
(par : Fin n → Fin n),
2 ≤ k → 1 ≤ Δ → 2 ≤ n → IsSpanningInTree G r par →
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) ∧
∀ v : Fin n, (mem (arrayCell n m v)).toNat = par v)
(c * ((m + n : ℕ) : ℝ))
(fun _ mem => ∀ v : Fin n, (mem (outCell n m v)).toNat =
if v ∈ hittingSet r par (outDeg G) (Δ / (k - 1)) then 1 else 0) := 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.