Eine Clique ist in einem ungerichteten Graphen eine Menge von Knoten, bei der jedes Paar von Knoten direkt durch eine Kante verbunden ist. Die Knoten bilden also einen vollständigen Teilgraphen. Das Entscheidungsproblem „Gibt es eine Clique mit mindestens k Knoten?“ heißt Cliquenproblem und ist NP-vollständig (Karp 1972).
Beispiel: Freundesgruppe
Stell dir ein soziales Netzwerk als Graphen vor: Jede Person ist ein Knoten, jede Freundschaft eine Kante. Eine Clique ist dann eine Gruppe, in der sich wirklich alle kennen – es gibt kein Paar ohne direkte Verbindung. Solche dichten Gruppen lassen sich in sozialen Netzwerken gezielt suchen.
Zusammenhang zur unabhängigen Menge
Die Clique ist das direkte Gegenstück zur unabhängigen Menge: Eine Clique im Graphen G ist eine unabhängige Menge im komplementären Graphen (dort sind genau die Nicht-Kanten von G als Kanten enthalten) – und umgekehrt. Wer eines der beiden Probleme lösen kann, kann auch das andere lösen.
Schwere und Approximation
- Eine maximale Clique (die sich nicht mehr erweitern lässt) findet ein Greedy-Verfahren greedy leicht.
- Die größte Clique zu finden ist NP-schwer – es gibt unter der Annahme P ≠ NP keinen Polynomialzeitalgorithmus und sogar keine gute Approximationsgarantie.
- In bipartiten Graphen ist das Cliquenproblem dagegen trivial: Die größte Clique hat höchstens zwei Knoten, weil keine Kanten innerhalb einer Partitionsseite existieren.
Anwendungen
- Soziale Netzwerke: dichte Freundes- und Interessensgruppen erkennen
- Bioinformatik: stark interagierende Proteingruppen finden
- Fehlerdiagnose und Datenanalyse: eng zusammenhängende Teilmengen identifizieren
Einordnung: Das Cliquenproblem gehört wie die NP-vollständigen Probleme zur Familie der schweren Entscheidungsprobleme; Grundlagen zu Knoten und Kanten findest du unter Graph-Datenstruktur.