SAT-Kodierung: Vertex Cover

Def: Graph G = (V, E), Menge M $\subseteq$ V heißt Knotenüberdeckung, falls $\forall$x $\in$ V $\setminus$ M : $\exists$y $\in$ M : xy $\in$ E.

Entscheidungsproblem: (G, k), Frage: ...| M|$\le$k

Anwendung: kleinstes Vertex Cover von Damen?