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

Catatan: Saya memposting pertanyaan serupa tentang grafik yang tidak diarahkan .

Diberikan

• Sebuah digraf tanpa beberapa sisi atau loop$G$
• Node sumber$s$
• N target node$t$
• Panjang jalur maksimal$l$

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

Perhatikan bahwa saya tidak perlu menyebutkan jalan.

Seperti pertanyaan yang dinyatakan, memiliki sebagai bagian dari input, masalahnya adalah N P -hard. Ini mengikuti sebagai kasus khusus dari klasifikasi kelas pola yang masalah homeomorfisma subgraph yang diarahkan adalah N P -complete oleh Fortune, Hopcroft, dan makalah Wyllie: Masalah homeomorfisme subgraph diarahkan .$l$$\mathsf{NP}$$\mathsf{NP}$

Secara khusus masalah berikut adalah -complete: Diberikan grafik G dan simpul s , t , v , apakah ada (sederhana) ( s , t ) -path melalui v ?$\mathsf{NP}$$G$$s,t,v$$(s,t)$$v$

Pembaruan: jawaban ini tampaknya cacat. Lihat komentar dari Kristoffer Arnsfelt Hansen.

Saya tidak tahu bagaimana menyelesaikan masalah Anda, tetapi di sini ada teknik untuk memecahkan versi sederhana dari masalah Anda: yaitu, diberi edge , uji apakah ada jalur sederhana dari s ke t yang mencakup edge e . (Ini sesuai dengan kasus khusus masalah Anda di mana l = ∞ .)$e$$s$$t$$e$$l=\infty$

Anda dapat memecahkan masalah yang lebih sederhana ini menggunakan "aliran maksimum dengan batas bawah" sebagai subrutin. Dalam masalah max-flow standar, kapasitas setiap tepi memberi kita batas atas pada jumlah aliran yang melewati tepi itu, dan kami mensyaratkan bahwa jumlah aliran di tepi dibatasi lebih rendah oleh 0. Dalam "max-flow dengan batas bawah ", kami diizinkan untuk menentukan batas bawah dan batas atas jumlah aliran melalui tepi itu. Diketahui bahwa "aliran maksimum dengan batas bawah" dapat diselesaikan dalam waktu polinomial.

Sekarang, anggaplah kita memiliki tepi , dan kami ingin menguji apakah ada jalur sederhana dari s ke t yang mencakup tepi e . Kita akan mengatur max-flow dengan masalah batas bawah. Secara khusus, ambil grafik G dan tambahkan simpul baru s 0 dengan tepi s 0 → s dan simpul baru t 1 dengan tepi t → t 1 . Buat kapasitas (batas atas) pada setiap tepi 1. Batas bawah pada semua tepi adalah 0, kecuali batas bawah pada tepi $e \in E$$s$$t$$e$$G$$s_0$$s_0 \to s$$t_1$$t \to t_1$$e$adalah 1. Sekarang periksa apakah ada aliran yang layak dari ke t yang memenuhi semua batas (tes ini dapat dilakukan dalam waktu polinomial, seperti yang disebutkan di atas). Jika tidak ada aliran, maka tidak ada jalur sederhana dari s ke t . Jika ada aliran seperti itu, kemudian menelusuri keluar bahwa aliran menghasilkan jalur sederhana dari s ke t yang mencakup tepi e , sehingga memang ada jalur sederhana tersebut.$s$$t$$s$$t$$s$$t$$e$

Bagaimana kita memecahkan masalah "max-flow dengan batas bawah"? Dalam hal ini, hanya satu sisi yang memiliki batas bawah yang bukan nol. Oleh karena itu, kita dapat menggunakan pendekatan standar untuk aliran jaringan, di mana pada setiap titik kita memilih jalur penambah dengan menghitung jalur terpendek dalam grafik residual - kecuali bahwa di sini kita bertanya (secara kasar) bahwa salah satu jalur penambah mencakup tepi .$e$

Saya belajar ide ini dari makalah berikut:

• Menemukan Jalur Sederhana dengan Banyak Node yang Harus Disertakan . Hars Vardhan, Shreejith Billenahalli, Wanjun Huang, Miguel Razo, Arularasi Sivasankaran, Limin Tang, Paolo Monti, Marco Tacca, dan Andrea Fumagalli. Universitas Texas di Dallas, Laporan Teknis UTD / EE / 2/2009. Juni 2009.

