SAT-Kodierung: Vertex Cover

• Def: Graph G = (V, E) mathend000#,

  Menge M⊆V mathend000# heißt Knotenüberdeckung,

  falls ∀x∈V $\setminus$ M : ∃y∈M : xy∈E mathend000#.

• Entscheidungsproblem: (G, k) mathend000#, Frage: ...| M|≤k mathend000#
• „Anwendung``: kleinstes Vertex Cover von Damen auf Schachbrett
• Anwendung: Plazierung von Versorgungs- oder Überwachungsknoten in einem Netzwerk