Hitung maks-flow dari min-cut

Kita tahu bahwa menghitung aliran arus maksimum. potongan minimum jaringan dengan kapasitas setara; lih. yang max-flow min-cut teorema .

Kami memiliki (kurang lebih efisien) algoritma untuk menghitung aliran maksimum, dan menghitung potongan minimum mengingat aliran maksimum juga tidak sulit atau mahal.

Tapi bagaimana dengan yang sebaliknya? Diberikan potongan minimum, bagaimana kita bisa menentukan aliran maksimum? Tanpa menyelesaikan Max-Flow dari awal, tentu saja, dan lebih baik lebih cepat dari itu juga.

Beberapa pemikiran:

Dari potongan minimum, kita tahu nilai aliran maksimum. Saya tidak melihat bagaimana informasi ini membantu pendekatan standar menambah jalur dan push-relabel, meskipun mengadaptasi yang terakhir tampaknya sedikit lebih masuk akal.
Kami tidak dapat menggunakan potongan minimum untuk membagi jaringan menjadi dua bagian dan berulang karena itu tidak akan mengecilkan masalah dalam kasus terburuk (jika satu partisi adalah singleton); juga kami tidak akan memiliki potongan minimum dari contoh yang lebih kecil.
Apakah mengetahui nilai aliran maksimum mempercepat penyelesaian Max-Flow LP, mungkin melalui kondisi kelonggaran yang saling melengkapi?

algorithms graphs network-flow Raphael
sumber

Pertanyaan terkait: apakah kita tahu algoritma untuk menghitung pemotongan minimum (yang tidak menggunakan algoritma aliran maksimum)?

Raphael

Kami benar-benar melakukannya, algoritma acak Karger adalah yang sangat populer, dan Anda membutuhkan nol pengetahuan tentang max-flow untuk itu.

Juho

Jika Anda tidak ingin algoritma acak, algoritma Stoer-Wagner adalah yang sangat sederhana, juga tanpa teknik aliran.

Juho

Barang bagus! Ada tantangan lain di sini. Mengetahui min-cut hanya menyampaikan

bit informasi (paling banyak), karena setiap potong adalah isomorfik untuk subset dari

. Namun, aliran maks dapat membutuhkan lebih dari

bit informasi untuk diwakili (terutama jika kapasitasnya besar). Jadi, informasi-secara teoritis, Anda tidak bisa berharap untuk algoritma yang hanya melihat pada cut dan meludahkan arus; itu juga perlu melihat grafik, dan melakukan beberapa perhitungan tambahan. (Saya menyadari ini bukan banyak penghalang.)

| V |

$|V|$

V

$V$

| V |

$|V|$

Jawaban:

Dalam kasus terburuk, pemotongan minimum itu sendiri tidak menyampaikan banyak informasi tentang aliran maksimum. Pertimbangkan grafik dimana minimum -cut memiliki nilai . Jika saya memperpanjang dengan menambahkan simpul baru dan tepi dengan bobot , minimum potong dalam grafik baru hanya terdiri dari tepi $G=(V,E)$ $s,t$ $w$ $G$ $s'$ $(s',s)$ $w$ $s',t$ $(s', s)$ tapi itu tidak memberikan informasi apa pun tentang cara mendapatkan unit aliran dari ke $w$ $s$ $t$ .

Secara efektif, potongan minimum memberi tahu Anda nilai aliran, tetapi tidak bagaimana mencapai aliran itu. Ini berarti mengetahui pemotongan minimum dapat mempercepat menemukan aliran paling banyak oleh faktor logaritmik, karena kita bisa melakukan pencarian biner untuk menemukan nilai pemotongan.

Tom van der Zanden
sumber

Tetapi faktor logaritmik itu akan berada pada ukuran interval nilai aliran potensial, karenanya tidak dapat dibandingkan dengan batas atas yang ada pada penyelesaian max-flow yang hanya bergantung pada ukuran grafik. Yang mengatakan, bahkan percepatan logaritmik akan menarik. Saya tidak yakin bahwa mengetahui nilai aliran maksimum tidak membantu sama sekali.

Raphael

-2

Tentu saja ada algoritma yang memungkinkan Anda menghitung potongan min sebelum menghitung maxflow. Dua algoritma tersebut adalah push relabel dan algoritma pseudoflow yang terkait erat. Yang terakhir lebih efisien. Kedua algoritma ini menggunakan properti khusus dari grafik residual yang secara iteratif mereka tingkatkan untuk mendapatkan aliran maksimum dari potongan minimum. Untuk lebih jelasnya saya sangat merekomendasikan membaca kode dan makalah.

Untuk menguraikan kasus relabel push, ketika algoritma dapat mendorong tidak ada lagi aliran ke wastafel itu dijamin telah menghitung potongan min. Bagian dari algoritma ini disebut fase 1 karena kurangnya nama yang lebih baik. Fase 2 adalah tahap yang lebih efisien di mana ia mengubah potongan min menjadi maxflow dengan membatalkan siklus berulang dalam grafik residu menggunakan pencarian pertama kedalaman tunggal dan mendorong kelebihan kembali ke sumber. Saya percaya fase 2 dapat dibuktikan secara asimptomatik lebih efisien daripada fase 1.

ldog
sumber

Harap baca kembali pertanyaannya; itu bukan yang kamu jawab.

Raphael

Contoh PR yang saya berikan berasumsi Anda telah menghitung informasi lain selama Anda menghitung min-cut. Pertanyaan awal Anda tidak menentukan apakah Anda diizinkan untuk mempertahankan informasi lain bersama dengan min-cut untuk membuat perhitungan maxflow selanjutnya lebih mudah. Apakah adil untuk menyatakan pertanyaan awal Anda sebagai "Diberikan potongan minimum dan tidak ada informasi lain , bagaimana kami dapat menentukan aliran maksimum?".

ldog

Saya menyatakan, "diberikan A, hitung B". Satu-satunya asumsi yang masuk akal adalah bahwa Anda hanya diberi A, jika tidak berbicara tentang masalah komputasi akan menjadi urusan yang sangat kabur.

Raphael

Saya mohon untuk berbeda. Dari perspektif praktis, Anda tidak akan pernah menghitung min-cut tanpa menghitung informasi tambahan (seperti yang ada dalam algoritma PR). Dari perspektif teoretis mungkin lebih baik untuk mempertimbangkan hal-hal secara terpisah seperti yang Anda katakan. Konteks adalah kunci di sini.

ldog