§8, p. 664 — the subgraph of induced by the weight-1 nodes is isomorphic to
ProvedSingleMachinePrec.VariableCost.heavy_subgraph_isograph-isomorphismp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reductionsschedulingvertex-cover
Let be a graph on vertices , let , and let be the scheduling instance of the proof of Theorem 8.1. Then:
- for all , the nodes and are adjacent in if and only if ;
- if , the subgraph of induced by the nodes of weight is isomorphic to , by an isomorphism sending to :
Together with the weight bounds, this identifies vertex covers of , up to light nodes, with vertex covers of .
Formalization Note For some light nodes , , have weight as well, so the set of weight-1 nodes is larger than the set of heavy nodes; the isomorphism is therefore stated under , while the adjacency equivalence (1) holds for every .
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_VariableCost_AdjacencyInstance open scoped NNReal
Formal statement
namespace SingleMachinePrec.VariableCost
/-- §8, p. 664 (proof of Theorem 8.1). For the instance `S = adjacencyInstance G k`:
(1) two nodes `(v′_i, v″_i)` and `(v′_j, v″_j)` are adjacent in `G^S_P` if and only if
`{v_i, v_j} ∈ E`; (2) if `k > 1`, the subgraph of `G^S_P` induced by the nodes of weight `1`
is isomorphic to `G`, by an isomorphism sending `(v′_i, v″_i)` to `v_i`. -/
theorem heavy_subgraph_iso {n : ℕ} (G : SimpleGraph (Fin n)) (k : ℝ≥0) :
(∀ i j : Fin n,
(vertexCoverGraph (adjacencyInstance G k).P).Adj (heavy G k i) (heavy G k j) ↔
G.Adj i j) ∧
(1 < k →
∃ f : (vertexCoverGraph (adjacencyInstance G k).P).induce
{u | vertexWeight (adjacencyInstance G k) u = 1} ≃g G,
∀ (i : Fin n) (h : heavy G k i ∈ {u | vertexWeight (adjacencyInstance G k) u = 1}),
f ⟨heavy G k i, h⟩ = i) := by sorry
end SingleMachinePrec.VariableCost
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 664, §8, proof of Theorem 8.1 (isomorphism with G)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.