Claim 3 — the subgraph of induced by is isomorphic to
ProvedSingleMachinePrec.IntervalReduction.claim_3graph-theoryinterval-ordersp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be a graph with a tree layout , let be the gadget graph of Stage 1, and let be the Stage 2 instance with interval order . Let be the subgraph of the vertex cover graph induced by the incomparable pairs in . Then
The paper's isomorphism sends (including ), , , and . Together with Claim 1, this is what lets the weighted vertex cover problem on encode the unweighted one on .
Formalization Note The statement asserts that a graph isomorphism exists. It does not involve the processing times, weights or : the graph depends only on .
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_IntervalReduction_TreeLayout import Definitions.Def_SingleMachinePrec_IntervalReduction_Instance
Formal statement
namespace SingleMachinePrec.IntervalReduction
/-- Claim 3 (p. 663): the subgraph `G′_I = (D, E_I)` of `G^S_I` induced by `D` is isomorphic
to `G′`. -/
theorem claim_3 {N : ℕ} {G : SimpleGraph (Fin N)} (L : TreeLayout G) :
Nonempty (GIprime L ≃g GPrime L) := by sorry
end SingleMachinePrec.IntervalReduction
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 663, Claim 3 (proof pp. 663–664)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.