Linear-time word-RAM implementation of the hitting set
ProvedDirKECC1549.Main.hitting_set_linear_programdirected-graphsedge-connectivity
There exist a single multiplication word-RAM program and a positive absolute constant such that, for every directed multigraph with vertices, every , and root reachable from every vertex, the program computes the indicator of Algorithm 2's hitting set for some spanning in-tree rooted at within ticks. The graph and parameters use the published graph-layout and subroutine contracts. The word width and memory contents are quantified as specified by that contract.
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_set_linear_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 => ∃ par : Fin n → Fin n, IsSpanningInTree G r par ∧
∀ 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 supporting statement for Georgiadis, Kipouridis, Kosinas, Papadopoulos, Pergaminelis, STOC 2027 submission #1549, Section 3.2.1, Algorithm 2 and Lemma 2, pp. 13–14.