Black Box Algorithmen

Hartmut KlauckUniversität FrankfurtSS 05

27.4.

Clique Problem

Sei p ein Parameter aus [0,1] Ein Graph hat Cliquendichte p, wenn es

eine Clique mit pn Knoten gibt D.h. eine Menge aus pn Knoten, die alle

paarweise miteinander verbunden sind p-Clique sei die Eigenschaft, Cliquendichte

p zu haben Ein Graph ist -weit von p-Clique entfernt,

wenn für jede Menge von pn Knoten n2 Kanten zwischen ihnen nicht vorhanden sind

Clique

Beachte: Clique zu entscheiden (gibt es eine Clique der Grösse n/2 z.B.) ist NP-vollständig

Selbst eine eine Clique zu finden, die1/n1-o(1) so gross ist wie die maximale, ist schwer [Hastad97]

Theorem 5.1.: p-Clique ist testbar

Tester nach Paradigma

Tester: Ziehe eine Subgraphen mit S=poly(1/) Knoten

uniform Frage alle Kanten im Subgraphen Wenn es eine Clique mit (p- S Knoten gibt, akz,

sonst verwerfe Relativ klar: wenn es eine Clique mit pn Knoten gibt,

dann werden erwartet pS davon gezogen, mit guter Wahrscheinlichkeit wird akzeptiert

Nicht so klar: verwerfen, denn pn Knoten, denen n2 Kanten zur Clique fehlen sollen nicht zum Akz. führen

Ein unnatürlicher Testalgorithmus

Der natürliche Tester wird als Korollar auch funktionieren

Für Analyse notwendig anderen Tester zu betrachten

GT01 Theorem auch anwendbar

Übersicht

Zeigen, wie eine approximative Clique gefunden werden kann, wenn es eine Clique gibt (mit Grösse pn)

Konstruieren Tester

Approximative Clique

Hintergrund: Wenn weit von p-Clique, gibt es keine grosse approximative Clique

Approximative Clique: Knotenmenge Grösse pn, der n2 Kanten fehlen

Approximative Clique

Schritt 1: [Zur Motivation]

Sei C eine Clique Erlaubt sind Fragen der Form „Hat v alle

Knoten in C zum Nachbarn?“ Dabei sei v sein eigener Nachbar Konstruiere eine Clique der Grösse |C|

Alle Knoten in C werden mit „ja“ beantwortet Aber auch andere!

Approximative Clique

Prozedur:Bestimme Menge T(C) von Knoten mit

Anwort jaCµ T(C), aber eventuell mehr KnotenSortiere Knoten in T(C) nach ihrem Grad

im Subgraphen T(C) Betrachte C‘, Menge der ersten |C| Knoten in

T(C) Behauptung: Ist Clique

Approximative Clique

Beweis: Jeder Knoten in C ist Nachbar jedes

Knoten in T(C) [ausser sich selbst]Jeder Knoten in C hat also Grad

T(C)-1, maximal!Bei Sortierung sind also Knoten mit

Grad T(C)-1 vorneErste |C| davon bilden Clique

Approximative Clique

Problem: Haben kein solches Orakel „Ist v adjazent zu allen in Clique C ?“ Angenommen wir bekommen Menge U‘ aus C mit

Grösse -2log(1/) T(U‘) sei Menge von Knoten, die Nachbar zu allen

Knoten in U‘ sind Idee: Meiste Knoten in T(U‘) sind adjazent zu meisten

Knoten in C Ordne Knoten in T(U‘) nach ihrem Grad in T(U‘) und

nehme pn viele mit höchstem Grad M.h.Ws. Approximative Clique der gewünschten

Grösse

Approximative Clique

Woher bekommen wir U‘ ? Ziehen Knotenmenge U und testen alle Teilmengen U‘ U guter Sampler für C (erwartet), und eine geeignet

grosse Teilmenge U‘ wird in C liegen U‘ ist dann zufällige Teilmenge von C, und T(U‘) hat

gewünschte Eigenschaft Finden grosse approximative Clique, wenn grosse

Clique existiert Wenn keine grosse approximative Clique existiert,

können wir auch keine finden!

Approximative Clique

Nächstes Problem: wie finden wir den Grad eines Knotens in T(U‘) schnell?

Verwende weitere Samplemenge W W(U‘) sei dann T(U‘)Å W Hoffen, dass Grad von v aus T(U‘) in

T(U‘) geteilt durch n ungefähr Grad von v in W(U‘) geteilt t ist, wenn |W|=t gross genug

Approximative Clique: Algorithmus t=10 -2 p log(1/) Wähle t Knoten in U und t Knoten in W uniform zufällig Für alle U‘µ U mit Grösse pt/2:

Setze T(U‘): Menge der Knoten, die alle u in U‘ zum Nachbarn haben

Wenn T(U‘) kleiner als pn, gehe zum nächsten U‘ W(U‘): Menge der Knoten in W, die alle u in U‘ zum

Nachbarn haben, also T(U‘)Å W Bestimme Grad von v in W(U‘) für alle v aus T(U‘) Setze C(U‘) auf erste pn Knoten nach obigem Grad

(gleicher Grad : lexikographisch) Bestimme bestes C(U‘) [meiste Kanten]

Analyse

Behauptung: Obiger Algorithmus gibt eine approximative Clique aus, wenn es eine Clique der Grösse pn gibt

Theorem 5.2:Theorem 5.2:Wenn G eine Clique der Grösse pn

hat, findet der Algo mit Ws. 2/3 eine Knotenmenge mit pn Knoten, der nur n2/10 Kanten fehlen

Bemerkungen

Laufzeit: für konstante p, ist Laufzeit O(n log n) [Sortieren], Anzahl der Fragen O(n)

Abhängigkeit von 1/ ist exponentiell Exaktes Finden von grossen Cliquen

ist NP-schwer

Wie geht es weiter?

Wollen Tester für Eigenschaft p-Clique, d.h. Akzeptieren, wenn es eine pn grosse Clique gibt, verwerfen wenn weit (d.h. es keine pn Knotenmenge gibt, die approximative Clique ist)

Meiste Laufzeit: Berechnung von C(U‘) „Sample“ aus C(U‘) um zu sehen, ob C(U‘) nah an

Clique Im wesentlichen wenden wir den obigen Algo auf einer

dritte Samplemenge S an, und testen, ob in S eine pS grosse approximative Clique gibt

Der Clique Tester

t=10 -2 p log(1/); m=10 -2 log(1/) Wähle t Knoten in U und t Knoten in W und m Knoten in S

uniform zufällig Für alle U‘µ U mit Grösse pt/2:

Setze S(U‘): Menge der Knoten in S, die alle u in U‘ zum Nachbarn haben

W(U‘): Menge der Knoten in W, die alle u in U‘ zum Nachbarn haben

Bestimme Grad von v in W(U‘) für alle v aus S(U‘) Setze D(U‘) auf erste pm Knoten nach obigem Grad

(gleicher Grad : lexikographisch) Entscheidung:

• Wenn |D(U‘)|> (p-/80) m und• Anzahl der fehlenden Kanten ist · m/3, AKZ• Sonst: Verwerfe

Bemerkungen zum Tester

Laufzeit exponentiell in (1/2) Idee: Wenn jede pn grosse Knotenmenge

weit von Clique entfernt, dann kann S Sample nicht erfolgreich sein

Andererseits: Wenn es eine pn Clique gibt, würde Algo zum Finden von approximativer Clique funktionieren und dann kann S Sample gut sein

p-Clique testbar !

Zurück: Approximative Clique, Alorithmus t=10 -2 p log(1/) Wähle t Knoten in U und t Knoten in W uniform zufällig Für alle U‘µ U mit Grösse pt/2:

Setze T(U‘): Menge der Knoten, die alle u in U‘ zum Nachbarn haben

W(U‘): Menge der Knoten in W, die alle u in U‘ zum Nachbarn haben, also T(U‘)Å W

Bestimme Grad von v in W(U‘) für alle v aus T(U‘) Setze C(U‘) auf erste pn Knoten nach obigem Grad

(gleicher Grad : lexikographisch) Bestes C(U‘) ausgeben

Analyse

Behauptung: Obiger Algorithmus gibt eine approximative Clique aus, wenn es eine Clique der Grösse pn gibt

Theorem 5.1:Theorem 5.1:Wenn G eine Clique der Grösse pn

hat, findet der Algo mit Ws. 2/3 eine Knotenmenge mit pn Knoten, der nur n2/10 Kanten fehlen

Übersicht Beweis:

Fixiere unbekannte Clique C mit pn Knoten, setze t wie im Algo

U‘ heisse -Clique-repräsentativ, wenn U‘ ist Teilmenge von C Für alle ausser n Knoten v gilt:

wenn der Grad von v in C nur (p-) n ist, dann ist v nicht zu ganz U‘ adjazent

Man kann zeigen: Mit Ws. 1-1/100 über Wahl von U enthält U

ein 2/p2-Clique-repr. Menge U‘ mit pt/2 Knoten

Übersicht Beweis:

Nehmen im folgenden an, dass U‘ repräsentativ ist

Nächstes Statement: Wenn wir aus T(U‘) ungefähr die Knoten mit höchstem Grad auswählen, bekommen wir eine approximative Clique

Dann: W heisse gut, wenn es gut die Knotengrade approximiert

Statement: Mit hoher Ws ist W gut

Übersicht Beweis:

Lemma 5.2.: Sei ¼2/p2

U‘ sei wie behauptet T(U‘) Menge der Knoten die alle u aus U‘ zum

Nachbarn haben : n sei der Grad des (p-/p) n –ten Knotens in der

Reihenfolge nach dem Grad in T(U‘) Sei C‘ eine Menge von pn Knoten, die mindestens

( - 3/p) n Knoten vom Grad ( - 2/p) n in T(u‘) hat. Dann ist C‘ eine approximative Clique (es fehlen O()

Kanten) Bemerkung: Durch W wird Schätzung der Grade

meistens gut sein, selten schlecht

Übersicht Beweis:

Noch zu zeigen: Gutes W liefert richtige Schätzung der Grade

Für festes U‘, T(U‘) sei W(U‘) der Schnitt von W mit T(U‘)

W heisse -gut, wenn für alle Knoten ausser n vielen: |degWÅT(U‘)(v)/t- deg T(U‘)(v)/n|·

D.h. für fast alle Knoten wird Grad gut geschätzt

Übersicht Beweis:

Lemma 5.3:Wenn T(U‘) gross ist (pn)Dann ist W /p-gut mit

Wahrscheinlichkeit1-1/100.

Übersicht Beweis:

Zusammengesetzt ergibt sich:Sei C eine pn grosse CliqueWenn U‘ clique-repräsentativ ist, und

W gut ist (m.h.Ws.)Dann ist die Menge der pn Knoten die

im Algorithmus gewählt werden eine approximative Clique, der n2/10 Kanten fehlen

Übersicht Beweis:

Beweis 5.3.: Einfach, Anwendung von Chernov Schranken

Beweis 5.2: komplizierter, analog zu vorherigen Betrachtungen über den Fall, wo wir den Grad exakt wussten

Eigenschaft von U‘ sichert, dass wenige Knoten mit sehr kleinem Grad in T(U‘) landen

Zusammenfassung

Wenn eine pn Clique existiert, können wir in Zeit O(n log n) eine approximative pn Clique finden

Durch Anwendung auf zufällige Knotenmenge ergibt sich Tester