Packing bound for tree hitting-set vertices
ProvedDirKECC1549.Main.hitting_set_packingdirected-graphsedge-connectivity
Let be a finite directed multigraph with edges and let be a spanning in-tree rooted at . For every natural number , let be the non-root vertices selected by Algorithm 2 with threshold and weights given by the outdegrees in . Then
This is the integer packing inequality underlying the size estimate: selected vertices charge disjoint positive blocks of at least outgoing edges, counted with multiplicity. Loops and parallel edges 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_packing {n m : ℕ} (G : Fin m → Fin n × Fin n)
(r : Fin n) (par : Fin n → Fin n) (b : ℕ) (ht : IsSpanningInTree G r par) :
(b + 1) * (hittingSet r par (outDeg G) b).card ≤ m := 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.