Sequential composition of in-tree and hitting-set word-RAM programs
ProvedDirKECC1549.Main.hitting_program_composedirected-graphsgraph-algorithmsword-ram
Suppose two fixed multiplication word-RAM programs satisfy the stated linear-time contracts for constructing a spanning in-tree while preserving the graph layout and parameters, and for computing the hitting set from that encoded tree. Then a single multiplication word-RAM program satisfies the combined linear-time hitting-set contract. This requires composition at the operational machine level: the first program's final memory must serve as the second program's initial memory, and a polynomial capacity and an absolute linear-time constant must work for the composed program.
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_program_compose
(A₁ A₂ : Complexity.Algorithm .multiplication) (c₁ c₂ : ℝ)
(h₁ : 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)))
(h₂ : 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)) :
∃ (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 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.