SAT-Kodierung: Vertex Cover

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

  Menge M⊆V heißt Knotenüberdeckung,

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

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