THEOREM 2, p. 367 — the edge dominating set problem for bipartite graphs of maximum degree 3 is NP-complete
ProvedEdgeDomSets.NPC.theorem_2Assume that the SAT-3-restricted problem is NP-complete (the paper takes this from its reference [13]). Then the edge dominating set problem for bipartite graphs with maximum degree 3 — given a graph that is bipartite with all degrees at most 3 and a positive integer , does have a set of at most edges which dominate all the other edges? — is NP-complete:
NP-completeness means membership in NP together with NP-hardness under polynomial-time many-one reductions. The result shows that minimum maximal matching is NP-hard even on bipartite graphs of maximum degree 3, and is the input to the paper's COROLLARY 1 on independent sets of total graphs.
Formalization Note NP-completeness is CookLevin.NPComplete (multi-tape Turing machines, polynomial step bounds). Graphs are coded by the published NPGraph encoding, formulas by the CookLevin formula code.
Differences from the source:
- reading: "The reduction is from the SAT-3-restricted problem" (NP-complete by [13]) → hypothesis CookLevin.NPComplete sat3rLang; reason: the paper cites [13] (Yannakakis 1978) for it; it is not on the platform and is not part of this paper
- 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; "maximum degree 3" as an upper bound
- encoding: NP-complete (Cook [2], Karp [9]) → CookLevin.NPComplete on binary codes (NPGraph graph code, CookLevin formula code); reason: the published framework of the Proved 3-SAT and CLIQUE results
- generalization: the SAT-3 restricted problem (a set of clauses, at most three literals per clause, every variable two times and its negation once) → sat3rLang: codes of satisfiable formulas with IsSat3Restricted, occurrences counted with multiplicity (repeated literals or clauses, a clause with x and x̄, empty clauses allowed); reason: sat3rLang contains every instance of the printed problem; the printed problem reduces to it by sending its instances to themselves and everything else to a fixed no-instance, so NP-completeness of the printed problem gives that of sat3rLang, and a reduction from sat3rLang gives one from the printed problem (paper.md reading 4)
import Mathlib import Definitions.Def_EdgeDomSets_NPC_Problems
namespace EdgeDomSets.NPC
theorem theorem_2 (h : CookLevin.NPComplete sat3rLang) :
CookLevin.NPComplete edsBip3Lang := by sorry
end EdgeDomSets.NPC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.