Menemukan min-max vertex-disjoint paths dengan sumber yang sama pada grafik planar

Diberikan grafik tanpa planar planar, dan kumpulan pasangan simpul ( adalah sebuah konstanta), temukan titik-disjoint (kecuali sumber) jalur dari ke sedemikian rupa sehingga panjang jalur terpanjang diminimalkan. $(s,t_1),\dots,(s,t_k)$ $k\ge2$ $k$ $s$ $t_i$

Pertanyaan: Apakah ada algoritma waktu polinomial untuk masalah?

Beberapa hasil terkait:

jika tidak diperbaiki masalahnya adalah NP-hard bahkan jika ; $k$ $t_1=\dots=t_k$
jika grafik input ditimbang dan sumber jalur tidak bersamaan, yaitu jalur adalah masalahnya adalah NP-hard bahkan untuk ; $(s_1,t_1),\dots,(s_k,t_k)$ $k=2$
masalah dengan tujuan yang berbeda, yaitu meminimalkan jumlah panjang jalur, adalah
- dipecahkan dengan algoritma aliran biaya minimum untuk sumber bertepatan;
- NP-hard untuk sumber yang tidak bersamaan dan umum ; $k$
- terbuka untuk sumber yang tidak sesuai dan konstan . $k$

ds.algorithms graph-algorithms Sergey Pupyrev
sumber

Tampaknya ada banyak hasil terkait. Bisakah Anda merangkum hasil terkait penting dalam pertanyaan?

Tsuyoshi Ito

Apakah grafik input G berbobot (yaitu, setiap tepi memiliki panjang bilangan positif)? Saya telah mengasumsikan bahwa G tidak berbobot, tetapi saya telah menyadari bahwa Anda mungkin mencampuradukkan dua pengaturan: (1) Jika G ditimbang, maka kasus k = 2 adalah NP-lengkap pada dasarnya oleh Teorema 14 di koran oleh Kobayashi dan Sommer yang Anda tautkan, yang pada dasarnya juga sama dengan paragraf terakhir di Bagian 2 [HP02] yang dikutip dalam jawaban saya. (2) Jika G tidak berbobot, maka saya tidak bisa melihat mengapa kertas oleh Kobayashi dan Sommer menyiratkan kekerasan NP dalam kasus k = 2 dan sumber yang berbeda.

Tsuyoshi Ito

Dalam pengaturan saya, grafik tidak berbobot, jadi Anda benar: klaim saya tentang NP-hardness dalam kasus K = 2 dan sumber yang berbeda (mungkin) salah.

Sergey Pupyrev

Saya telah memperbarui pernyataan masalah dengan mempertimbangkan komentar Tsuyoshi Ito.

Sergey Pupyrev

Jawaban:

Ini bukan apa yang Anda tanyakan, tetapi masalahnya adalah NP-lengkap jika k bukan konstanta tetapi bagian dari input.

Ini mengikuti dari bukti Teorema 1 di van der Holst dan de Pina [HP02], yang mengatakan: diberikan grafik planar G , simpul s dan t berbeda dalam G , dan bilangan bulat positif k dan b , NP-lengkap untuk memutuskan apakah ada k berpasangan secara internal jalur vertex-disjoint antara s dan t masing-masing panjang paling banyak b .

Perhatikan bahwa masalah dalam pernyataan Teorema 1 berbeda dari Anda dalam dua hal. Salah satu perbedaannya adalah, seperti yang saya sebutkan, bahwa k diberikan sebagai bagian dari input. Yang lain adalah bahwa masalah dalam [HP02] adalah tentang jalur dengan titik akhir yang sama, bukan jalur dengan sumber yang sama dan sink yang berbeda. Saya tidak tahu bagaimana cara memperbaiki perbedaan pertama; perbedaannya begitu besar sehingga kemungkinan kita akan membutuhkan bukti yang sama sekali berbeda untuk memperbaikinya k . Tapi saya tahu setidaknya bagaimana cara memperbaiki perbedaan kedua.

Bukti Teorema 1 dalam [HP02] memberikan pengurangan dari 3SAT. Reduksi ini memiliki sifat sebagai berikut: dalam instance ( G , s , t , k , b ) dibangun oleh reduksi, derajat verteks t selalu sama dengan k . Mari t ₁ , ..., t _k menjadi k tetangga t . Kemudian alih-alih bertanya apakah ada k secara berpasangan secara internal jalur-disjoint antara s dan t masing-masing panjang paling banyak b, kita dapat sama-sama bertanya apakah ada jalur berpasangan-disjoint-kecuali-sumber P ₁ , ..., P _k sedemikian rupa sehingga setiap P _i adalah jalur antara s dan t _i dengan panjang paling banyak b −1.

[HP02] H. van der Holst dan JC de Pina. Jalur disjoint panjang terikat dalam grafik planar. Discrete Applied Mathematics , 120 (1-3): 251–261, Agustus 2002. http://dx.doi.org/10.1016/S0166-218X%2801%2900294-3

Tsuyoshi Ito
sumber

k

$k$

k

$k$

@SergeyPupyrev: Anda menulis bahwa k adalah konstanta. (Anda menulisnya karena Anda tahu apa artinya, bukan?) Dari apa yang saya pelajari dari pandangan sepintas di makalah yang relevan, apakah k adalah konstan atau tidak dalam masalah terkait tampaknya membuat perbedaan besar dalam status saat ini dari kompleksitas masalah.

Tsuyoshi Ito

k

$k$

k

$k$

@SergeyPupyrev: Saya tidak dapat menemukan kertas yang menyatakan kompleksitas dalam kasus di mana k adalah konstanta, tetapi ini hanya berarti bahwa itu tidak diketahui oleh saya .

Tsuyoshi Ito