Struktur data untuk jalur terpendek

Biarkan menjadi grafik tidak berarah tanpa bobot dengan simpul dan tepi . Apakah mungkin untuk preprocess dan menghasilkan struktur data ukuran sehingga dapat menjawab pertanyaan dari bentuk "jarak antara dan " dalam waktu O (n)? $G$ $n$ $m$ $G$ $m \cdot \mathrm{polylog}(n)$ $u$ $v$

Masalahnya tampaknya terlalu mendasar untuk dipecahkan.

graph-theory graph-algorithms ds.data-structures ilyaraz
sumber

Menanggapi komentar terakhir Anda tentang "terlalu mendasar untuk tidak terpecahkan": Jika kueri harus dijawab dalam waktu yang konstan, itu memang dipelajari dengan baik. Tetapi inti dari pertanyaan Anda adalah bahwa Anda memberi O (n) waktu untuk kueri (bukan O (1) atau O (m) yang sepele). Meskipun saya pikir itu adalah pertanyaan yang menarik, saya tidak berpikir bahwa pertanyaan itu sangat penting.

Tsuyoshi Ito

@ TsuyoshiIto - Saya tidak melihat mengapa pertanyaan kehilangan "kepentingan mendasar" jika memungkinkan waktu kueri super-konstan tapi sub-linear. Sebagai contoh, misalkan saya dapat menyelesaikan masalah di atas dengan batasan bahwa pertanyaan jarak dapat dijawab dalam waktu untuk beberapa , dan waktu pemrosesan paling banyak - tidakkah ini memberi saya algoritma sub-kubik untuk menghitung jalur terpendek? Saya pribadi berpikir bahwa ini adalah pertanyaan yang sangat menarik.

O (n^{1 - ε})

$O(n^{1-\varepsilon})$

ε > 0

$\varepsilon > 0$

O (n^{3 - ε})

$O(n^{3 - \varepsilon})$

Rachit

Saya tidak tahu ada cara umum atau tidak, tetapi ada cara yang baik dalam grafik treewidth terikat, lihat permintaan Shortest Path dalam grafik treewidth terikat

Saeed

Juga jika Anda dapat membuat pohon jalur terpendek (mulai dari setiap node) dan kemudian menjawab kueri jalur terpendek (oleh root terkait) di , atau dengan cara yang sama mungkin Anda dapat membangun struktur data dengan ukuran memori lebih sedikit.

m = Ω (n^{2})

$m = \Omega(n^2)$

O (n)

$O(n)$

Saeed

Jawaban:

Ini adalah pertanyaan yang sangat menarik. Pada tingkat tinggi, Anda bertanya apakah seseorang dapat memproses grafik sedemikian rupa sehingga kueri jalur terpendek tidak tergantung pada kepadatan grafik, tanpa menggunakan banyak ruang ekstra - menarik, tetapi seperti yang Anda katakan, tidak terselesaikan.

Jika Anda senang dengan perkiraan jarak, berikut adalah cara untuk mendapatkan perkiraan . Misalkan adalah grafik tak berarah tertimbang dengan node dan edge. Hal ini ditunjukkan dalam makalah berikut bahwa untuk perkiraan jarak pertanyaan, merancang struktur data untuk grafik dengan edge tidak lebih sulit daripada grafik di mana setiap node memiliki derajat yang dibatasi oleh : $2$ $G$ $n$ $m$ $m$ $m/n$

R. Agarwal, PB Godfrey, S. Har-Peled, Perkiraan jarak perkiraan dan perutean ringkas dalam grafik jarang, INFOCOM 2011

Jadi, asumsikan bahwa adalah grafik terikat -degree. Sampel node seragam secara acak; sebut titik tengara ini. Selama fase preprocessing, simpan jarak dari setiap titik landmark ke setiap titik lainnya dalam grafik; ini membutuhkan ruang . Untuk setiap simpul , simpan simpul tengara terdekatnya . Juga, simpan grafik dalam struktur data, katakanlah sebagai daftar adjacency. $G$ $m/n$ $\alpha = O(m/n)$ $O(m)$ $u$ $\ell(u)$

Ketika ditanya untuk jarak antara dan , menumbuhkan bola di sekitar kedua node - bola node didefinisikan sebagai set node yang secara ketat lebih dekat ke daripada ke simpul landmark terdekat, katakan . Dapat ditunjukkan bahwa ukuran masing-masing bola adalah , sesuai harapan. Misalkan , di mana adalah bola dari simpul dan adalah himpunan tetangga dari simpul dalam . Dapat ditunjukkan bahwa ukuran adalah , sesuai harapan. $u$ $v$ $w$ $w$ $\ell(w)$ $O(n^2/m)$ $\Gamma(u) = B(u) \cup N(B(u))$ $B(u)$ $u$ $N(B(u))$ $B(u)$ $\Gamma(u)$ $O(n)$

Menjawab pertanyaan: jika , kembalikan ; selain itu jika , kembalikan ; lain kembalikan . Sangat mudah untuk menunjukkan bahwa ini adalah approximation. $\Gamma(u) \cap \Gamma(v) \neq \emptyset$ $\min_{x \in \Gamma(u) \cap \Gamma(v)} \{d(u, x) + d(v, x)\}$ $d(u, \ell(u)) \leq d(v, \ell(v))$ $d(u, \ell(u)) + d(\ell(u), v)$ $d(v, \ell(v)) + d(\ell(v), u)$ $2$

