Memangkas digraf yang sangat terhubung

10

Mengingat digraf G yang sangat terhubung dengan tepi berbobot, saya ingin mengidentifikasi tepian yang terbukti bukan bagian dari subgraph minimal terhubung kuat (MSCS) dari G.

Salah satu metode untuk menemukan tepi tersebut adalah algoritma Floyd-Warshall yang dimodifikasi. Dengan menggunakan algoritma Floyd-Warshall, orang dapat mengidentifikasi tepi mana yang tidak pernah merupakan pilihan terbaik untuk beralih dari vertex i ke j. Node ini tidak dapat menjadi bagian dari MSCS karena lebih baik menggantinya dengan dua atau lebih tepi lainnya.

Teknik pemangkasan Floyd-Warshall bekerja cukup baik ketika bobot tepi bervariasi secara signifikan, tetapi sangat buruk ketika bobot tepi serupa tetapi besarnya besar.

Apakah Anda tahu metode pemangkasan efektif untuk bobot tepi besar dan serupa? Apakah masalah ini setara dengan masalah yang lebih umum yang tidak saya kenali? Apakah pemangkasan semacam ini telah dipelajari sebelumnya dalam literatur?

ds.algorithms graph-theory graph-algorithms Nate
sumber
1
Saya tidak bisa menjawab pertanyaan itu tanpa membaca literatur tentang masalahnya. Sudahkah Anda mencoba membaca literatur sendiri? Bisakah Anda meringkas apa yang Anda temukan?
Warren Schudy
1
Banyak literatur yang berkaitan dengan menemukan algoritma aproksimasi, beberapa di antaranya cukup baik. Sebagian besar beroperasi melalui kontraksi siklus, dengan hasil yang baik. Saya mengalami kesulitan menemukan literatur untuk pemangkasan dan bukan perkiraan, itulah sebabnya saya bertanya-tanya apakah masalah pemangkasan adalah generalisasi dari masalah yang lebih umum yang dapat saya baca. Setiap tips terkait literatur apa yang akan diterima.
Nate
1
Fungsi apa yang sedang diperkirakan oleh algoritma aproksimasi dan bagaimana perbedaannya dari pemangkasan?
Suresh Venkat
Perkiraan mendekati subgraph minimal yang sangat terhubung. Seperti yang saya katakan, mereka sering menggunakan kontraksi siklus untuk melakukannya. Pemangkasan melalui kontraksi siklus dapat menghasilkan subgraph yang tidak optimal (karenanya, perkiraan). Saya ingin memangkas sedemikian rupa sehingga saya dapat menjamin bahwa saya belum memotong setiap tepi yang muncul pada MSCS.
Nate

Jawaban:

3

Kami berasumsi bahwa edge edge adalah bilangan bulat positif. Mengingat grafik diarahkan G dengan bobot tepi, sebut keunggulan e berlebihan jika e tidak milik setiap minimum berat badan sangat-terhubung mencakup subgraphs dari G .

Kami mengklaim bahwa kecuali P = NP, tidak ada algoritma waktu polinomial yang selalu menemukan tepi redundan dalam grafik berarah yang diberikan dengan bobot tepi selama ada. Lebih tepatnya:

Teorema . Diberi grafik G terarah dengan bobot tepi, NP-sulit untuk menemukan tepi redundan di G atau menyatakan bahwa G tidak memiliki tepi redundan.

Bukti . Pengamatan kuncinya adalah bahwa jika G memiliki subgraph spanning berat minimum yang terhubung kuat dan unik , maka Anda dapat menghitung subgraph itu dengan menghilangkan tepi yang berlebih satu per satu. Oleh karena itu, tetap menunjukkan bahwa keunikan tidak membuat masalah subgraph spanning dengan bobot minimum yang terhubung lebih mudah, tetapi ini dibuktikan oleh Lemma berikutnya. QED .

Lemma . Diberikan grafik G terarah dengan bobot tepi, NP-sulit untuk menghitung berat subgraf spanning terkoneksi-bobot rendah-berat G bahkan di bawah janji bahwa G memiliki subgraph spanning minimum-weight-link unik yang unik.

Bukti . Seperti yang Anda tahu , masalah tanpa janji adalah NP-hard (bahkan untuk kasus berat unit) dengan pengurangan dari masalah sirkuit Hamilton. Kami mengurangi masalah tanpa janji untuk masalah dengan janji.

Biarkan G menjadi grafik berarah dengan bobot tepi. Label tepi G oleh e 0 , e 1 , ..., e m -1 , dimana m adalah jumlah tepi di G . Biarkan w i menjadi bobot yang diberikan dari tepi e i . Biarkan bobot baru w ′ i = 2 m w i +2 i . Maka mudah untuk memverifikasi bahwa G dengan bobot baru memiliki subgraf spanning unik dengan bobot minimum yang terhubung dengan kuat. Juga mudah untuk memverifikasi bahwa berat minimumW dari subgraf spanning yang terhubung kuat dalam G dengan bobot asli dapat dihitung dari bobot minimum W ′ dalam G dengan bobot baru sebagai W = ⌊ W ′ / 2 m ⌋. QED .

Tsuyoshi Ito
sumber
2
Ya, jelas, sulit untuk menemukan semua sisi seperti itu. Saya tidak mencari semua tepi seperti itu, saya mencari satu set tepi yang dapat Anda tentukan mampu memotong dalam waktu polinomial. Algoritma Floyd-Warshall dapat digunakan untuk menemukan satu set tepi seperti itu, seperti dijelaskan di atas. Saya bertanya-tanya apakah ada cara lain untuk mengidentifikasi subset dari tepi yang dapat dilepas dalam waktu polinomial.
Nate