p. 367, proof of THEOREM 2, part (i) — a satisfying assignment gives a dominating edge-set F with |F| = 3n
ProvedEdgeDomSets.NPC.part_iLet be a SAT-3-restricted formula with variables and a truth assignment satisfying all clauses. Define
Then is an edge dominating set of and .
Together with part (ii) this shows that has an edge dominating set of size exactly when is satisfiable.
Formalization Note Clause and position indices are 0-based (Fin). The vertices of are indexed by literal occurrences: the occurrence has a literal vertex lit o (the paper's , or ), a pendant pend o (the primed copy) and a variable-side vertex varNode o ( or for the two positive occurrences of , for the negated one); dNode j, dNode' j are , . The set is assignEdges φ α: at every occurrence, the edge from the literal vertex to its clause vertex if the literal is true under , and to its variable-side vertex if it is false; this is the printed . The assignment is a map .
Differences from the source:
- encoding: vertices a_i, b_i, c_i, (a_i, j1), (b_i, j2), (c_i, j3), their primed copies, d_j, d'_j, with 1-based indices → one literal vertex, one pendant vertex and one variable-side vertex per literal occurrence (clause index, position), plus d_j, d'_j, all 0-based (
Fin); reason: under SAT-3-restricted the three occurrences of x_i are exactly x_i ∈ C_j1, x_i ∈ C_j2, x̄_i ∈ C_j3, so the vertices and edges are the printed ones - generalization: a set of clauses with at most three literals per clause, every variable occurring two times and its negation once → IsSat3Restricted φ on a list of literal lists: occurrences counted with multiplicity, so a clause may repeat a literal or hold x and x̄, clauses may repeat, and empty clauses are allowed; reason: every instance of the printed problem satisfies IsSat3Restricted, so the statement specializes to the source's claim on each of them; the construction and the argument are unchanged on the extra formulas (paper.md reading 4)
import Mathlib import Definitions.Def_EdgeDomSets_NPC_Construction
namespace EdgeDomSets.NPC
theorem part_i (φ : CookLevin.Formula) (hφ : IsSat3Restricted φ)
(α : CookLevin.Assignment) (hα : CookLevin.Satisfies α φ) :
IsEdgeDominating (G φ) (assignEdges φ α) ∧
(assignEdges φ α).card = 3 * numVars φ := by sorry
end EdgeDomSets.NPC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.