SAT-Kodierung: Independent Set

Def: Graph G = (V, E), Menge M $\subseteq$ V heißt unabhängig, falls $\forall$x, y $\in$ M : xy $\notin$E.

Entscheidungsproblem:

• Eingabe: (G, k)
• Frage: existiert unabhängige Menge M in G mit | M|$\ge$k?

Optimierungsproblem:

• Eingabe: G
• Ausgabe: möglichst große unabhängige Menge in G