Completeness and soundness of the colouring reduction to generalized flow shops (core of Theorem 1.2)
ProvedFlowJobHardness.ColoringReduction.coloring_reduction_gapLet be a simple graph on vertices whose vertices are partitioned into independent sets (a proper colouring into classes), let be an integer, and let be the generalized flow shop instance of the colouring reduction, with . Then:
- Structure. is a generalized flow shop: every job visits its machines in strictly increasing global machine order. Every job has length and every machine has load .
- Completeness. For every , if is -colourable then
i.e. some feasible schedule of has makespan at most . 3. Soundness. For every real with : if every independent set of has fewer than vertices, then in every feasible schedule of fewer than half of the jobs finish within .
This gap is the mathematical core of Theorem 1.2 of the paper. Combined with Khot's hardness of distinguishing graphs of chromatic number at most from graphs with independence number at most , and with , , it shows that it is NP-hard to distinguish generalized flow shop instances with a schedule of makespan from those in which no schedule finishes more than half of the jobs within .
Formalization Note. Only the combinatorial gap is formalized; "NP-hard", "for sufficiently large ", "in time polynomial in and ", Khot's theorem and the parameter choice are not. The paper's soundness clause ("given a schedule where at least half the jobs finish within time units, we can find an independent set of of size ") is stated in its contrapositive, distinguishing form, as Theorem 1.2 uses it; its positive form is Lemma 3.9. "Sufficiently large " is the explicit threshold . "At least half of the jobs" is . The vertex set is Fin n, which covers every finite graph up to relabelling.
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
/-- **The completeness/soundness gap of the reduction `Γ`** (Mastrolilli–Svensson 2011, §3,
p. 20:12; Remark 3.6, Lemma 3.7 and Lemma 3.9, pp. 20:17–20:18), the mathematical core of
Theorem 1.2 (p. 20:5). For every graph `G` on `n` vertices with a proper colouring
`c : V → {1, …, d}` and every `r ≥ 8`, the instance `S = S(r, d)` satisfies:
* (a) `S` is a generalized flow shop: the machines of every job are visited in strictly
increasing global machine order; every job length and every machine load equal
`lb = r^{2d}`;
* (b) completeness: if `G` is `K`-colourable then `S` has a feasible schedule of makespan at
most `2K · r^{2d}`;
* (c) soundness: for every real `0 < L ≤ r`, if every independent set of `G` has fewer than
`n / (8L)` vertices, then in no feasible schedule of `S` do at least half of the jobs finish
within `L · r^{2d}`. -/
theorem coloring_reduction_gap {n d : ℕ} (G : SimpleGraph (Fin n)) (c : G.Coloring (Fin d))
(r : ℕ) (hr : 8 ≤ r) :
(∀ q : Fin (size r d n), ∀ i i' : Fin ((inst G c r).μ q), i < i' →
MachBefore c ((inst G c r).π q i) ((inst G c r).π q i')) ∧
(∀ q : Fin (size r d n), (inst G c r).jobLength q = (R r d : ℝ)) ∧
(∀ p : Fin (size r d n), (inst G c r).load p = (R r d : ℝ)) ∧
(∀ K : ℕ, G.Colorable K →
∃ s : (inst G c r).Op → ℝ,
(inst G c r).IsFeasibleSchedule Finset.univ s ∧
(inst G c r).makespan Finset.univ s ≤ 2 * (K : ℝ) * (R r d : ℝ)) ∧
(∀ L : ℝ, 0 < L → L ≤ r →
(∀ I : Finset (Fin n), G.IsIndepSet (I : Set (Fin n)) → (I.card : ℝ) < (n : ℝ) / (8 * L)) →
∀ s : (inst G c r).Op → ℝ, (inst G c r).IsFeasibleSchedule Finset.univ s →
2 * (finishedCount G c r s L : ℝ) < (size r d n : ℝ)) := by sorry
end FlowJobHardness.ColoringReduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.