ParAlg, Kapitel 6.5

6.5 MPC-Graphenalgorithmen: Zusammenhangskomponenten

Sei $G = (V, E)$ ein endlicher ungerichteter Graph. Im MPC-Setting können wir $G$ darstellen, indem wir annehmen, dass jede Kante ${u, v}$ als ein Item auf einer Maschine liegt. Wieder treffen wir keine Annahmen darüber, auf welche Weise die Kanten auf den Maschinen verteilt sind, außer, dass keine Maschine mehr als $S$ Items hat. Wie üblich nehmen wir an, dass $S = O (N^{ϵ})$ gilt, wobei $N$ die Menge der Eingabe-Items ist, in diesem Falle als $m = | E |$ , die Anzahl der Kanten.

Diese Darstellung hat den Nachteil, dass Sie nicht zwischen

und

unterscheiden kann, da nur Kanten als Eingabe-Items gegeben werden. Legen wir also fest, dass zusätzlich jeder Knoten ein Eingabe-Item ist; die Eingabemenge ist somit $V \cup E$ , im zweiten Graphen oben also

\begin{array}{r} {a, b, c, d, {a, b}, {a, c}, {b, c}} . \end{array}

Übungsaufgabe 6.5.1 (Graphdarstellung organisieren). Wir wollen die Darstellung des Graphen so erweitern, dass wir für jeden Knoten $u$ den Grad kennen: dass also das Item $(u, \deg (u))$ auf irgendeiner Maschine liegt; zusätzlich, dass jedes Kanten-Item ${u, v}$ weiß, auf welcher Maschine die Knoten $u$ und $v$ liegen. Zeigen Sie, wie wir das in $O (1 / ϵ)$ Runden erreichen können.

Zusammenhangskomponenten berechnen

Wir wollen nun die Zusammenhangskomponenten von $G$ berechnen. Genauer gesagt wollen wir für jeden Knoten $u$ ein Label $l (u)$ berechnen, so dass $\begin{array}{r} (1) & l (u) = l (v) ⟺ u und v sind in der gleichen Zusammenhangskomponente . \end{array}$ Wir gehen dabei so vor wie in Kapitel 4.1. Wir unterhalten eine Funktion $f : V \to C$ , die jedem Knoten eine Farbe zuordnet. Zu jedem Zeitpunkt soll gelten:

\begin{array}{r} (2) & f (u) = f (v) ⟹ u und v sind in der gleichen Zusammenhangskomponente \end{array}

Für eine Farbe $c \in C$ sei

\begin{array}{r} V_{c} := {u \in V | f (u) = c} \end{array}

die Farbklasse $c$ . Wenn $V_{c}$ nichtleer ist, nennen wir es ein Fragment $c$ . Wenn ein Fragment $V_{c}$ eine Zusammenhangskomponente von $G$ ist, dann ist es ein vollständiges Fragment, ansonsten ein unvollständiges Fragment. Im letzteren Fall gibt es eine Kante ${u, v} \in E$ mit $f (u) \neq f (v)$ . Falls jedes Fragment vollständig ist, so erfüllt $f$ die Bedingung ( $1$ ) und somit haben wir die Zusammenhangskomponenten gefunden.

Es gibt einen MPC-Algorithmus, der die Zusammenhangskomponenten in $O (1 / ϵ \cdot \log n)$ Runden berechnet. 6.5.1

Beweis. Unser Algorithmus folgt eng dem CREW-PRAM-Algorithmus aus Kapitel 4.1, Wir initialisieren $f (u) := u$ . Jeder Knoten ist also in seiner eigenen Farbklasse, und es gibt somit $n$ unvollständige Fragmente (bzw. weniger, falls es in $G$ isolierte Knoten gibt). Aus technischen Gründen ersetzen wir jede ungerichtete Kante ${u, v}$ durch die zwei gerichteten $(u, v)$ und $(v, u)$ . Der Algorithmus geht nun in Phasen vor. Jede Phase benötigt $O (1 / ϵ)$ Runden und reduziert die Anzahl unvollständiger Fragment im Erwartungswert um mindestens $1 / 4$ . Nach $t$ Phasen haben wir im Erwartungswert höchstens ${(\frac{3}{4})}^{t} \cdot n$ unvollständige Fragmente; für $t = O (\log n)$ haben wir nach $t$ Phasen mit hoher Wahrscheinlichkeit keine unvollständigen Fragmente mehr.

Wir beschreiben nun eine Phase des Algorithmus. Wir gehen davon aus, dass die Funktion als Menge von Items der Form $u \overset{f}{\mapsto} c$ gegeben ist, und dass eine Maschine, die Item $(u, v)$ besitzt, auch $u \overset{f}{\mapsto} c_{1}$ und $v \overset{f}{\mapsto} c_{2}$ besitzt; dass sie also die Farbe der Knoten an ihren Kanten kennt. Sei $R$ die Relation

\begin{array}{r} R := {(f (u), f (v)) | (u, v) \in E \land f (u) \neq f (v)} . \end{array}

$R$ beschreibt in gewissem Sinne einen Graphen auf der Menge $C$ der Farbklassen, nämlich den Graphen, den wir erhalten, wenn wir jede Farbklasse zu einem Knoten kontrahieren. Ein kleines Detail: die "Relation" $E \subseteq V \times V$ ist symmetrisch und somit ist auch $R$ symmetrisch und kann als ungerichteter Graph betrachtet werden.

Wir können die Relation $R$ in einer Runde erzeugen: für jede Kante $e = (u, v)$ erzeugt die Maschine, auf der $e = (u, v)$ liegt, das Paar $(f (u), f (v))$ , falls $f (u) \neq f (v)$ ist. Möglicherweise wird das gleiche Paar mehrfach erzeugt. Im obigen Beispiel würde zum Beispiel $(2, 1)$ doppelt, $(1, 2)$ doppelt, $(2, 3)$ dreifach und $(3, 2)$ auch dreifach erzeugt werden. Das Paar $(3, 4)$ würde nur einmal erzeugt werden. Wir erzeugen insgesamt höchstens $2 | E |$ solche Paare (höchstens, weil Kanten innerhalb des selben Fragments keine solchen Paare erzeugen).

Die Interpretation des Paares $(f (u), f (v))$ ist: die Kante $(u, v)$ schlägt vor, alle Knoten der Farbe $f (u)$ in Farbe $f (v)$ umfärben; so würde $(u, v)$ vorschlagen, alle blauen Knoten (Farbe 2) in rot (Farbe 1) umzufärben. Dazu müssen sich die Maschinen allerdings pro Farbklasse auf einen Vorschlag einigen: genau das Setting "Relationen auswerten" aus Kapitel 6.4. Hierzu müssen wir Query-Items definieren. Eine Maschine, die ein Kanten-Item $(u, v)$ hat, würde gerne wissen, wohin $u$ umgefärbt werden soll, erzeugt also das Query-Item $(f (u), ?)$ .

