NP-Vollständigkeit beweisen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Betrachten Sie das folgende Problem:
Netzwerküberlebensfähigkeit (NetworkSurvivability - NWS)
Eingabe: Ungerichteter Graph G=<V,E> für jedes V [mm] \cup [/mm] E eine Ausfallwahrscheinlichkeit p(x) [mm] \in \IQ [/mm] , 0 [mm] \le [/mm] p(x) [mm] \le [/mm] 1 und eine Zahl q [mm] \in \IQ [/mm] mit q [mm] \le [/mm] 1.
Aufgabe: Angenommen, dass das Versagen von Knoten und Kanten unabhängige Ereignisse sind, entscheiden, ob die Wahrscheinlichkeit größer oder gleich q ist, dass für alle Kanten {u,v} [mm] \in [/mm] E mindestens u oder v oder {u,v} ausfällt.
Beweisen Sie, dass NWS ein NP-vollständiges Problem ist. (Hinweis: Für die Reduktion könnte man das Problem VC betrachten). |
Anmerkung: das Problem VC (Vertexcover) ist die Knotenüberdeckung eines Graphen, wobei eine Zahl k gegeben ist. Man soll bestimmen, ob es eine Untermenge U [mm] \subseteq [/mm] V gibt, die hächstens k Knoten enthält, wobei jede Kante von G einen Endknoten in U hat.
Um die NP-Vollständigkeit zu beweisen, muss ich also eine FP-Reduktion finden, so dass gilt:
1) L [mm] \in [/mm] NP (in dem Fall ist es das Problem NWS)
2) L' [mm] \in [/mm] NP und L' reduzierbar auf L (dank des Hinweises wissen wir, dass L' das Problem VC ist)
Ich denke, ich verstehe es richtig, dass die FP-Reduktion eine Funktion ist, die das eine Problem in das andere überführt (und auch zurückführt).
Leider habe ich keine guten Ideen, wie man das eine Problem auf das andere (mit polynomialer Komplexität versteht sich:)) reduzieren sollte.
Der einzige Ansatz von mir ist, dass ich den Wert k vom Problem VC nehme und diesen Wert in den Wahrscheinlichkeitswert q vom Problem NWS umrechne (z.B. wir haben |V|=10 [10 Knoten im Graphen] und k=5, der daraus berechnete Wert ist dann q=0,5). Dadurch habe ich den "Schwellwert" für NWS.
Und von NWS nach VC würde ich analog aus q den Wert k berechnen.
Was meint ihr? Kann man mit der Lösung arbeiten oder bin ich komplett auf dem falschen Weg?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Mi 17.03.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
