Lemma 2 — deterministic hitting set for large (<k)-out sets
ProvedDirKECC1549.Main.lemma_2directed-graphsedge-connectivitygraph-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1word-ram
Let be a directed multigraph with vertices and edges, a vertex, and integers, and .
- For every spanning tree of directed towards , Algorithm 2 returns a set with ,
and for every with and . 2. The construction takes time: there are one word-RAM program and one absolute constant such that for all such in which every vertex can reach , started on the graph layout of with in the parameter cells, the program halts within ticks with the indicator of , for some spanning tree of directed towards , in the output cells.
Lemma 2 provides, in linear time, the hitting sets used by Algorithm 3 for the large cuts.
Formalization Note The output is written as 's indicator: cell holds if and otherwise.
Differences from the source:
- generalization: directed graph with parallel edges (p.9) → self-loops also allowed; reason: a loop leaves no vertex set and can be deleted from any path, so it changes no out_D, no λ_D and no component; on loop-free multigraphs the statement is exactly the source's
- encoding: vertex set V and edge multiset E → vertices Fin n, edge ids Fin m, an edge map Fin m → Fin n × Fin n; reason: Lean convention; parallel edges are distinct ids, so every count includes multiplicities as on p.9; same instances
- encoding: running time on the word-RAM (p.25) → ticks of the published word-RAM WordRAM.run (Hagerup's model, multiplication instruction set, one tick per instruction, no native constants); reason: the paper's model is the standard word-RAM; every instruction costs one tick
- encoding: O(·) with explicit dependence on k → one program for all k (k read from memory) and one absolute constant c fixed before every input; reason: an O(·) without subscript hides an absolute constant; the k-dependence is written out
- reading: the subroutine's input graph → the graph layout (edge list, sorted out- and in-adjacency arrays of D and Dᴿ with their start offsets) and the scalar parameters are already in fixed memory cells; reason: the paper charges these bounds to a graph already represented (Lemma 5's proof adds the O(m) separately, p.18); for the sublinear bounds this is the only meaningful reading
- generalization: a word-RAM call with word size Θ(log N) → the contract holds for every memory content outside the stated cells and for every word width w with 2^w at least the algorithm's capacity C(N+1)^D+N+16 at the layout size N; reason: Hagerup's model does not initialize memory, and a subroutine runs inside a larger program's width; it specializes to the standard setting
- generalization: the spanning tree T obtained from a DFS from r in Gᴿ (part 1) → every spanning tree of G directed towards r; reason: the proof uses only that T is a spanning in-tree of G; the DFS tree is one
- reading: "we run a DFS from r in Gᴿ … compute Z using Algorithm 2" (part 2) → the program outputs Algorithm 2's set for some spanning tree of G directed towards r; reason: the DFS is the paper's means of obtaining a spanning in-tree towards r; by part 1 the guarantees of Z hold for every such tree
- generalization: Δ ≥ k − 1 (standing in §3.1) → Δ ≥ 1; reason: the statement holds for every Δ ≥ 1 and specializes to Δ ≥ k − 1
- reading: a spanning tree T of G directed towards r (construction preamble) → every vertex can reach r (part 2); a given spanning in-tree (part 1); reason: the construction presupposes it, and §3.2 applies it to strongly connected G; without it the claim fails: if S is the set of vertices that cannot reach r, then out_G(S) = 0 and S ∩ Z = ∅ although vol_G(S) may exceed Δ
- encoding: the set Z → its 0/1 indicator in cells 7B + v; reason: output convention; same content
Preamble
import Mathlib import Definitions.Def_DirKECC1549_Main_HittingSet import Definitions.Def_DirKECC1549_Main_Machine set_option autoImplicit false open WordRAM
Formal statement
namespace DirKECC1549.Main
/-- Lemma 2, p.14 (with the construction of p.13). Let `k ≥ 2`, `Δ ≥ 1`, `n ≥ 2`, `b = ⌊Δ/(k−1)⌋`.
(1) For every spanning tree `T` of `G` directed towards `r`, Algorithm 2 returns
`Z ⊆ V \ {r}` with `|Z| < (k−1)m/Δ` and `S ∩ Z ≠ ∅` for every `S ⊆ V \ {r}` with
`out_G(S) < k` and `vol_G(S) > Δ`.
(2) The construction (a spanning in-tree towards `r`, then Algorithm 2) takes `O(m + n)` time:
one word-RAM program with one absolute constant `c` computes, from the graph layout and
`k, Δ, r`, the indicator of `Z = HittingSet(T, deg⁺, b)` for some spanning in-tree `T`, within
`c (m + n)` ticks, whenever every vertex can reach `r`. -/
theorem lemma_2 :
(∀ (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 →
r ∉ hittingSet r par (outDeg G) (Δ / (k - 1)) ∧
((hittingSet r par (outDeg G) (Δ / (k - 1))).card : ℝ) < ((k : ℝ) - 1) * m / Δ ∧
∀ S : Finset (Fin n), r ∉ S → outCount G S < k → Δ < vol G S →
(S ∩ hittingSet r par (outDeg G) (Δ / (k - 1))).Nonempty) ∧
(∃ (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
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis, STOC 2027 submission #1549 (October 2026), Section 3.2.1, p.13 (construction) and Lemma 2, p.14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.