Digraph Reachability Algorithms
Daniel Wolleb-Graf · Repository for Publications and Research Data (ETH Zurich) · 2018
Take a blank page, draw some small circles, and connect them with a few arrows, and voilà you created a directed graph, a digraph for short.Now let us ask an algorithmic question: If I point out two of those circles to you, one as the start and one as the target, can you find a way to go from the start to the target by only using the arrows in their one-way direction?While this reachability question is well-studied, we found new algorithms for the following slight variations of the reachability problem: What if we ask this questions for many starts and many targets while we also add and remove arrows in between answering these questions?What if we want to find two ways from the start to the target that use completely different arrows?Or can we even find three disjoint paths?And how fast can we compute the answer for all combinations of starts and targets?Zusammenfassung Nehmen Sie ein leeres Blatt, zeichnen Sie einige kleine Kreise und verbinden Sie diese mit einigen Pfeilen, und schon haben Sie einen gerichteten Graphen kreiert.Nun stellen wir uns eine algorithmische Frage: Wenn ich auf zwei der Kreise zeige, einen als Start und einen als Ziel, können Sie einen Weg finden, um vom Start zum Ziel zu gelangen und dabei nur Pfeile in entlang ihrer Richtung benutzen?Diese Erreichbarkeitsfrage ist altbekannt, aber wir haben neue Algorithmen für die folgenden Variationen des Erreichbarkeitsproblems gefunden: Was passiert, wenn wir diese Frage für viele Start-und Zielkreise stellen und dazwischen auch noch Pfeile hinzufügen und entfernen?Was, wenn wir zwei Wege vom Start ins Ziel finden möchten, die komplett unterschiedliche Pfeile benutzen?Oder können wir gar drei disjunkte Pfade finden?Und wie schnell können wir die Antwort für alle Kombinationen von Start und Ziel berechnen?Für das dynamische Erreichbarkeitsproblem fassen wir zuerst die Link-Cut Tree Datenstruktur für dynamische gewurzelte Wälder zusammen, bevor wir sie auf einen neue Klasse von dynamischen Graphen ausbauen: Graphen von partiellen Funktionen.Wir stellen einen Algorithmus vor, der Anfragen und Aktualisierungen in beliebiger Reihenfolge in der Zeit O(log n) verarbeitet.Im verallgemeinerten Erreichbarkeitsproblem fragen wir nach der Existenz von mehreren kantendisjunkten Pfaden zwischen den Anfrageknoten.Das Alle-Paare-k-Erreichbarkeitsproblem fragt nach der Anzahl kantendisjunkter Wege zwischen allen Knotenpaaren, wobei die Antwort "mindestens k" gegeben werden kann, wann immer es k oder mehr kantendisjunkte Wege gibt.2-Erreichbarkeit beantwortet die Frage nach der Ausfallsicherheit von Wegen, d.h.ob es eine Kante gibt, die auf einem Weg von u nach v nicht umgangen werden kann.Wir stellen als unser Hauptresultat einen Algorithmus vor, der in Zeit O(n ω log n) die 2-Erreichbarkeit zwischen allen Knoten eines beliebigen gerichteten Graphen berechnet, wobei ω der Matrixmultiplikationsexponent ist.Das Resultat besteht aus drei Schritten: zuerst entwickeln wir eine Pfadalgebra mit binären Kodierungen für azyklische Graphen, dann benutzen wir Dominatorbäume, um Hilfsgraphen zu bauen, welche die Antwort für stark zusammenhängende Graphen repräsentieren, und am Ende kombinieren wir die beiden auf beliebigen gerichteten Graphen.Schliesslich schauen wir uns das generelle k-Erreichbarkeitsproblem auf azyklischen Graphen an.Wir entwickeln einen Rahmen, um mit der Struktur von extremalen Schnitten umzugehen und um diese Schnitte effizient zu codieren und zu manipulieren, und bauen damit zwei Algorithmen für DAGs: einer läuft in Zeit O(mn 1+o(1) ) für k = o( √ log n) und einer in Zeit O(n ω+o(1) ) für k = o(log log n).Ein hübscher Nebeneffekt dieser Algorithmen ist, dass sie nicht nur die Grösse des minimalen Schnitts bestimmen, sondern auch gleich einen Schnitt als Zeuge liefern.And how fast can we compute the answer for all combinations of start and target circles?