Polynomielle Reduktion < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:47 Mo 12.12.2011 | | Autor: | Gedro |
| Aufgabe | Gegeben sind die Sprachen:
$R := [mm] \{ | X \text{endliche Menge}, S \subseteq P(X), \text{so dass es eine Teilmenge von} X \text{der Groesse hoechstens} k \text{gibt, die aus jeder Menge in} S \text{mindestens ein Element enthält} \}$
[/mm]
VertexCover := [mm] $\{ | G \text{besitzt eine Knotenueberdeckung der Groesse} k \}$
[/mm]
Reduzieren sie die Sprache Vertex Cover auf R. |
Hallo,
bei dieser Aufgabe stehe ich gerade ein wenig auf dem Schlauch.
Wenn ich mir die Definition beider Sprachen Anschaue, dann sind die von der mathematischen Beschreibung ja so gut wie identisch.
Für R gilt:
$<X, S [mm] \subseteq [/mm] P(X),k> = [mm] w_{1}$
[/mm]
[mm] $w_{1}\in [/mm] R$ wenn gilt:
[mm] $\exists T\subseteq [/mm] X$ mit [mm] $|T|\le [/mm] k$: Für [mm] $\forall M\in [/mm] S$, gilt [mm] $M\cap T\not= \emptyset$
[/mm]
$<G=(V,E),k> = [mm] w_{2}$
[/mm]
[mm] $w_{2}\in [/mm] VC$ wenn gilt:
[mm] $\exists T\subseteq [/mm] V$ mit [mm] $|T|\le [/mm] k$: Für [mm] $\forall \{u,v\}\in [/mm] E: [mm] \{u,v\}\cap T\not=\emptyset$
[/mm]
Jetzt versuche ich mittels [mm] w_{1} [/mm] einen Graphen zu konstruieren, der eine Knotenüberdeckung von höchstens k hat.
Nach meiner Vorstellung würde V=X gelten, d.h. die Elemente in X sind die Knoten in G. S müsste hier irgendwie die Kanten definieren, damit sich eine Teilmenge [mm] T\subseteq [/mm] X finden lässt, die eine Knotenüberdeckung darstellt. Das Problem auf das ich hier stoße ist aber, dass S eine Teilmenge einer Potenzmenge ist, d.h. S hat höchstens [mm] 2^{|X|} [/mm] Elemente(Mengen). Daraus folgt, dass ich mit S einfach nichts anfangen kann, da selbst ein naiver Durchlauf schon nicht mehr polynomiell wäre.
Aber einen entsprechenden Graphen nur aus X und k zu konstruieren scheint mir irgendwie nicht möglich.
Hat jemand eine Idee wie ich hier vorgehen kann?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
MfG
Gedro
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:49 So 18.12.2011 | | Autor: | Gedro |
Ich hab mich leider geirrt bei der Aufgabe. Die Sprache Vertex-Cover soll auf R reduziert werden. Dadurch wir die Reduktion trivial.
Die Richtung die ich oben einschlagen wollte ist nämlich wegen dem Problem, das ich erwähnt habe, gar nicht möglich.
Gruß,
Gedro
|
|
|
|
