Vertex Cover (Knotenüberdeckung) ist eines der bekanntesten NP-vollständigen Probleme auf Graphen: Gesucht ist eine möglichst kleine Menge von Knoten, sodass jede Kante des Graphen mindestens einen ihrer beiden Endpunkte in dieser Menge hat.
Definition und Komplexität
Gegeben ein Graph G = (V, E). Eine Knotenmenge C ⊆ V ist eine Knotenüberdeckung, wenn für jede Kante {u, v} mindestens einer der Knoten u oder v in C liegt. Die Entscheidungsfrage „gibt es eine Überdeckung mit höchstens k Knoten?“ ist NP-vollständig, die Optimierungsvariante NP-schwer.
Approximation und exakte Verfahren
Ein einfacher Algorithmus liefert eine 2-Approximation: Berechne ein maximales Matching und nimm alle dessen Knoten in die Überdeckung. Jede echte Überdeckung muss aus jeder Matching-Kante mindestens einen Knoten enthalten, daher ist die Lösung höchstens doppelt so groß wie das Optimum. Trotz der NP-Schwere ist Vertex Cover mit Parametrisierung nach k fix-parameter-berechenbar (FPT): Die Laufzeit ist für kleine k praktikabel. In bipartiten Graphen gilt sogar der Satz von Kőnig: minimale Knotenüberdeckung = maximales Matching, also polynomial lösbar.
Zusammenhang zur unabhängigen Menge
Es gilt die elegante Komplement-Beziehung: Eine Knotenmenge S ist genau dann eine unabhängige Menge, wenn V S eine Knotenüberdeckung ist. Die Größen hängen zusammen als α(G) + τ(G) = |V| — mit α als größter unabhängiger Menge und τ als kleinster Knotenüberdeckung. Ein Problem ist also genau dann schwer, wenn das andere es ist.
Anwendungen
- Überwachung: minimale Kamera-Standorte, die alle Wege (Kanten) abdecken
- Netzwerk-Sicherheit: minimale Knoten, die alle Verbindungen kontrollieren
- Bioinformatik: Genom-Analysen mit Graphenmodellen
Gemeinsam mit Set Cover und der unabhängigen Menge ist Vertex Cover ein Kernbaustein der Theorie NP-vollständiger Probleme.