Problem ($s$-$t$-Erreichbarkeit)Gegeben ein gerichteter Graph $G = (V,E)$ und zwei Knoten $s, t \in V$: gibt es einen Pfad von $s$ nach $t$?
Falls $G$ ungerichtet ist, dann können wir den Algorithmus für Zusammenhangskomponenten aus dem vorherigen Kapitel laufen lassen und dann überprüfen, ob $s$ und $t$ in der gleichen Zusammenhangskomponente liegen. Für gerichtete Graphen geht das leider nicht mehr. Wir brauchen einen vollständigen Perspektivwechsel.
Definition Sei $G = (V,E)$ ein gerichteter Graph über der Knotenmenge $V = \{1, \dots, n\}$. Die Adjazenzmatrix ist die Matrix $A \in \N^{n \times n}$ mit
\begin{align*} A_{uv} := \begin{cases} 1 & \textnormal{ falls $(u,v) \in E$} \\ 0 & \textnormal{ sonst.} \end{cases} \end{align*}Erinnern Sie sich: ein Kantenzug in $G$ (auf Englisch walk in $G$) ist eine Folge $u_0, u_1, \dots, u_k$ mit $(u_{i-1}, u_i) \in E$ für alle $1 \leq i \leq k$. Also eine Folge von Knoten, bei der zwei aufeinanderfolgende Knoten durch eine Kante verbunden sind. Die Länge des Kantenzuges ist $k$. Ein Kantenzug heißt Pfad, falls die $k+1$ Knoten $u_0, \dots, u_k$ alle verschieden sind.
Lemma Sei $G = (V,E)$ ein gerichteter Graph und $A$ seine Adjazenzmatrix. Mit $A^k$ bezeichnen wir die $k$-te Potenz von $A$ und mit $A^k_{uv}$ den Eintrag von $A^k$ in Zeile $u$ und Spalte $v$. Dann ist $A^k_{uv}$ die Anzahl der Kantenzüge von Länge $k$ mit Startpunkt $u$ und Endpunkt $v$.
Beweis. Wir beweisen das Lemma per Induktion über $k$. Für $k=0$ gilt $A^k = I$, die $(n \times n)$-Einheitsmatrix. Es gilt $I_{uv}=1$ genau dann, wenn $u=v$, ansonsten ist $I_{uv}=0$. Dies ist auch genau die Anzahl der Kantenzüge von Länge $0$ von $u$ nach $v$.
Sei nun $k \geq 1$. Wir schreiben $B := A^{k-1}$ und somit $A^k = A \cdot B$. Nach Induktionshypothese ist $B_{uw}$ die Anzahl der Kantenzüge der Länge $k-1$ von $v$ nach $w$. Für zwei Knoten $u$ und $w$ gilt
\begin{align*} A^k_{uw} & = (A \cdot B)_{uw} = \sum_{v \in V} A_{uv} B_{vw} \\ & = \sum_{v \in V} \left\{ \begin{array}{ll} 1 & \textnormal{ falls $(u,v) \in E$,} \\ 0 & \textnormal{ sonst} \end{array} \right\} \cdot \left\{ \textnormal{Anzahl der Kantenzüge der Länge $k-1$ von $v$ nach $w$} \right\} \\ & = \sum_{\substack{v \in V}\\ (u,v)\in E} \left\{ \textnormal{Anzahl der Kantenzüge der Länge $k-1$ von $v$ nach $w$} \right\} \\ & = \left\{ \textnormal{Anzahl der Kantenzüge der Länge $k$ von $u$ nach $w$} \right\} \\ \end{align*}Die letzte Gleichung gilt, weil jeder $k$-Kantenzug von $u$ nach $w$ die Form $u, v, \dots, w$ hat, wobei $(u,v) \in E$ gilt und $v, \dots, w$ ein Kantenzug der Länge $k-1$ ist. \(\square\)
Die Idee für unseren parallelen Algorithmus für $s$-$t$-Erreichbarkeit ist nun, $A^1, A^2 ,\dots, A^{n-1}$ irgendwie parallel zu berechnen und dann zu schauen, ob irgendwo $A^k_{st}=1$ gilt; hierbei nutzen wir aus, dass ein $s$-$t$-Pfad höchstens Länge $n-1$ haben kann. Als Komplikation ergibt sich noch, dass die Einträge von $A^k$ exponentiell groß werden können: in einem vollständigen Graphen zum Beispiel ist $A^k_{uv} = (n-1)^{k-2} \cdot (n-2) = \Theta(n^k)$.
Übungsaufgabe Die Formel $(n-1)^{k-2}$ ist fehlerhaft. Sei $K_n$ der vollständige gerichtete Graph auf $V = \{1, \dots, n\}$ ohne Selbstschleifen, also
\begin{align*} K_n & = (V, V \times V \setminus \{(v,v) \ | \ v \in V\}) \end{align*}Sei $A$ die Adjazenzmatrix von $K_n$. Finden Sie eine explizite Formel für die Einträge in $A^k$.
Das Problem hoher ganzer Zahlen in $A^k$ lässt sich leicht umgehen. Wir sind ja nicht an der Zahl der Kantenzüge interessiert, sondern nur daran, ob deren Anzahl $0$ oder positiv ist. Wir definieren daher für $A, B \in \{0,1\}^{n \times n}$ das Matrixprodukt $A \odot B$ als
\begin{align} (A \odot B)_{uw} = \bigvee_{v \in V} A_{uv} \wedge B_{vw} \ . \label{def-boolean-product} \end{align}Es gilt nun: $\left(A^{\odot k}\right)_{uv}$ ist $1$ genau dann, wenn es einen Kantenzug der Länge $k$ von $u$ nach $v$ gibt. Wir definieren nun $\tilde{G}$ als den Graphen $G$ plus einer Selbstschleife an jedem Knoten; die Adjazenzmatrix $A$ von $\tilde{G}$ ist genau wie die von $G$, nur dass auf der Diagonale lauter Einsen stehen. Es gilt nun: $A^k_{uv}=1$ genau dann, wenn es in $G$ einen Kantenzug der Länge höchstens $k$ von $u$ nach $v$ gibt. Und somit lösen wir $s$-$t$-Erreichbarkeit, in dem wir schauen, ob
\begin{align*} \left(A^{\odot n}\right)_{st} \end{align*}gleich 1 ist.
Beobachtung Sei $G$ ein gerichteter Graph, $\tilde{G}$ der Graph $G$ plus eine Selbstschleife an jedem Knoten und $A$ die Adjazenzmatrix von $G$. Für $s, t \in V$ gilt: es gibt einen $s$-$t$-Pfad in $G$ genau dann, wenn $\left(A^{\odot (n-1)}\right)_{s,t} = 1$ ist. Hierbei ist $\odot$ das in (\ref{def-boolean-product}) definierte "Boolesche Matrixprodukt".
Ein Boolescher Schaltkreis für $s$-$t$-Erreichbarkeit
Unseren parallelen Algorithmus für $s$-$t$-Erreichbarkeit beschreiben wir als Booleschen Schaltkreis. Sei $d$ so, dass $2^{d-1} \lt n \leq 2^d$ gilt. Wir berechnen $A^{\odot 2^d}$ statt $A^{\odot n}$, was aber das Gleiche ist. Es gilt $d = \ceil{\log n}$. Wir können nun $A^{2^d}$ mit $d$ vielen "$\odot$-Gates" berechnen:
Dies ist im Prinzip die schnelle Matrixmultiplikation, wie Sie sie vielleicht in Theoretischer Informatik 1 gesehen haben. Wir beschreiben nun einen Schaltkreis für $\odot$. Dieser ist sehr groß, aber nicht sehr tief:
Dieser Schaltkreis berechnet $(A \cdot B)_{uw}$ für ein Paar $uw$; wir bauen nun $n^2$ solche Schaltkreise parallel für jedes Paar. Um Fan-in 2 zu erreichen, müssen wir das $\bigvee$ noch durch einen Binärbaum aus $\vee$ ersetzen. Der $\odot$-Schaltkreis hat somit $n^2 \cdot (n + n - 1) in \Theta(n^3)$ Gates. Beachten Sie: das $\Theta(n^3)$ entspricht der $\Theta(n^3)$, das Sie für die Laufzeitkomplexität des "üblichen" Matrixmultiplikationsalgorithmus bekommen. Fassen wir zusammen: ein $\odot$-Schaltkreis hat $O(n^3)$ Gates und Tiefe $O(\log n)$. Der gesamte Schaltkreis für $s$-$t$-Erreichbarkeit hat somit $O(n^3 \log n)$ Gates und Tiefe $O(\log^2 n)$.
Randbemerkung: auf einer Collision CRCW PRAM oder Common CRCW PRAM können wir das in $O(\log n)$ implementieren, weil wir das $\bigwedge$ in $O(1)$ auswerten können.