Menghitung semua pasangan jalur terpisah

10

Mengingat grafik diarahkan dan dua simpul . Sepasang jalur sederhana dari ke adalah edge disjoint jika mereka tidak berbagi edge. $G = (V,E)$ $s,t \in V$ $p_1,p_2$ $s$ $t$

Menggunakan aliran maks, mudah untuk memutuskan apakah ada sepasang jalur disjoint ujung dari ke . Sekarang, apakah ada algoritma waktu tunda polinomial untuk menghitung semua pasangan jalur disjoint tepi dari ke ? $s$ $t$ $s$ $t$

cc.complexity-theory graph-algorithms Amatir
sumber

1

Tidak, karena mungkin ada banyak jalur seperti itu secara eksponensial.

Kaveh

6

@ Kaveh: Saya pikir "algoritma penundaan polinomial" diizinkan untuk mengambil waktu yang eksponensial, selama penundaan antara keluaran panjang secara polinomial. Misalnya, ada algoritma penundaan polinomial yang mencantumkan semua klik maksimal dalam urutan yang meningkat, meskipun jumlah klik maksimal adalah eksponensial.

Robin Kothari

3

Apakah mungkin untuk memasukkan penjelasan tentang keterlambatan polinomial dalam pertanyaan? Saya tidak terbiasa dengan itu sampai saya membaca komentar Robin.

Artem Kaznatcheev

@Robin, Anda benar, saya tidak memperhatikan kata "keterlambatan".

Kaveh

6

Saya percaya jawaban Artem Kaznatcheev benar, tetapi tidak memberikan ruang polinomial. Jadi, inilah pendekatan berbeda yang seharusnya bekerja sedikit lebih baik dalam hal itu.

Dengan menggunakan aliran maks, mungkin untuk menyelesaikan masalah yang sedikit lebih umum: temukan sepasang jalur penjaluran tepi dari beberapa dua simpul {s1, s2} ke beberapa simpul lain {t1, t2}, tetapi tanpa mengendalikan sumber simpul mana yang terhubung ke titik tujuan.

Misalkan kita memiliki grafik G dan simpul s1, s2, t1, t2 yang ingin kita daftarkan semua pasangan jalur. Temukan satu pasangan jalur P1, P2, dan biarkan e = (s1, v) menjadi tepi pertama di salah satu jalur tersebut. Kemudian kita dapat membagi ruang masalah menjadi dua sub-masalah: pasangan jalur yang menggunakan e sama dengan jalur dari {v, s2} ke {t1, t2} di G-s1, dan pasangan jalur yang tidak menggunakan e sama dengan jalur dari {s1, s2} ke {t1, t2} di Ge. Berulang di kedua subproblem ini, dan (untuk menghindari duplikasi) hanya melaporkan jalan ketika Anda berada di bagian bawah rekursi.

David Eppstein
sumber

1

apakah jelas bahwa algoritme tersebut adalah penundaan polinomial jika kita menunggu hingga bagian bawah rekursi?

Artem Kaznatcheev

Rekursi mengambil banyak level secara polinomi ke bawah (karena setiap level menghapus sesuatu dari grafik), dan masing-masing cabang langsung kembali (karena tidak dapat menemukan sepasang jalur) atau melakukan bottom-out dan mengembalikan sesuatu, jadi ya, itu tidak hanya menunda polinomial.

David Eppstein

5

Ini adalah pertama kalinya saya membaca tentang algoritma penundaan polinomial, jadi saya tidak 100% yakin dengan jawaban saya, tapi saya pikir sesuatu seperti berikut ini akan berfungsi.

Pilih beberapa konvensi untuk mewakili jalur yang memiliki total pemesanan alami didefinisikan di atasnya. (Salah satu contoh akan hanya untuk daftar simpul dari jalur dan memesan secara leksikografis). Pilih struktur data in-place yang mendukung pencarian logaritmik dan masukkan (katakan pohon merah-hitam). Biarkan menjadi grafik Anda $<$ $D$ $G$

Tentukan algoritma : $F$

$F(s,t,G, ^*D)$ :

(di sini berarti referensi ke datastructure inplace ) $^*D$ $D$

jalankan algoritma poli-waktu Anda untuk mengembalikan sepasang jalur disjoint edge dengan dari ke . $(P,Q)$ $P < Q$ $s$ $t$
Jika tidak di . $(P,Q)$ $D$

2.1. Masukkan ke (dan hasilkan jika Anda mengira akan keluar saat algoritma berjalan). $(P,Q)$ $D$

2.2. Untuk setiap tepi jalankan $uv \in E(P\cup Q)$ $F(s,t,G - \{uv\}, ^*D)$

$D$ $s,t \in V(G)$ $s < t$ $s \neq t$ $F(s,t,G,*D)$

$PSPACE$ $PSPACE$

Artem Kaznatcheev
sumber

2

$O(m)$

Rui Ferreira
sumber

Menghitung semua pasangan jalur terpisah

Jawaban: