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