§2, proof of Theorem 1, pp. 4–5 — in a pseudoforest, job nodes of degree ≥ 2 can be matched to machines
ProvedUnrelatedSched.TwoApprox.pseudoforest_job_matchingLet , and let be the edge set of a bipartite graph between machines and jobs which is a pseudoforest (every set of machines and of jobs spans at most edges). Let be a set of jobs each of which has degree at least in . Then there is a matching that covers all of : a map from jobs to machines with
In the proof of the Rounding Theorem this is applied to the support graph of a vertex after deleting the jobs that the vertex already assigns integrally; the matching assigns each remaining job to a distinct machine.
Formalization Note The paper's graph is the support graph with the job nodes of degree removed; here the jobs of are any set of jobs of degree at least , and the pseudoforest property of the whole graph is assumed (it passes to ). The degree of job is the number of edges of at .
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoApprox_DeadlineLP
namespace UnrelatedSched.TwoApprox
/-- §2, proof of Theorem 1, pp. 4–5: in a machine–job pseudoforest, any set of jobs each of degree
at least 2 can be matched into the machines. -/
theorem pseudoforest_job_matching {m n : ℕ} (hm : 0 < m)
(E : Finset (Fin m × Fin n)) (hE : IsPseudoforest E)
(T : Finset (Fin n)) (hdeg : ∀ j ∈ T, 2 ≤ (E.filter fun e => e.2 = j).card) :
∃ f : Fin n → Fin m, (∀ j ∈ T, (f j, j) ∈ E) ∧ Set.InjOn f (T : Set (Fin n)) := by sorry
end UnrelatedSched.TwoApprox
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.