Cliquen-Problem und k-Clique < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:40 Mi 22.06.2011 | | Autor: | Pille456 |
| Aufgabe | Problem: k-Clique (Für ein [mm] k\in\IN)
[/mm]
Gegeben: Ein ungerichteter Graph G
Frage: Gibt es in G eine Clique C der Größe k?
Problem: Clique
Gegeben: Ein ungerichteter Graph G und ein (festes) k [mm] \in \IN
[/mm]
Frage: Gibt es in G eine Clique C der Größe k?
k-Clique lässt sich in polynomineller Zeit lösen. Warum folgt daraus nicht, dass sich auch das Problem Clique in polynomieller Zeit lösen lässt? |
Hio,
Ich glaube ich habe die Problemdefinition nicht ganz verstanden, denn ich verstehe die Frage nicht so recht.
Erstmal ist das k-Cliquen-Problem für jedes k [mm] \in \IN [/mm] ein anderes Problem. Heißt das nun, dass jedes dieser Probleme in polynomineller Zeit lösen lässt oder nur bestimmte?
Beim Clique-Problem erhalte ich nun k als zusätzliche Eingabe:
Angenommen für alle k [mm] \in \IN [/mm] lässt sich k-Clique (jeweils) in polynomineller Zeit lösen, wo ist dann das Problem, für Clique einfach eine Fallunterscheidung zu machen und entsprechend dem eingegebenen k den passenden Algo. für das k-Clique Problem aufzurufen, der dann in polynomineller Zeit abläuft?
Gruß
Pille
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:02 Mi 22.06.2011 | | Autor: | felixf |
Moin!
> Problem: k-Clique (Für ein [mm]k\in\IN)[/mm]
> Gegeben: Ein ungerichteter Graph G
> Frage: Gibt es in G eine Clique C der Größe k?
>
> Problem: Clique
> Gegeben: Ein ungerichteter Graph G und ein (festes) k [mm]\in \IN[/mm]
>
> Frage: Gibt es in G eine Clique C der Größe k?
>
> k-Clique lässt sich in polynomineller Zeit lösen. Warum
> folgt daraus nicht, dass sich auch das Problem Clique in
> polynomieller Zeit lösen lässt?
>
> Hio,
>
> Ich glaube ich habe die Problemdefinition nicht ganz
> verstanden, denn ich verstehe die Frage nicht so recht.
>
> Erstmal ist das k-Cliquen-Problem für jedes k [mm]\in \IN[/mm] ein
> anderes Problem. Heißt das nun, dass jedes dieser Probleme
> in polynomineller Zeit lösen lässt oder nur bestimmte?
Jedes.
Allerdings: fuer jedes fest gewaehlte $k$ hast du ein anderes Polynom. Und das ist hier der Knackpunkt.
> Beim Clique-Problem erhalte ich nun k als zusätzliche
> Eingabe:
> Angenommen für alle k [mm]\in \IN[/mm] lässt sich k-Clique
> (jeweils) in polynomineller Zeit lösen, wo ist dann das
> Problem, für Clique einfach eine Fallunterscheidung zu
> machen und entsprechend dem eingegebenen k den passenden
> Algo. für das k-Clique Problem aufzurufen, der dann in
> polynomineller Zeit abläuft?
Nun, schau dir mal die Laufzeit des polynomiellen Algorithmus an. Der Algorithmus ist sehr einfach: fuer jede $k$-elementige Teilmenge von $V(G)$ teste, ob diese eine $k$-Clique ist. Da es [mm] $\binom{|V(G)|}{k} [/mm] = [mm] O(|V(G)|^k)$ [/mm] solche Teilmengen gibt, ist die Laufzeit somit polyomiell in $|V(G)|$.
Aber was bedeutet das jetzt fuer die Laufzeit deines Algorithmus?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:25 Do 23.06.2011 | | Autor: | Pille456 |
Hio!
Ich fasse das mal in meinen Worten zusammen:
Der Algorithmus zum Testen, ob ein Graph G=(V,E) eine k-Clique hat kann wie folgt vorgehen:
Teste jede k-Elementige Teilmenge von V, ob diese eine Clique ist. Falls eine gefunden wird geben diese aus, sonst gebe "nein" zurück.
Nun ist die Frage: Wie viele k-elementigen Teilmengen gibt es? Das ist gerade der Binominialkoeffizient:
[mm] \vektor{|V| \\ k}=\bruch{|V|!}{k!(|V|-k)!} [/mm]
Wie kommt man hiervon auf [mm] O(|V|^k) [/mm] ? Irgendwie finde ich das recht unintuitiv, denn je größer k wird, je weniger Teilmengen gibt es und je weniger hat der Algorithmus zu testen.
Ich glaube mir fehlt hier gerade noch die Tatsache, dass man die Mengen miteinander kombinieren muss oder?
Bsp: k=1, dann gibt es ja nicht |V| Kandidaten, sondern ich muss ja gerade jedes v [mm] \in [/mm] V mit jedem anderen x [mm] \in [/mm] V (x [mm] \not= [/mm] v) vergleichen oder?
Klar ist, wenn die Laufzeit [mm] O(|V|^k) [/mm] beträgt, und sowohl G=(V,E) und k die Eingabe ist, dass der Algo. dann exponentiell abläuft, weil ja k gerade auch die Eingabe ist!
Aber wer sagt mir, dass der Algorithmus zum Lösen von k-Clique gerade so abläuft, dass er alle Teilmengen testen muss? Klar das geht, aber hier ist ja nur von irgendeinem polynominellen Algorithmus die Rede. Ist die Einschränkung hier nicht zu groß gewählt oder ist es egal, da ich sowieso weiß, dass jeder Algorithmus zum Lösen von k-Clique polynominelle Zeit braucht und es somit für die Laufzeit egal wird, welchen konkret ich betrachte?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:51 Do 23.06.2011 | | Autor: | felixf |
Moin!
> Hio!
> Ich fasse das mal in meinen Worten zusammen:
>
> Der Algorithmus zum Testen, ob ein Graph G=(V,E) eine
> k-Clique hat kann wie folgt vorgehen:
> Teste jede k-Elementige Teilmenge von V, ob diese eine
> Clique ist. Falls eine gefunden wird geben diese aus, sonst
> gebe "nein" zurück.
> Nun ist die Frage: Wie viele k-elementigen Teilmengen gibt
> es? Das ist gerade der Binominialkoeffizient:
> [mm]\vektor{|V| \\ k}=\bruch{|V|!}{k!(|V|-k)!}[/mm]
> Wie kommt man hiervon auf [mm]O(|V|^k)[/mm] ? Irgendwie finde ich
> das recht unintuitiv, denn je größer k wird, je weniger
> Teilmengen gibt es und je weniger hat der Algorithmus zu
> testen.
Wenn du dich fuer die Laufzeit von $k$-Clique interessierst, bist du an der Laufzeit fuer $|V| [mm] \to \infty$ [/mm] interessiert. Dann ist $k$ konstant, und [mm] $\binom{|V|}{k} [/mm] = [mm] \frac{1}{k!} \prod_{i=0}^{k-1} [/mm] (|V| - i)$ ist ein Polynom in $|V|$ von Grad $k$. Also ist die Laufzeit [mm] $O(|V|^k)$.
[/mm]
Wenn du natuerlich auch $k$ laufen laesst, sieht es anders aus. Es gilt ja [mm] $\binom{|V|}{k} [/mm] = [mm] \binom{|V|}{|V| - k}$, [/mm] weswegen die Laufzeit eher [mm] $|V|^{\min\{ k, |V| - k \}}$ [/mm] ist. Fuer $k [mm] \approx \frac{|V|}{2}$ [/mm] ist die Laufzeit [mm] $\binom{|V|}{|V|/2}$ [/mm] (nehmen wir mal an dass $n$ geraede ist), fuer diesen Ausdruck gibt es asymptotische Abschaetzungen, und diese sind exponentiell in $|V|$.
Und schliesslich: [mm] $\sum_{k=0}^{|V|} \binom{|V|}{k} [/mm] = [mm] 2^{|V|}$.
[/mm]
> Ich glaube mir fehlt hier gerade noch die Tatsache, dass
> man die Mengen miteinander kombinieren muss oder?
> Bsp: k=1, dann gibt es ja nicht |V| Kandidaten, sondern ich
> muss ja gerade jedes v [mm]\in[/mm] V mit jedem anderen x [mm]\in[/mm] V (x
> [mm]\not=[/mm] v) vergleichen oder?
Nein, bei $k = 1$ musst du streng genommen gar nichts tun. Jeder Vertex von $G$ bildet eine 1-Clique. Alternativ kannst du auch jede 1-elementige Teilmenge durchgehen und schauen ob es eine 1-Clique ist (ist es immer). Aber eine quadratische Laufzeit bekommst du sicher nicht.
> Klar ist, wenn die Laufzeit [mm]O(|V|^k)[/mm] beträgt, und sowohl
> G=(V,E) und k die Eingabe ist, dass der Algo. dann
> exponentiell abläuft, weil ja k gerade auch die Eingabe
> ist!
>
> Aber wer sagt mir, dass der Algorithmus zum Lösen von
> k-Clique gerade so abläuft, dass er alle Teilmengen testen
> muss?
Niemand. Aber du kannst gern versuchen einen anderen zu finden 
Man kann da schon ein wenig herumtricksen, aber die Laufzeit aendert sich nicht wesentlich.
> Klar das geht, aber hier ist ja nur von irgendeinem
> polynominellen Algorithmus die Rede. Ist die Einschränkung
> hier nicht zu groß gewählt oder ist es egal, da ich
> sowieso weiß, dass jeder Algorithmus zum Lösen von
> k-Clique polynominelle Zeit braucht und es somit für die
> Laufzeit egal wird, welchen konkret ich betrachte?
Es gibt auch nicht-polynomielle Algorithmen fuer $k$-Clique (wie fuer jedes andere Problem auch, grob gesprochen: man muss einfach irgendwie Zeit totschlagen). Hier weisst du nur, dass es fuer jedes $k$ einen polynomiellen Algo fuer $k$-Clique gibt.
Wie schnell der ist ist nicht gesagt, und ob es schneller geht als [mm] $O(|V|^k)$ [/mm] (fuer festes $k$) oder [mm] $O(|V|)^{k-1})$ [/mm] oder sowas ist eine Frage fuer sich.
Die Laufzeit muss jedoch exponentiell in $k$ sein, da es ansonsten auch einen subexponentiellen Algorithmus fuer Clique geben wuerde. Bekannt ist aber keiner.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:45 Do 23.06.2011 | | Autor: | Pille456 |
Hio!
Danke für Deine Hilfe, hat mir wirklich sehr geholfen. Gerade die Abschätzung $ [mm] \sum_{k=0}^{|V|} \binom{|V|}{k} [/mm] = [mm] 2^{|V|} [/mm] $ hat es doch nochmal recht deutlich erklärt. Ich fühle mich in dem Thema zwar noch nicht so sicher, aber das Cliquen-Problem habe ich nun deutlich besser verstanden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:24 Fr 24.06.2011 | | Autor: | felixf |
Moin!
> Danke für Deine Hilfe, hat mir wirklich sehr geholfen.
> Gerade die Abschätzung [mm]\sum_{k=0}^{|V|} \binom{|V|}{k} = 2^{|V|}[/mm]
Das ist keine Abschaetzung, sondern echte Gleichheit
Folgt direkt aus dem binomischen Lehrsatz, wenn man $(1 + [mm] 1)^{|V|}$ [/mm] damit ausschreibt.
LG Felix
|
|
|
|
