Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Completeness and soundness of the colouring reduction to generalized flow shops (core of Theorem 1.2)

Proved
FlowJobHardness.ColoringReduction.coloring_reduction_gap

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

flow-shopgraph-coloringhardness-of-approximationindependent-setjob-shopp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let G=(V,E)G=(V,E)G=(V,E) be a simple graph on nnn vertices whose vertices are partitioned into ddd independent sets (a proper colouring into ddd classes), let r≥8r \ge 8r≥8 be an integer, and let S=S(r,d)S = S(r,d)S=S(r,d) be the generalized flow shop instance of the colouring reduction, with lb=r2d\mathrm{lb} = r^{2d}lb=r2d. Then:

  1. Structure. SSS is a generalized flow shop: every job visits its machines in strictly increasing global machine order. Every job has length r2dr^{2d}r2d and every machine has load r2dr^{2d}r2d.
  2. Completeness. For every K∈NK\in\mathbb NK∈N, if GGG is KKK-colourable then
Cmax⁡∗(S)≤lb⋅2K=2K r2d,C^*_{\max}(S) \le \mathrm{lb}\cdot 2K = 2K\, r^{2d},Cmax∗​(S)≤lb⋅2K=2Kr2d,

i.e. some feasible schedule of SSS has makespan at most 2K r2d2K\,r^{2d}2Kr2d. 3. Soundness. For every real LLL with 0<L≤r0 < L \le r0<L≤r: if every independent set of GGG has fewer than n/(8L)n/(8L)n/(8L) vertices, then in every feasible schedule of SSS fewer than half of the jobs finish within L⋅lbL\cdot\mathrm{lb}L⋅lb.

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 KKK from graphs with independence number at most n/K(1/25)log⁡Kn/K^{(1/25)\log K}n/K(1/25)logK, and with d=Δ+1d=\Delta+1d=Δ+1, r=K(1/25)log⁡Kr = K^{(1/25)\log K}r=K(1/25)logK, it shows that it is NP-hard to distinguish generalized flow shop instances with a schedule of makespan 2K⋅lb2K\cdot\mathrm{lb}2K⋅lb from those in which no schedule finishes more than half of the jobs within 18K(1/25)log⁡K⋅lb\tfrac18 K^{(1/25)\log K}\cdot \mathrm{lb}81​K(1/25)logK⋅lb.

Formalization Note. Only the combinatorial gap is formalized; "NP-hard", "for sufficiently large KKK", "in time polynomial in nnn and rdr^drd", 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 lb⋅L\mathrm{lb}\cdot Llb⋅L time units, we can find an independent set of GGG of size n/(8L)n/(8L)n/(8L)") is stated in its contrapositive, distinguishing form, as Theorem 1.2 uses it; its positive form is Lemma 3.9. "Sufficiently large rrr" is the explicit threshold r≥8r\ge 8r≥8. "At least half of the jobs" is 2⋅#{j:Cj≤L r2d}≥r2dn2\cdot\#\{j : C_j\le L\,r^{2d}\}\ge r^{2d}n2⋅#{j:Cj​≤Lr2d}≥r2dn. The vertex set is Fin n, which covers every finite graph up to relabelling.

Preamble
import Mathlib
import Definitions.Def_JobShopLTAS_Core_Instance
import Definitions.Def_FlowJobHardness_ColoringReduction_Construction
import Definitions.Def_FlowJobHardness_ColoringReduction_Schedule

open JobShopLTAS.Core
Formal statement
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
Source
Mastrolilli, Svensson, Hardness of Approximating Flow and Job Shop Scheduling Problems, J. ACM 58(5) (2011), Article 20, p. 20:12 (Section 3, completeness and soundness of the reduction), with Remark 3.6, Lemma 3.7 (p. 20:17) and Lemma 3.9 (p. 20:18); core of Theorem 1.2 (p. 20:5)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me