Reduzierung des Platzbedarfs für st-connectivity mit mehreren Durchläufen?

Angenommen, ein Graph$G$ mit $n$ Eckpunkten wird als Strom von $m$ Kanten dargestellt, aber es sind mehrere Durchgänge über den Strom zulässig.

Monika Rauch Henzinger, Prabhakar Raghavan und Sridar Rajagopalan stellten fest, dass ein $\Omega(n/k)$ -Raum erforderlich ist, um zu bestimmen, ob es einen Pfad zwischen zwei gegebenen Eckpunkten in $G$ , wenn Durchgänge über die Daten zulässig sind. (Siehe auch die Version des technischen Berichts .) Sie bieten jedoch keinen Algorithmus, um diese Grenze tatsächlich zu erreichen. Ich gehe davon aus, dass ein optimaler Algorithmus in einem realistischen Rechenmodell tatsächlich Platz beansprucht, da man die n verschiedenen Eckpunkte unterscheiden muss, wenn man den Speicher nicht mit Zeigern konstanter Größe indizieren kann.$k$$O((n\, \log\, n)/k)$$n$

Wie kann man die Konnektivität von Graphen mit Durchgängen unter Verwendung von festlegen?$k$$O((n\, \log\, n)/k)$

Wenn nur ein Durchgang zulässig ist, können die Eingabedaten als Partition der Scheitelpunktmenge gespeichert werden, wobei Sätze zusammengeführt werden, wenn eine Kante zwischen Scheitelpunkten in zwei verschiedenen Sätzen sichtbar ist. Dies erfordert eindeutig höchstens Raum. Meine Frage ist zu k > 1 : Wie kann man mehr Pässe verwenden, um den benötigten Platz zu reduzieren?$O(n\, \log\, n)$$k > 1$

(Zur Vermeidung von Trivialität ist ein Parameter, der nicht von vornherein durch eine Konstante begrenzt werden kann, und die Raumgrenzen sind Ausdrücke, die Funktionen von n und k beinhalten .)$k$$n$$k$

Update: Selbst für wäre es sehr nützlich, nur n / 2 Vertices zu speichern . Oder gibt es tatsächlich eine stärkere Untergrenze c n für eine Konstante c , unabhängig von k ?$k=2$$n/2$$cn$$c$$k$

Es ist ein seit langem offenes Problem, einen Algorithmus für die St-Konnektivität zu finden, der gleichzeitig im sublinearen Raum und in der Polynomzeit abläuft. Dies ist eine einfachere Aufgabe als das, was Sie anstreben. Derartige Algorithmen sind für die ungerichtete Version bekannt , aber selbst diese erfordern eine große Polynomzeit (anstelle der O (km) -Zeit, die ein k-Pass-Algorithmus implizieren würde). Siehe insbesondere den Verweis auf Tompas Aufsatz, warum der gerichtete Fall schwierig zu sein scheint.

Dies ist keine Antwort, aber ich wollte nur darauf hinweisen, dass, wenn Sie dieses Problem für lösen können, Sie die st-Konnektivität im Raum O ( log n ) und in der Zeit O ( n m ) (welche ) lösen im Offline-Fall kann man mit einer Wahrscheinlichkeit> 1/2 einen zufälligen Spaziergang machen, aber es scheint etwas schwieriger zu sein, wenn die Kanten von einem Stream stammen. Sehr interessante Frage, IMO.$k = \Theta(n)$$O(\log n)$$O(nm)$

$k$

Noch eine Nicht-Antwort: Es gibt einige Artikel über Mapreduce-Algorithmen, die mit großen Graphen arbeiten. Das Ziel besteht darin, für dichte Graphen pro Maschine den Platz o (m) zu erreichen, normalerweise wird jedoch der Platz O (n) pro Maschine benötigt.

theory.stanford.edu/~sergei/papers/soda10-mrc.pdf http://theory.stanford.edu/~sergei/papers/spaa11-matchings.pdf

Auch keine Antwort, aber Sie können in st-Konnektivität entscheiden $O(n\log n/ k)$ nicht deterministischer Raum mit $k$geht vorbei. Errate einfach den ersten$n/k$ Knoten eines $st$ Verfolge und überprüfe, ob sie in der ersten Runde verbunden sind, und fahre dann mit der letzten fort $n/k$ Scheitelpunkte und überprüfen Sie die nächste $n/k$ von dem $st$ Pfad und so weiter.