Theorem 7.1 — vertex cover on connected graphs of degree at most 3 reduces to on interval orders
ProvedSingleMachinePrec.IntervalReduction.theorem_7_1The paper states: Problem with precedence constraints that form an interval order is NP-hard. Its proof reduces vertex cover on connected graphs of maximum degree 3, which is NP-complete (Garey, Johnson and Stockmeyer). What the proof establishes, and what is formalized, is the correctness of that reduction.
Let be a connected graph in which every vertex has at most neighbours, let be a spanning tree of rooted at whose numbering puts every parent before its children, and let be an integer. Let be the scheduling instance of Stage 2 built from and , with jobs and , let be its precedence constraints and the minimum weight of a vertex cover of . Set . Then
- is an interval order, and
- has a vertex cover of size at most if and only if
Since solving is equivalent to finding a minimum weight vertex cover of (Theorem 2.1 of the paper), this shows that remains hard when the precedence constraints form an interval order, a class on which many scheduling problems become polynomially solvable.
Formalization Note "NP-hard", the NP-completeness of the source problem, and the polynomial size of the construction are not formalized. Neither is the passage from to schedules (Theorem 2.1, cited). The statement holds for every parent-first spanning tree, not only the paper's breadth-first tree. The connectivity and degree hypotheses are kept as in the paper, although the reduction's correctness does not use them. The interval order is AppliedComb.Posets.IsIntervalOrder applied to the instance's order on jobs; is Nat.floor ().
import Mathlib import Definitions.Def_AppliedComb_Posets_intervalOrder import Definitions.Def_SingleMachinePrec_IntervalReduction_TreeLayout import Definitions.Def_SingleMachinePrec_IntervalReduction_Instance
namespace SingleMachinePrec.IntervalReduction
/-- Theorem 7.1 (p. 661), in the form its proof (pp. 661–664) establishes: for a connected graph
`G` of maximum degree at most 3 with a rooted spanning tree numbered parent-first, the instance
`S` of Stage 2 (with `k = n² + 1`) has interval-order precedence constraints, and `G` has a vertex
cover of size at most `m` if and only if `⌊w(C_I)⌋ ≤ m + c`, where `c = |V| + |E \ E_T|`. -/
theorem theorem_7_1 {N : ℕ} (G : SimpleGraph (Fin N)) (hconn : G.Connected)
(hdeg : ∀ v, (G.neighborSet v).ncard ≤ 3) (L : TreeLayout G) (m : ℕ) :
AppliedComb.Posets.IsIntervalOrder (Job L) ∧
((∃ C : Finset (Fin N), G.IsVertexCover (C : Set (Fin N)) ∧ C.card ≤ m) ↔
⌊tauW L⌋₊ ≤ m + N + Fintype.card (NonTreeEdge L)) := by sorry
end SingleMachinePrec.IntervalReduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.