[BuK] polynomielle Reduktion: IndSet <=p ComSubGraph

[Heiner]

Tag zusammen,
ich lern grade für BuK, und wie das so ist am Ende des Semesters ärgere ich mich nicht immer brav bei der Übung gewesen zu sein und Lösungen mitget zu haben. Da es auch keine Musterlösung gibt und die Aufgabe so in den Jahren wo es eine gab nicht vorkam, bitte ich jetzt hier um Hilfe.
Und zwar ist zu zeigen:
INDEPENDENTSETCOMMONSUBGRAPH
Ist die erste Aufgabe von Blatt 8.
Mein Gedankengang bisher: IndependentSet: Elemente nicht verbunden => Menge im Komplementärgraph: Elemente alle Verbunden (Clique) => Eingabe für CS ist einmal der Komplementärgraph und einmal der vollständige Graph. Aber wie wähle ich meine Zahl ?

[Mandelbrot]

Ich würde die Funktion f ((V,E),k) -> ((V1',E1'),(V2',E2'),k') wählen:

V' = V, e E' gdw. e E (komplementär)
G2' vollständiger Graph mit k-Knoten
k' = k

Dass das in poly-Zeit berechenbar ist, lässt sich leicht erkennen ( O(V³)).

Und zur Korrektheit:
G hat k-IS -> G1' hat k-Clique C1 ->G2' ist k-Clique C2 -> Ex. Isomorphismus von C1 auf C2 -> folglich haben G1' und G2' k-CS (nämlich C1 und C2).

G hat kein k-IS -> G1' hat keine k-Clique -> G2' ist k-Clique -> Es existiert kein Isomporphismus von C1 auf C2 -> folglich existiert kein k-CS (vllt. k-1, aber das erfüllt unsere Bedingung nicht).

Sollte so tun, auch wenn ich mir das grad nur ausgedacht habe...

P.S.: Irgendwie sieht tex hier komisch aus?!

[Heiner]

Auf die Idee bin ich garnicht gekommen, als zweiten Graphen einfach eine k-Clique zu nehmen. Scheint ja so zu funktioniern... Danke!

[Tommytb]

Ich behaupte mal das klappt so nicht, da bei ComSub nach einem Subgraph mit >= k Kanten gefragt ist, eine k-Clique hat aber k^2 Kanten. D.h. deine 2. Korrektheitsschlussfolgerung funzt nicht. Aber mit k' = k^2 sollte es passen.

[Heiner]

Eine k-Clique hat nicht k² Kanten.
Knoten -> Kanten
1 -> 0
2 -> 1
3 -> 3
4 -> 6
usw.
Sind

[Tommytb]

Naja ist aber O(k^2), ich denke in diesen Dimensionen gerichtet wie ungerichtet.

[Teldo]

Ich bekomme die Rückrichtung leider nicht hin und glaube ein Gegenbeispiel gefunden zu haben:
Also angenommen wir haben in G1 und G2 einen CommonSubGraph mit
Dann müsste daraus folgen, dass G einen Independentset der Größe k hat.

Gegenbeispiel (4 Knoten):

Code: Alles auswählen

a ----------- b
|             |
|             |
c ----------- d


Der gleiche Graph von oben mit allen möglichen Kanten.
Gemäß f ist G dann der Graph von oben, in dem nur die Kanten {a,d} und {c,b} existieren.
Offensichtlich ist G1 in der Form wie er oben steht ein CommonSubGraph von G1 und G2 mit 4 Kanten.
Offensichtlich gibt es in G aber maximal einen Independentset der Größe 2, denn von den beiden Knoten die verbunden sind kann jeweils nur einer gewählt werden.

[Teldo]

Das ganze müsste funktionieren, wenn man k' = k*(k-1) / 2 setzt, denn das ist die Anzahl an Kanten in G2.

[Heiner]

Wenn es um -CS vom volständigen Graphen mit k Knoten und geht, dann hat G(quer) doch ein k-IS, oder?

[Mandelbrot]

Ja, sorry.

Wenn man statt Kanten Knoten betrachtet, dann tut das mit k' = k natürlich ...^^ Bevor man Probleme löst, sollte man die Definitionen lernen

... nehmen wir einfach k' = |E2'| = (k über 2) und es sollte tun, oder (Ausrufezeichen!)? Dass wir einen ungerichteten Graphen betrachten sollte im Kontext der VL klar sein

Hmm, Heiner, welches G? Generell kann man sagen: G hat k-IS <=> G_quer hat k-Clique <=> G_quer hat (k über 2)-CS . Ich verstehe die Frage nicht so ganz