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

20

Angenommen, ein GraphG 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 Ω(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.kO((nlogn)/k)n

Wie kann man die Konnektivität von Graphen mit Durchgängen unter Verwendung von festlegen?kO((nlogn)/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(nlogn)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 .)knk


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=2n/2cnck

András Salamon
quelle
Wie unabhängig von ? Wenn es sehr groß sein kann, kann die st-Konnektivität im O ( log 2 n ) -Raum gelöst werden, sodass die Chance für einen Algorithmus besteht, aber wie von azotlichid gezeigt, wahrscheinlich nicht in O ( n log n / k ) . kO(log2n)O(nlogn/k)
Domotorp
Beachten Sie, dass die Pass-Eliminierung von Guha und McGregor für zufällige Algorithmen in die entgegengesetzte Richtung funktioniert und mehr Platz benötigt, um weniger Passes zuzulassen (obwohl der zusätzliche Platz groß ist, wenn der gewünschte Fehler klein ist). Bei dieser Frage wird gefragt, ob durch die Verwendung von mehr Durchläufen der Platzbedarf verringert werden kann.
András Salamon

Antworten:

8

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.

Noam
quelle
1
M. Tompa, Zwei bekannte transitive Verschlussalgorithmen, die keine polynomielle Zeit zulassen, sublineare Raumimplementierungen, SIAM J. Comput. 11 (1), 130–137. dx.doi.org/10.1137/0211010
András Salamon
In diesem Artikel wird ein Algorithmus für die st-Konnektivität angegeben, der gleichzeitig ausgeführt wirdsublinear Raum und Polynom Zeit . “
4

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=Θ(n)O(logn)O(nm)

zotachidil
quelle
3

k

Chad Brewbaker
quelle
Vielen Dank für den Hinweis, dies ist ein interessantes Papier. Die Prozessoren haben gemeinsamen Zugriff auf eine Datenstruktur, die mindestens so groß wie das Diagramm ist. Dies trägt also nicht zur Reduzierung des Speicherplatzbedarfs bei. Es wäre in der Tat interessant, wenn es einen Weg gäbe, den Platzverbrauch durch Ausnutzung der Anzahl der Runden sowie der Anzahl der Prozessoren zu verringern.
András Salamon
2

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

Martin Pál
quelle
1

Auch keine Antwort, aber Sie können in st-Konnektivität entscheiden O(nLogn/k) nicht deterministischer Raum mit kgeht vorbei. Errate einfach den erstenn/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.

domotorp
quelle