Unabhängige Menge (Independent Set) ist ein zentrales Problem der Graphentheorie: Gesucht ist eine möglichst große Menge von Knoten, in der keine zwei Knoten durch eine Kante verbunden sind. Zwei Nachbarn dürfen also nie gemeinsam in der Menge liegen.
Definition und Komplexität
Gegeben ein Graph G = (V, E). Eine Knotenmenge S ⊆ V heißt unabhängig, wenn für jedes Paar u, v ∈ S gilt: {u, v} ∉ E. Die Frage „gibt es eine unabhängige Menge mit mindestens k Knoten?“ ist NP-vollständig — eines der 21 Karp-Probleme. In bipartiten Graphen ist das Problem dagegen polynomial lösbar.
Zusammenhang zu Vertex Cover und Clique
Die unabhängige Menge ist das direkte Komplement zur Knotenüberdeckung: Genau dann wenn S unabhängig ist, ist V S eine Vertex Cover. Damit gilt α(G) + τ(G) = |V|. Außerdem ist S genau dann eine unabhängige Menge in G, wenn S im komplementären Graphen eine Clique (vollständig verbundene Teilmenge) bildet — auch das Cliquenproblem ist NP-vollständig.
Berechnung
Eine maximal unabhängige Menge (die sich durch keine einzelne Ergänzung vergrößern lässt) findet der Greedy-Algorithmus leicht: nimm einen Knoten, entferne ihn samt Nachbarn, wiederhole. Eine größte unabhängige Menge zu finden ist dagegen NP-schwer; die Größe lässt sich aber mit Branch-and-Bound oder auf gewichteten Graphen mit dynamischer Programmierung auf Bäumen exakt bestimmen.
Anwendungen
- Scheduling: konfliktfreie Terminmengen, bei denen sich keine zwei überschneiden
- Soziale Netzwerke: Gruppen, in denen niemand direkt verbunden ist
- Funknetze: Sender, die sich gegenseitig nicht stören
- Registerallokation in Compilern (Interferenzgraphen)
Zusammen mit Set Cover und Vertex Cover bildet die unabhängige Menge die klassische Familie NP-schwerer Überdeckungs- und Auswahlprobleme.