Cliquenproblem nicht approxim. < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:11 Do 03.09.2009 | | Autor: | marko86 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo alle zusammen,
ich habe ein kleines Verständnisproblem bei einem Beweis, dass das Cliquenproblem nicht mit einem konstanten (hier nur additiven) Approximationsfehler k approximierbar ist.
Folgende Konstruktion besteht im Moment: Wir nehmen an, es gibt einen solchen Algorithmus mit konstantem Approximationsfaktor k und geben für diesen Algorithmus folgende Eingabe: Ein Graph [mm] G^k [/mm] = G x [mm] C_k, [/mm] wobei das "x" bedeuten soll, dass es sich praktisch um das kartesiche Produkt unseres Ausgangsgraphen G und der k-Clique [mm] C_k [/mm] handelt (V(G)=A,B,C, [mm] V(C_2)=D,E [/mm] => [mm] V(G^2) [/mm] = ((A,D),(B,D),(C,D),(A,E),(B,E),(C,E)). Das genaue Aussehen ist glaube ich nicht so wichtig, es sind nur ziemlich viele Kanten drin ;) Die Größe der maximalen Clique in G ist w(G); nach Konstruktion ist [mm] w(G^k) [/mm] = k * w(G).
Nun machen wir folgendes: Wir geben unserem Algorithmus A die Eingabe [mm] G^{(k+1)}. [/mm] Dieses Ding hat folglich (k+1)*w(G) als größte Cliquengröße. Auch sind k+1 Kopien von G in dem neuen Graphen, genannt [mm] G_i, [/mm] da er ja das kartesische Produkt von G und einer Clique der Größe k+1 ist. In jedem dieser Kopien sind nun Teile der maximalen Lösung für k+1 enthalten, genannt [mm] C_i. [/mm] Da die Teilgraphen ja nur k Knoten haben, gilt v.a., dass jedes [mm] C_i [/mm] <= w(G) "Lösungsanteile" hat. Da unser Algorithmus einen konstanten Approximationsfaktor von k hat, gilt (wenn man das ganze etwas umstellt): (k+1)*w(G) - [mm] \summe_{i=1}^{k+1}(|C_i|) [/mm] <= k. Daraus folgt: [mm] \summe_{i_1}^{k+1}(w(G)-|C_i|) [/mm] <= k.
Nun zu meiner Frage: Als nächstes wird behauptet, dass genau wegen [mm] \summe_{i_1}^{k+1}(w(G)-|C_i|) [/mm] <= k folgt, dass es ein [mm] C_i [/mm] geben muss mit [mm] |C_i|=w(G) [/mm] (und draraus dann, dass man Clique in polynomialer Zeit approximieren könnte, was ja nicht sein kann, solange P!=NP). Ich habe da schon stundenlang überlegt, mir fällt aber kein echter Grund ein, weswegen man die Existenz dieses [mm] C_i [/mm] folgern dürfte. Ich meine, ja, die Formel ist soweit für mich verständlich, auch aus der Herleitung, aber irgendwie scheine ich im Moment ein Brett vor dem Kopf zu haben, was denn passieren würde, wenn es dieses eine [mm] C_i [/mm] mit [mm] |C_i|=w(G) [/mm] nicht geben würde; wäre die Summe dann > k? Und warum?
Es wäre sehr nett von euch, wenn ihr hier mal kurze Denkanstöße reinschreiben würdet.
Viele Grüße
Marko
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:52 Do 03.09.2009 | | Autor: | marko86 |
Hallo, ich habe die Sache mal eben versucht durchzurechnen.
Es gilt ja: (k+1)w(G) - [mm] \summe_{i=1}^{k+1}(|C_i|) [/mm] <= k. Dabei sind die [mm] |C_i| [/mm] <= w(G).
Mit k := 5 (als Approximationsfehler), w(G) := 3 (geht ja, mein Graph hat halt nur maximal 3-Cliquen) ergibt sich:
(5+1)w(G) - [mm] \summe_{i=1}^{5+1}(|C_i|) [/mm] <= 5, also
6w(G) - [mm] \summe_{i=1}^{6}(|C_i|) [/mm] <= 5, d.h.
18 - [mm] \summe_{i=1}^{6}(|C_i|) [/mm] <= 5.
Die Summe muss also >= 13 sein.
Da die [mm] C_i [/mm] <= 3 sind, nehme ich mal an, es gilt [mm] \forall [/mm] i: [mm] |C_i| [/mm] = 2.
Dann ist die Summe aber 2+2+2+2+2+2 = 12 <= 13, was nicht geht und somit [mm] \exists [/mm] i: [mm] |C_i| [/mm] = 3, womit ich meine gewünschte Clique der Größe 3 in meinem konstruierten Graphen gefunden habe.
Der Ansatz kommt mir irgendwie und einigermaßen logisch vor (und dazu noch irgendwie trivial...) Aber nachdem ich mich heute schon so dämlich angestellt habe, diese vermeintliche Lösung nicht zu finden [geht übrigens auch für k:=1, also minimalem Fehler], traue ich mir noch nicht ganz und würde gerne eure Meinung wissen...
Sorry, dass ich euch mit dieser vielleicht unnötigen Frage gernevt habe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:20 Mo 07.09.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
