§2, proof of Theorem 1, p. 4 — the support graph of a vertex of (LP) is a pseudoforest
ProvedUnrelatedSched.TwoApprox.vertex_support_pseudoforestLet , deadlines and , and let be a vertex of the linear program (LP) of the Rounding Theorem. Let be the bipartite support graph of , with . Then is a pseudoforest: for every set of machines and every set of jobs,
Equivalently, each connected component of is a tree or a tree plus one edge. This structural fact is what makes the vertex roundable: the rounding of the Rounding Theorem is a matching in this graph.
Formalization Note The paper states the component form ("the number of nodes in each component is at least equal to the number of edges"); the hereditary counting form above is equivalent for finite graphs. The paper's deadlines and threshold are integers; the statement is for real ones, which the proof allows.
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoApprox_DeadlineLP
namespace UnrelatedSched.TwoApprox
/-- §2, proof of Theorem 1, p. 4: the support graph of a vertex of (LP) is a pseudoforest. -/
theorem vertex_support_pseudoforest {m n : ℕ} (P : Matrix (Fin m) (Fin n) ℕ) (d : Fin m → ℝ)
(t : ℝ) (x : Matrix (Fin m) (Fin n) ℝ) (hx : IsLPVertex P d t x) :
IsPseudoforest (supportEdges x) := by sorry
end UnrelatedSched.TwoApprox
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.