SAT-Kodierung: Independent Set

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

Entscheidungsproblem:

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

Optimierungsproblem:

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

Ist das Optimierungsproblem schwieriger (aufwendiger) als das Entscheidungsproblem? (Hier: nein.)