13 Näherungslösung für das Vertexcover Problem

Das Vertexcover-Problem (Gesucht: Minimales VC ) läßt sich mit Fehlerschranke f = 2 lösen.

Finde maximales Matching.
Nimm Endpunkte jeder Matching-Kante.
$\Rightarrow$ f = 2 .

Sei K ein Vertexcover für G = (V,E) $\Rightarrow$ V$\backslash$K ist Independent Set.

Der gleiche Näherungsalgorithmus wie oben liefert jedoch eine beliebig schlechte Fehlerschranke für das Independent Set-Problem.

z.B.: n = 100 Knoten, minimales Vertexcover sei 45 Knoten.
Näherung für Vertexcover ( VC ) liefert 90 Knoten.
$\Rightarrow$ Näherung für Independent Set hat 10 Knoten.
Opt. Independent Set = 55 Knoten $\Rightarrow$ Fehlerschranke f > 5 !

Satz:

Falls das Independent Set Problem mit Fehlerschranke f > 1 gelöst werden kann, so kann es mit beliebiger Fehlerschranke f' > 1 gelöst werden.

Hierzu bilden wir aus einem Graphen G einen Graphen G' , der |V| Kopien von G enthält, wobei Kopie i mit Kopie j genau dann paarweise verbunden ist, wenn es Kante (i,j) $\in$ E gibt.

G hat ein Independent Set der Größe k$\iff$G' hat ein Independent Set der Größe k ². Näherungsalgorithmus findet Independent Set der Größe ${\frac{k^2}{f}}$ in G' . Daraus läßt sich in G ein Independent Set der Größe $\sqrt{\frac{k^2}{f}}$ = ${\frac{k}{\sqrt{f}}}$ finden. (Bisher wurde aber noch kein Näherungsalgorithmus mit konst. Fehlerschranke f gefunden.)