p. 365 — the edge dominating set problem for bipartite graphs with maximum degree 3 is in NP
ProvedEdgeDomSets.NPC.edsBip3_inNPnp-completenessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
The edge dominating set problem for bipartite graphs with maximum degree 3 belongs to NP:
i.e. there is a verifier running in polynomially many Turing-machine steps, with polynomially bounded certificates, that accepts some certificate for exactly when .
This is the membership half of THEOREM 2; the paper's recipe (p. 365) requires it but gives no argument.
Formalization Note NP is CookLevin.InNP.
Differences from the source:
- encoding: P ∈ NP → CookLevin.InNP edsBip3Lang; reason: Cook's and Karp's notion, on the published CookLevin machine model
- reading: bipartite graphs with maximum degree 3; a positive integer k → simple graph with Colorable 2, every degree ≤ 3, and 1 ≤ k; reason: paper.md reading 6
Preamble
import Mathlib import Definitions.Def_EdgeDomSets_NPC_Problems
Formal statement
namespace EdgeDomSets.NPC theorem edsBip3_inNP : CookLevin.InNP edsBip3Lang := by sorry end EdgeDomSets.NPC
Source
Yannakakis, Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38(3) (1980) 364–372, p. 365, §2 ("it is enough to prove that P ∈ NP …")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.