Algorithm 2 hits large low-outdegree cuts
ProvedDirKECC1549.Main.hitting_set_cutsdirected-graphsedge-connectivity
Let be a finite directed multigraph with a spanning in-tree rooted at , and let and . Run Algorithm 2 with threshold and outdegree weights. Every vertex set excluding , with fewer than outgoing edges and out-volume greater than , contains a selected vertex. Parallel edges are counted with multiplicity and loops are allowed.
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_cuts {n m : ℕ} (G : Fin m → Fin n × Fin n)
(k Δ : ℕ) (r : Fin n) (par : Fin n → Fin n)
(hk : 2 ≤ k) (hΔ : 1 ≤ Δ) (ht : IsSpanningInTree G r par)
(S : Finset (Fin n)) (hr : r ∉ S) (hout : outCount G S < k) (hvol : Δ < vol G S) :
(S ∩ hittingSet r par (outDeg G) (Δ / (k - 1))).Nonempty := 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.