(Pastikan untuk membaca versi laporan teknologi, bukan versi yang diterbitkan. Ide ini ditemukan di paragraf kedua dari pengantar.)

Sayangnya, saya tidak tahu bagaimana untuk memperluas teknik ini untuk memecahkan masalah asli Anda, dengan batas atas Anda pada panjang jalan sederhana.$l$

Atau, kami dapat memecahkan masalah Anda dengan cara langsung menggunakan integer linear programming (ILP). Dalam praktiknya, pemecah ILP cukup bagus pada banyak masalah. Namun, waktu berjalan terburuk mereka masih eksponensial, jadi ini tidak akan memberikan algoritma dengan waktu berjalan terburuk polinomial. Beri tahu saya jika Anda ingin saya menguraikan cara merumuskan ini menggunakan ILP.

Kita dapat menghitung subgraf menggunakan dua pencarian pertama-lebar dan pemindaian melalui node dan tepi dalam waktu O ( V + E ) .$G$$O(V + E)$

Kami melakukan pencarian luas-pertama dari di G untuk mendapatkan BFS penomoran d s ( v ) untuk setiap node v di G . Nomor BFS menunjukkan jumlah tepi di jalur terpendek dari s ke v . Kami juga melakukan pencarian luas-pertama dari t di transpos dari G (yaitu grafik dengan tepi ( v , u ) untuk setiap tepi ( u , v ) di G ) untuk mendapatkan BFS penomoran d t$s$$G$$d_s(v)$$v$$G$$s$$v$$t$$G$$(v,u)$$(u,v)$$G$ untuk setiap node v di G .$d_t(v)$$v$$G$

Untuk setiap simpul dalam G, jalur sederhana terpendek dari s ke t yang melewati v memiliki panjang d s ( v ) + d t ( v ) .$v$$s$$t$$v$$d_s(v) + d_t(v)$

Subgraf berisi simpul v dari G jika dan hanya jika d s ( v ) + d t ( v ) ≤ l dan sebuah edge ( u , v ) jika dan hanya jika d s ( u ) + d t ( v ) ≤ l - 1 .$G'$$v$$G$$d_s(v) + d_t(v) \leq l$$(u,v)$$d_s(u) + d_t(v) \leq l-1$

Berikut adalah algoritma FPT sederhana (di mana adalah parameternya), yang berfungsi untuk kasus terarah dan tidak terarah dalam waktu O ( 2 l ⋅ m ( n + m ) ) , yang mungkin layak jika grafik Anda besar tetapi l adalah cukup kecil. Dalam jawaban saya yang lain, saya memberikan algoritma waktu poli untuk kasus yang tidak diarahkan.$l$$O(2^l\cdot m(n+m))$$l$

Pertama, pertanyaannya adalah setara (hingga faktor di runtime) untuk menanyakan apakah ada jalan ukuran paling l yang masuk melalui beberapa tepi tertentu e . Selanjutnya, idenya adalah untuk memaksa kesederhanaan jalan dengan mempartisi simpul menjadi yang bisa muncul sebelum tepi yang diperiksa dan yang hanya bisa muncul setelah itu di lulus.$m$$l$$e$

Foreach $e=(u,v)\in E$: 
a. do for $O(2^l)$ times:
  1. Compute a random partition of the vertices set $V=(S,V\setminus S)$ 
   such that $s,u\in S$, $v,t\not \in S$ (and every other vertex is in $S$ w.p. 1/2).
  2.Find the shortest path from $s$ to $u$ in the subgraph induced by $S$.
    And the shortest path from $v$ to $t$ in the subgraph of $V\setminus S$. 
  3.If the sum of distances is no more than $l-1$, add $e$ to the output graph.

Analisis
a. Jelas, jika tidak ada jalur sederhana ukuran dalam G yang melewati e , algoritma tidak akan mengembalikannya.$\leq l$$G$$e$

$u$$S$$V\setminus S$$2^{-l}$$O(2^l)$

Derandomisasi

$2^{polylog(l)}$

$(n,l)$$S$$O(2^{l+ log^3(l)}\cdot poly(n))$