Black Box Algorithmen

Hartmut KlauckUniversität FrankfurtSS 05

22.4.

K-Färbbarkeit

Ein Graph heisst k-färbbar, wenn es eine Partition der Knoten in k Mengen gibt, wobei keine Kante innerhalb einer der Mengen verläuft

2-färbbare Graphen: bipartit Entscheidung von 3-Färbbarkeit ist

NP-vollständig ! Dennoch testbar!

K-Färbbarkeit

Tester [AK99]:Ziehe O(k log k2) KnotenFrage alle KantenBestimme, ob k-färbbarJa: akz., nein: verw.

Fragen: O(k2 log24) Zeit: exp(k log k/2) Also testbar!

K-Färbbarkeit

Beweis eines etwas schwächeren Resultats verläuft ähnlich wie bei Bipartitheit

NP-Vollständigkeit schliesst Testbarkeit nicht aus!

Das Testparadigma im Matrixmodell Es wird ein Subgraph ausreichender

Grösse gesamplet, und dann auf Grapheigenschaft getestet

Theorem 4.1. [GT01]: Jede testbare Grapheigenschaft [im

Matrixmodell] kann auch durch getestet werden, indem ein Subgraph uniform zufällig gewählt wird, alle Kanten im Subgraph gefragt werden, und dann auf dem Subgraph eine Grapheigenschaft entschieden wird

Die Anzahl der Fragen steigt von q auf 2q2

Beweis

Ein Tester heisst nichtadaptiv, wenn alle seine Fragen unabhängig von den Antworten am Anfang feststehen (dürfen abhängig von der Randomisierung sein)

Tester folgend dem Subgraph Paradigma sind offensichtlich nichtadaptiv

Schwächerer Beweis: exponentieller blowup der Fragenanzahl

Bewahrt immer noch Testbarkeit

Beweis

Gegeben: beliebiger Property Tester für eine Grapheigenschaft P

Schritt 1: Umwandlung in nichtadaptiven Tester

Random bits seien am Beginn festgelegt Bei q Fragen gibt es 2q verschiedene

Antwortmuster Frage alle! Insgesamt q 2q Fragen, nun nichtadaptiv Genauer: in Schritt i gibt es 2i-1 mögliche

Fragen, insgesamt 2q

Beweis

Also nun gegeben: nichtadaptiver Tester, q‘ viele Fragen

Gesucht: Tester, der Subgraphparadigma folgt Es gibt · 2q‘ Knoten in der Folge von Fragen Frage alle inzidenten Kanten, also O(q‘2) Damit wird ein Subgraph gefragt, und dies

nichtadaptiv Noch zu zeigen:

• Erreiche uniforme Verteilung• Entscheide eine Grapheigenschaft

Beweis

Grapheigenschaften sind invariant unter Permutation der Knoten

Neuer Tester:• Bestimme zuerst eine zufällige Permutation von

{1,…,n}• Lasse den alten Tester laufen, bilde Fragen des

Testers mit der Permutation ab• D.h. Auf Frage (i,j) Antwort ((i),(j))• Klar: Algorithmus hat selbe

Korrektheitseigenschaft wie zuvor• Ebenfalls: Jeder Subgraph hat nun dieselbe

Wahrscheinlichkeit, gefragt zu werden

Beweis

Genauer gesagt:Ein Graph wird akzeptiert mit einer

Wahrscheinlichkeit, die der Erwartungswert ist über die Ws. dass seine Permutationen akzeptiert werden

Analoges für VerwerfenWenn vorher immer ¸ 2/3, dann

nachher auch

Beweis

Noch zu zeigen: Tester entscheidet eine Grapheigenschaft auf dem Subgraphen Egal, was der vorherige Tester getan hat,

nach der Transformation ist seine Akzeptierungs/Verwerfungsws. invariant unter Knotenpermutation

D.h. nun Entscheidung auf einem Subgraphen nur noch vom Subgraphen abhängig, nicht von seiner Position im Graphen, aber noch randomisiert

Beweis

Mache nun die Entscheidung deterministisch:• Wenn Tester einen Graphen mit >1/2 akzeptiert,

akzeptiere immer, sonst verwerfe immer Wie verhält sich der Fehler ?

Beispiel: 1/3 aller Subgraphen werden mit Wahrscheinlichkeit 1 akzeptiert, alle anderen mit ½, insgesamt also Akzeptanz

Nach Modifikation: Ausweg: verringere zuerst Fehler auf 1/6

Zu akzeptierende Graphen: Im schlimmsten Fall werden 1/3 aller Subgraphen mit ½ akzeptiert, alle anderen sicher. Gesamtakzeptanz 5/6. Nach Modifikation immer noch 2/3.

Zu verwerfende Graphen analog

Beweis

Erhalten also einen Tester, der Subgraph uniform wählt, und dann deterministisch eine Grapheigenschaft entscheidet

[GT01] tun das Ganze mit nur quadratischem blowup in der Anzahl der Fragen

Idee GT01

Nicht zuerst nichtadaptiv machen Zuerst Wechsel zu Subgraph Test Dann Entscheidung unabhängig

machen von der Position des Subgraphen

Zum Schluss auf deterministische Grapheigenschaftstests modifizieren

Skizze

Gegeben ein Tester Wenn q Fragen gestellt werden, sind nur 2q

Knoten im Spiel Simuliere Tester

Frage (i,j) im originalen Tester: Frage alle Kanten zu Knoten, die vorher einmal vorkamen

Gesamt: 2q2 Fragen, es wird ein Subgraph mit 2q Kanten komplett aufgedeckt

Skizze

Gegeben Tester, der (adaptiv) Subgraphen mit 2q Knoten aufdeckt

Jetzt wieder Tester mit zufälliger Permutation der Knoten simulieren

Zeige jetzt, dass die Wahrscheinlichkeit, einen Subgraphen aufzudecken, uniform ist Genauer: Wenn i Knoten (und ihre Kanten

zu vorherigen Knoten) gefragt sind, ist nächster Knoten uniform zufällig

Skizze

Ersetze nun durch Algorithmus, der zu Beginn uniform einen Subgraphen wähltEntkoppelt Wahl Subgraph von

Randomisierung im restlichen Tester Klar auch: Akzeptanzws. OK

Skizze

Nun noch gegeben: Tester, der Subgraph wählt, und dan probabilistisch weiterrechnet

Zeigen: Akz. Ws. unabhängig von Position des Subgraphen

Dann: Deterministisch machen Es ergibt sich wieder Test einer

Grapheigenschaft auf zuf. Subgraphen, diesmal polynomieller Grösse

Schlussfolgerung

Wenn eine Grapheigenschaft P auf n Knoten testbar ist, dann

Gibt es eine Konstante q() und eine Grapheigenschaft P‘ auf q Knoten, so dass in einem -weit von P entfernten Graphen 2/3 aller Subgraphen mit q Knoten P‘ nicht erfüllen

Für Property Testing von Grapheigenschaften ist der Unterschied zwischen adaptiven und nichtadaptiven Algorithmen höchstens quadratisch

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 Approximation mit einem Faktor n1-o(1) ist schwer

Theorem 4.2.: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

Bemerkung: In diesem Beispiel ist Eigenschaft auf kleinen Graphen nicht exakt dieselbe wie auf grossem