Dalam hal waktu kueri, perhatikan bahwa bola tumbuh membutuhkan waktu untuk grafik terikat -degree; membangun dan mengingat masing-masing bola membutuhkan waktu (karena tetangga disimpan dalam struktur data); dan memeriksa apakah kosong atau tidak juga membutuhkan waktu. $O(n)$ $m/n$ $\Gamma(u)$ $\Gamma(v)$ $O(n)$ $\Gamma(u) \cap \Gamma(v)$ $O(n)$

Batas di atas dalam harapan; Saya pikir itu mudah untuk derandomize konstruksi. Sayangnya, teknik ini tampaknya tidak memungkinkan mendapatkan perkiraan yang lebih baik dari . Ini pertanyaan yang sangat menarik .... $2$

Rachit
sumber

Teknik di atas tidak memanfaatkan fakta bahwa grafik input Anda tidak berbobot; mungkin ada sesuatu yang menarik yang dapat Anda lakukan dengan mengeksploitasi fakta itu tetapi saya tidak bisa memikirkan cara untuk mengambil jarak yang tepat. Misalnya, dimungkinkan untuk mengurangi waktu kueri menjadi dan mendapatkan jarak yang dibatasi oleh , di mana adalah jarak yang tepat antara dan .

O (n^{2} / m)

$O(n^2/m)$

2 d + 1

$2d+1$

d

$d$

u

$u$

v

$v$

Rachit

Saya menyadari bahwa saya tidak mengerti mengapa ini adalah perkiraan 2. Thorup-Zwick dalam situasi yang sama memberikan 3-kira-kira.

ilyaraz

@ilyaraz: Perhatikan bahwa skema Thorup-Zwick tidak perlu memeriksa (dan karenanya, menjawab pertanyaan dalam waktu yang hampir konstan). Lihat kertas yang saya sebutkan di atas untuk stretch proof.

Γ (u) \cap Γ (v)

$\Gamma(u) \cap \Gamma(v)$

2

$2$

Rachit

Yang Anda butuhkan disebut "oracle jarak". Sayangnya, saya tidak terlalu akrab dengan oracle jarak, jadi saya hanya bisa merujuk Anda ke makalah mani karena Thorup dan Zwick:

Mikkel Thorup dan Uri Zwick. Perkiraan jarak oracle. STOC '01, 2001.

Berikut adalah kutipan dari abstrak:

Misalkan menjadi grafik tertimbang yang tidak diarahkan dengan dan . Biarkan menjadi bilangan bulat. Kami menunjukkan bahwa dapat diproses sebelumnya dalam waktu yang diharapkan, membangun struktur data ukuran , sedemikian rupa sehingga selanjutnya kueri jarak dapat dijawab, kira-kira, dalam waktu . Perkiraan jarak yang dikembalikan adalah peregangan paling banyak , yaitu, hasil bagi yang diperoleh dengan membagi perkiraan jarak dengan jarak sebenarnya terletak antara 1 dan . [...] Persyaratan ruang dari algoritma kami adalah [...] pada dasarnya optimal. $G = (V, E)$ $|V| = n$ $|E| = m$ $k$ $G = (V, E)$ $O(kmn^{1/k})$ $O(kn^{1+1/k})$ $O(k)$ $2k - 1$ $2k - 1$

Menurut hasil mereka, apa yang Anda minta pada dasarnya bisa dilakukan bahkan untuk grafik berbobot: memilih menghasilkan jarak oracle ukuran diperoleh dalam waktu yang diharapkan , yang dapat menjawab kueri jalur terpendek Anda dengan -ringkas dalam waktu! $k=1$ $O(n^2)$ $O(mn)$ $1$ $O(1)$

Oracle jarak adalah bidang yang diteliti dengan sangat baik, sehingga Anda akan dapat menggali lebih lanjut saya percaya.

Gabor Retvari
sumber

Versi jurnal: JACM 2005 .

Tsuyoshi Ito

Dengan menggunakan ruang dapat menyimpan tabel pencarian secara naif. Jadi, makalah ini (yang saya sadari) tidak relevan di sini.

O (n^{2})

$O(n^2)$

ilyaraz

Cukup adil. Hasil yang paling dekat dengan apa yang Anda minta AFAIK adalah untuk grafik dengan derajat rata-rata yang memberikan lintasan stretch-2 dengan ruang di kueri waktu. (R. Agarwal, P. Godfrey, dan S. Har-Peled, "Perkiraan Kueri Jarak dan Perutean Ringkas dalam Grafik Jarang", INFOCOM 2011.)

Θ (\log n)

$\Theta(\log n)$

O (n^{3 / 2})

$O(n^{3/2})$

O (\sqrt{n})

$O(\sqrt{n})$

Gabor Retvari

Dengan menggunakan metrik yang dimasukkan oleh Bourgain ke , orang dapat membuat oracle dengan spasi , waktu kueri dan kesalahan multiplikasi .

ℓ_{1}

$\ell_1$

O (n \log^{2} n)

$O(n \log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log n)

$O(\log n)$

ilyaraz