Claim 1 —
ProvedSingleMachinePrec.IntervalReduction.claim_1graph-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1vertex-cover
Let be a graph with a tree layout , and let be the gadget graph of Stage 1. Write for the minimum size of a vertex cover of a graph . Then
In the paper's words: if and are optimum vertex covers of and , then . The construction follows Alimonti and Kann's proof of APX-completeness of vertex cover on cubic graphs. It transfers the vertex cover problem on to the graph , which the scheduling instance reproduces.
Formalization Note is Mathlib's SimpleGraph.vertexCoverNum, valued in (finite here). The claim does not use connectivity of or the degree bound, and holds for any parent-first spanning tree.
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_IntervalReduction_TreeLayout
Formal statement
namespace SingleMachinePrec.IntervalReduction
/-- Claim 1 (p. 662): the minimum vertex cover of `G′` is larger than that of `G` by exactly
`|V| + |E \ E_T|`. -/
theorem claim_1 {N : ℕ} (G : SimpleGraph (Fin N)) (L : TreeLayout G) :
(GPrime L).vertexCoverNum =
G.vertexCoverNum + (N : ℕ∞) + (Fintype.card (NonTreeEdge 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. 662, Claim 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.