Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2 — deterministic hitting set for large (<k)-out sets

Proved
DirKECC1549.Main.lemma_2

by mikedeng1 · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

directed-graphsedge-connectivitygraph-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1word-ram

Let GGG be a directed multigraph with n≥2n\ge2n≥2 vertices and mmm edges, rrr a vertex, k≥2k\ge2k≥2 and Δ≥1\Delta\ge1Δ≥1 integers, and b=⌊Δ/(k−1)⌋b=\lfloor\Delta/(k-1)\rfloorb=⌊Δ/(k−1)⌋.

  1. For every spanning tree TTT of GGG directed towards rrr, Algorithm 2 returns a set Z=HittingSet(T,(deg⁡G+(v))v,b)Z=\mathrm{HittingSet}(T,(\deg^+_G(v))_v,b)Z=HittingSet(T,(degG+​(v))v​,b) with Z⊆V∖{r}Z\subseteq V\setminus\{r\}Z⊆V∖{r},
∣Z∣<(k−1)mΔ,|Z|<\frac{(k-1)m}{\Delta},∣Z∣<Δ(k−1)m​,

and S∩Z≠∅S\cap Z\ne\emptysetS∩Z=∅ for every S⊆V∖{r}S\subseteq V\setminus\{r\}S⊆V∖{r} with outG(S)<k\mathrm{out}_G(S)<koutG​(S)<k and volG(S)>Δ\mathrm{vol}_G(S)>\DeltavolG​(S)>Δ. 2. The construction takes O(m+n)O(m+n)O(m+n) time: there are one word-RAM program and one absolute constant c>0c>0c>0 such that for all such G,r,k,ΔG,r,k,\DeltaG,r,k,Δ in which every vertex can reach rrr, started on the graph layout of GGG with k,Δ,rk,\Delta,rk,Δ,r in the parameter cells, the program halts within c(m+n)c(m+n)c(m+n) ticks with the indicator of HittingSet(T,(deg⁡G+(v))v,b)\mathrm{HittingSet}(T,(\deg^+_G(v))_v,b)HittingSet(T,(degG+​(v))v​,b), for some spanning tree TTT of GGG directed towards rrr, 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 ZZZ's indicator: cell 7B+v7B+v7B+v holds 111 if v∈Zv\in Zv∈Z and 000 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
  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me