Wir rufen jetzt den Algorithmus zum Auswerten von Relationen aus und haben nun eine Funktion $p : C \to C \cup {⊥}$ , mit folgenden Eigenschaften: wenn es für $c$ überhaupt irgendein $(c, c^{'}) \in R$ gibt, dann ist $p (c) \neq ⊥$ ; umgekehrt, wenn $p (c) \neq ⊥$ ist, dann ist $(c, p (c)) \in R$ . Bildlich gesprochen wählt jedes Fragment eine ausgehende Kante, zum Beispiel:

Wir sehen auch: $p (c) = ⊥$ gilt genau dann, wenn $V_{c}$ ein vollständiges Fragment ist, wie das der Farbe 7 im obigen Beispiel. Eine Maschine, die am Anfang der Phase ein Kanten-Item $(u, v)$ besitzt, besitzt am Anfang der Phase auch Items $u \overset{f}{\mapsto} c_{1}$ und $v \overset{f}{\mapsto} c_{2}$ und nun auch noch ein Item der Form $c_{1} \overset{p}{\mapsto} c^{'}$ . Am obigen Beispiel: die Maschine, die $(u, v)$ besitzt, hat auch $u \overset{f}{\mapsto} 2$ und $v \overset{f}{\mapsto} 1$ . Sie hat das Query-Item $(2, ?)$ erzeugt und nun als Antwort $2 \overset{p}{\mapsto} 4$ erhalten. Die Maschinen haben sich darauf geeinigt, Farbe 2 durch Farbe 4 zu ersetzen.

Damit wir keine "zyklischen" Umfärbungen haben und die Anzahl unvollständiger Fragmente tatsächlich abnimmt, müssen wir die Zyklen in $p$ brechen, zum Beispiel oben $2 \overset{p}{\mapsto} 4 \overset{p}{\mapsto} 3 \overset{p}{\mapsto} 2$ . Dies tun wir randomisiert: jede Farbklasse wählt eine Anführerin unter den Machinen; die Anführerin wählt zufällig ein Bit 0 oder 1; wir bewahren nur $p$ -Kanten, die von einer $0$ zu einer $1$ führen. Im MPC-Modell ist das etwas schwieriger, da sich die Maschinen erst einmal einigen müssen, wer pro Farbklasse dieses Zufallsbit wählt, und dieses muss dann auch an alle kommuniziert werden.

Anfüherinnen wählen. Eine Maschine $M_{i}$ mit Item der Form $c \overset{p}{\mapsto} c^{'}$ erzeugt ein Item der Form $⟨ c, i ⟩$ mit der Bedeutung Ich, Maschine $i$ , bin daran interessiert, Farbklasse $c$ umzufärben und stehe als Kandidatin für das Amt der Anführerin von Klasse $c$ zur Verfügung. Gleichzeitig erzeugt sie das Query-Item $⟨ c, ? ⟩$ . Per Relationsauswertung können wir die Relation $⟨ \cdot, \cdot ⟩$ auswerten. Jede Maschine weiß nun, für welche Farbklassen sie Anfüherin ist (wenn überhaupt). Die Anführerin von Farbklasse $c$ wählt nun zufällig ein Bit $b \in {0, 1}$ und erzeugt das Item $c \overset{b i t}{\mapsto} b$ .

Eine Maschine mit Item $(u, v)$ kennt nun also die Farben $c_{1} = f (u)$ und $c_{2} = f (v)$ und auch $c^{'} = p (c)$ . Sie erzeugt Query-Items $c \overset{b i t}{\mapsto} ?$ und $c^{'} \overset{b i t}{\mapsto} ?$ . Eine weitere Relationsauswertung später kennt sie nun das gewählte Bit $b$ von Farbklasse $c$ und das Bit $b^{'}$ von Farbklasse $c^{'}$ . Falls $b = 0$ und $b^{'} = 1$ ist, so wissen wir, dass die Umfärbung von $c$ auf $c^{'}$ durchgeführt werden soll. Die ersetzt das Item $u \overset{f}{\mapsto} c$ durch $u \overset{f}{\mapsto} c^{'}$ .

Und schließlich die neue Färbung:

Dies beendet die aktuelle Phase und läutet die nächste Phase ein. Um die erwartete Anzahl von Phasen zu berechnen, sehen wir, dass jedes unvollständige Fragment $c$ eine ausgehende Kante $c \overset{p}{\mapsto} c^{'}$ haben wird; mit Wahrscheinlichkeit $1 / 4$ ist $b (c) = 0$ und $b (c^{'}) = 1$ und die Umfärbung wird tatsächlich durchgeführt. Das Fragment $c$ geht somit in einem anderen auf, und die Farbe $c$ verschwindet. Sei $F_{t}$ die Anzahl der unvollständigen Fragmente nach $t$ Phasen. Es gilt

\begin{array}{r} E [F_{t + 1} | F_{t} = k] = \frac{3}{4} \cdot k . \end{array}

Wenn es also nach $t$ Phasen $k$ unvollständige Fragmente gibt, dann gibt es nach $t + 1$ Phasen im Erwartungswert $\frac{3}{4} \cdot k$ viele. Es gilt $F_{0} \leq n$ und somit

\begin{array}{r} E [F_{t}] \leq {(\frac{3}{4})}^{t} \cdot n . \end{array}

Wenn wir $t = 2 \log_{4 / 3} (n)$ setzen, dann gilt

\begin{array}{r} E [F_{t}] = {(\frac{3}{4})}^{\log_{4 / 3} n} \cdot n = \frac{1}{n^{2}} \cdot n = \frac{1}{n} . \end{array}

Mit Wahrscheinlichkeit $1 - 1 / n$ also gibt es nach $t$ Phasen keine unvollständigen Fragmente mehr und der Algorithmus kann terminieren.

◻

Übungsaufgabe 6.5.2 Können Sie den Algorithmus so ändern, dass er überprüft, ob es wirklich keine unvollständigen Fragmente mehr gibt, und falls doch, weiterläuft? So dass er schlussendlich Erfolgswahrscheinlichkeit $1$ hat?