Lemma 3.9 — if half the jobs of S(r, d) finish by , then G has an independent set of size
ProvedFlowJobHardness.ColoringReduction.lemma_3_9Let be a simple graph on vertices with a proper colouring into classes, let be an integer, let be a real number with , and let be the generalized flow shop instance of the colouring reduction, with .
If has a feasible schedule in which at least half of its jobs finish within time units, then has an independent set with
This is the soundness half of the reduction: a schedule in which many jobs finish early certifies a large independent set.
Formalization Note. The paper states that such an independent set can be found "in time polynomial in and "; the algorithmic clause is not formalized, only the existence of the independent set. "At least half the jobs" is . The paper's "for any " is taken with , so that is meaningful; for the hypothesis can only hold when , since every job has length . The threshold is inherited from Lemma 3.12.
import Mathlib import Definitions.Def_JobShopLTAS_Core_Instance import Definitions.Def_FlowJobHardness_ColoringReduction_Construction import Definitions.Def_FlowJobHardness_ColoringReduction_Schedule open JobShopLTAS.Core
namespace FlowJobHardness.ColoringReduction
/-- **Lemma 3.9** (Mastrolilli–Svensson 2011, p. 20:18), mathematical content. Let `r ≥ 8`
and `0 < L ≤ r`. If `S(r, d)` has a feasible schedule in which at least half of the
`r^{2d} n` jobs finish within `lb · L = L · r^{2d}` time units, then `G` has an independent set
of size at least `n / (8L)`. (The paper's "in time polynomial in `n` and `r^d`" is not
formalized.) -/
theorem lemma_3_9 {n d : ℕ} (G : SimpleGraph (Fin n)) (c : G.Coloring (Fin d)) (r : ℕ)
(hr : 8 ≤ r) (L : ℝ) (hL0 : 0 < L) (hLr : L ≤ r) (s : (inst G c r).Op → ℝ)
(hs : (inst G c r).IsFeasibleSchedule Finset.univ s)
(hhalf : (size r d n : ℝ) ≤ 2 * (finishedCount G c r s L : ℝ)) :
∃ I : Finset (Fin n), G.IsIndepSet (I : Set (Fin n)) ∧
(n : ℝ) / (8 * L) ≤ (I.card : ℝ) := by sorry
end FlowJobHardness.ColoringReduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.