Subgraf yang berisi semua simpul dan tepi yang merupakan bagian dari jalur st sederhana yang panjangnya terbatas dalam grafik yang tidak diarahkan

Cukup mirip dengan pertanyaan saya yang diposting sebelumnya . Namun kali ini, grafik tidak diarahkan.

Diberikan

Sebuah diarahkan grafik $G$ tanpa multiple-tepi atau loop,
Sumber simpul $s$ ,
Target titik $t$ ,
Panjang jalur maksimal $l$ ,

Saya mencari $G'$ - Subgraf $G$ yang berisi simpul dan tepi $G$ (dan hanya itu), yang merupakan bagian dari setidaknya satu jalur sederhana dari $s$ ke $t$ dengan panjang $\leq l$ .

Catatan:

Saya tidak perlu menyebutkan jalan.
Saya mencari algoritma yang efisien (baik waktu dan memori), karena saya perlu menjalankannya pada grafik yang sangat besar (10 ^ 8 vertex, 10 ^ 9 edge).

ds.algorithms graph-algorithms shortest-path Lior Kogan
sumber

lihat ini. Menemukan makalah ini , yang tampaknya melakukan pengurangan aliran biaya min yang serupa, tetapi menggunakan karakteristik khusus jaringan untuk menyelesaikannya lebih cepat daripada algoritma MCF umum.

Jawaban:

Nah, masalahnya ada di setelah semua. Aku akan menjaga jawaban sebelumnya karena juga bekerja untuk kasus diarahkan (yang NPC, seperti menjawab pada pertanyaan lain), dan menunjukkan itu adalah sehubungan dengan . $P$ $FPT$ $l$

Dalam kasus yang tidak diarahkan, ini dapat dipecahkan, secara deterministik melalui aliran biaya minimum (ini mungkin tidak bekerja pada skala yang Anda maksudkan dalam pertanyaan, tetapi lebih baik daripada algoritma eksponensial.

Prosedur berikut akan memutuskan apakah beberapa sisi harus menjadi bagian dari grafik output. Untuk menjawab masalah awal, lakukan perulangan di semua sisi. $e=(u,v)\in E$

Untuk membuat jaringan aliran, lakukan hal berikut:

Langkah 1: Perluas untuk memiliki simpul dan ganti dengan tepian (mereka diarahkan sebagai bagian dari jaringan aliran), tetapkan biaya ke 0. $e$ $x_e$ $e$ $(u,x_e),$ $(x_e,u),(v,x_e),(x_e,v)$

Langkah 2: ganti setiap simpul , kecuali untuk oleh dua simpul dan , dan tambahkan tepi . Atur biaya tepi ini ke 1. $t$ $x_e$ $t^-$ $t^+$ $(t^-,t^+)$

Langkah 3: Ganti setiap tepi dengan tepi . Setel biaya tepi ini ke 0. $\{a,b\}\in E$ $(a^+,b^-),(b^+,a^-)$

Langkah 4: Menambahkan baru vertex dan menambahkan tepi dengan biaya 0. $y_e$ $(s,y_e),(t,y_e)$

Langkah 5: atur semua kapasitas ke 1.

Sekarang jalankan algoritma aliran biaya min, mencari aliran nilai 2 dari ke . $x_e$ $y_e$

Analisis:

$x_e$ $y_e$ $x_e\leadsto s\to y_e$ $x_e\leadsto t\to y_e$
Path terpisah, karena untuk setiap simpul hanya ada 1 kapasitas dalam busur . $t$ $(t^-,t^+)$
Jalur yang dikembalikan adalah dua jalur yang jumlah jaraknya minimal, dan itu juga biaya aliran yang ditemukan. Ini memungkinkan kita untuk menambahkan ke grafik keluaran atau menghapus yang lain. $e$

BPR
sumber

Lebih mudah untuk memahami argumen dalam jawaban di atas dengan menghilangkan reduksi ke aliran yang diarahkan. Ada jalur sederhana dari ke berisi simpul jika ada jalur dari ke dan jalur dari ke sedemikian rupa sehingga dan adalah simpul terpisah kecuali pada . Ini sangat penting menggunakan arah. Ini dapat diperiksa melalui aliran dan versi biaya juga dapat dilakukan melalui aliran biaya minimum. Orang dapat memeriksa apakah ada jalur sederhana dari ke berisi

s

$s$

t

$t$

v

$v$

P

$P$

v

$v$

s

$s$

Q

$Q$

v

$v$

t

$t$

P

$P$

Q

$Q$

v

$v$

s

$s$

t

$t$

e

$e$ dengan memperkenalkan simpul di tengah .

e

$e$

Chandra Chekuri

@ChandraChekuri - itu benar, tetapi perlu diingat bahwa jika masalahnya tidak memiliki batasan panjang, ada banyak algoritma yang lebih sederhana untuk memutuskannya - lihat di sini

Tentu, saya menyadari solusi itu juga - secara konseptual itu baik untuk memahami komponen yang terhubung melalui jalur terpisah meskipun seseorang dapat menemukan simpul-potong dan komponen yang terhubung langsung melalui DFS.

Chandra Chekuri

@RB: Terima kasih. Algoritme yang disarankan mungkin efektif ketika l relatif besar, tetapi mungkin suboptimal untuk nilai l yang relatif kecil. Saya kira saya dapat memotong G terlebih dahulu dengan menghapus titik lebih jauh dari lantai (l / 2) dari s dan ceil (l / 2) dari t.

Lior Kogan

Cobalah mengadaptasi algoritma jalur terpendek berturut-turut (juga disebut algoritma Surballe untuk kasus 2 jalur yang menarik di sini). Anda ingin mencari jalur 2 terpendek dari (lebih baik menyebutnya daripada karena sama untuk semua tepi) ke setiap . Saya pikir ini bisa dilakukan secara efisien dengan terlebih dahulu menghitung pohon jalur terpendek dari dan kemudian menerapkan perhitungan jalur kedua dengan hati-hati.

y

$y$

y

$y$

y_{e}

$y_e$

x_{e}

$x_e$

y

$y$

Chandra Chekuri

Berikut adalah jawaban yang salah : ini menghasilkan beberapa simpul yang merupakan bagian dari jalur non-sederhana dari ke dan yang bukan bagian dari jalur sederhana dari ke dari panjang . Jawabannya mungkin masih relevan dengan aplikasi penanya, jadi saya meninggalkannya di sini. $s$ $t$ $s$ $t$ $\le \ell$

Berikut ini adalah algoritma yang berjalan dalam waktu (dan sebenarnya lebih cepat dari ini ketika kecil). $O(|V|+|E|)$ $\ell$

Algoritma menjalankan pencarian BFS dari yang berakhir pada kedalaman . BFS ini memberikan satu set dari semua simpul dicapai dari dengan jalan panjang paling , dan juga menghitung jarak untuk setiap . Lalu saya akan melakukan hal yang sama dari dan mendapatkan himpunan dan jarak dari . Akhirnya, simpul yang Anda cari persis . Tepi-tepi itu persis tepi-tepi itu dalam ( $s$ $\ell$ $V_s$ $s$ $\ell$ $dist(s,v)$ $v \in V_s$ $t$ $V_t$ $t$ $V_{solution}=\{ v : v \in V_s \cap V_t, dist(s,v)+dist(t,v) \le \ell \}$ $E[V_{solution}]$ $=(v,u) \in E : u,v \in V_{solution}$ ).

Waktu berjalan dari algoritma ini pastinya adalah karena hanya melakukan dua BFSs. Tetapi waktu sebenarnya adalah yang akan jauh lebih kecil dari ukuran grafik ketika lingkungan -radius dari dan kecil. $O(|V|+|E|)$ $O(|V_s| + |V_t| + |E[V_s]|+|E[V_t]|)$ $\ell$ $s$ $t$

Sunting: mungkin ada algoritma yang agak lebih cepat dalam praktiknya yang melakukan BFS dari dan hanya kedalaman daripada . Ini menemukan semua jalur, dan kemudian dengan sedikit pembukuan Anda dapat menemukan semua simpul. Ini memotong waktu berjalan dengan akar kuadrat untuk kasus grafik tampak acak besar ketika kecil. $s$ $t$ $\ell/2$ $\ell$ $\ell$

pangsit mobius
sumber

Ini tidak memaksa jalan untuk menjadi sederhana. Pertimbangkan grafik jalur sederhana dan . Anda akan mengembalikan sebagai bagian dari output, meskipun tidak ada jalur st sederhana yang melewati ...

t - u - s - v - x

$t-u-s-v-x$

l = 4

$l=4$

v

$v$

v

$v$

Terima kasih atas koreksi @RB. Saya mengedit jawaban saya untuk mencatat bahwa itu salah.

Mobius dumpling

Ini dimaksudkan sebagai komentar, tetapi terlalu lama untuk memposting sebagai komentar.

$G = (V, E)$ $H = (V, E')$ $H = (V, E', w)$

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

Jika ini terdengar bermanfaat, saya dapat mencoba dan menggali konstruksi yang relevan untuk Anda.

GMB
sumber