SAT-Kodierung: Independent Set

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

Entscheidungsproblem:

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

Optimierungsproblem:

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

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