Mengurangi penggunaan ruang konektivitas-st dengan banyak lintasan?

Misalkan grafik dengan n simpul disajikan sebagai aliran tepi m , tetapi beberapa lintasan diizinkan melewati aliran.$G$$n$$m$

Monika Rauch Henzinger, Prabhakar Raghavan, dan Sridar Rajagopalan mengamati bahwa ruang diperlukan untuk menentukan apakah ada jalur antara dua simpul yang diberikan dalam G , jika k pass diizinkan pada data. (Lihat juga versi laporan teknis .) Namun, mereka tidak menyediakan algoritma untuk benar-benar mencapai batas ini. Saya berasumsi bahwa algoritma optimal sebenarnya akan mengambil O ( ( $\Omega(n/k)$$G$$k$ ruang dalam model komputasi realistis, karena kita harus membedakan n simpul yang berbeda jika seseorang tidak dapat mengindeks memori menggunakan pointer ukuran konstan.$O((n\, \log\, n)/k)$$n$

Bagaimana seseorang dapat memutuskan konektivitas grafik dengan pass menggunakan O ( ( $k$ ruang?$O((n\, \log\, n)/k)$

Jika hanya satu lintasan diperbolehkan, data input dapat disimpan sebagai partisi dari set simpul, menggabungkan set jika tepi terlihat antara simpul dalam dua set berbeda. Ini jelas membutuhkan paling banyak ruang. Pertanyaan saya adalah tentang k > 1 : bagaimana cara menggunakan lebih banyak pass untuk mengurangi ruang yang dibutuhkan?$O(n\, \log\, n)$$k > 1$

(Untuk menghindari hal-hal sepele, adalah parameter yang tidak dapat dibatasi apriori oleh konstanta, dan batas ruang adalah ekspresi yang melibatkan fungsi n dan k .)$k$$n$$k$

Pembaruan: bahkan untuk akan sangat berguna untuk memiliki cara untuk menyimpan hanya n / 2 simpul. Atau ada sebenarnya lebih kuat batas bawah c n untuk beberapa konstan c , terlepas dari k ?$k=2$$n/2$$cn$$c$$k$

Ini adalah masalah terbuka yang lama untuk menemukan algoritma untuk st-konektivitas yang berjalan secara simultan dalam ruang sub-linear dan waktu polinomial, tugas yang lebih mudah daripada apa yang Anda tuju. Algoritma semacam itu dikenal untuk versi yang tidak diarahkan , tetapi bahkan ini membutuhkan waktu polinomial yang besar (daripada waktu O (km) yang akan tersirat oleh algoritma k-pass). Lihat terutama referensi ke kertas Tompa tentang mengapa kasus yang diarahkan tampaknya sulit.

Ini bukan jawaban, tapi saya hanya ingin menunjukkan bahwa jika Anda dapat menyelesaikan masalah ini untuk , maka Anda memecahkan st-konektivitas dalam ruang O ( log n ) dan waktu O ( n m ) (yang dalam kasus offline, Anda dapat melakukannya dengan probabilitas> 1/2 dengan melakukan jalan acak; tetapi tampaknya sedikit lebih sulit ketika tepiannya berasal dari aliran). Pertanyaan yang sangat menarik, IMO.$k = \Theta(n)$$O(\log n)$$O(nm)$

Yossi Shiloach, Uzi Vishkin. Algoritma Konektivitas Paralel O (log n). J. Algorithms, 1982: 57 ~ 67 - Salah satu makalah favorit saya. Akan menarik jika Anda bisa melakukannya di ruang O ((nlogn / k) / p) dengan prosesor p di putaran di mana setiap putaran masing-masing prosesor hanya diperbolehkan membaca di O (n / p) pada tepiannya.$k$

Namun jawaban lain: ada beberapa makalah tentang algoritma gaya mapreduce yang beroperasi pada grafik besar. Tujuannya adalah untuk mencapai ruang per-mesin o (m) untuk grafik padat, tetapi biasanya membutuhkan O (n) ruang per mesin.

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

$O(n\log n/ k)$$k$$n/k$$st$$n/k$$n/k$$st$