Pemotongan minimum dalam grafik asiklik langsung tertimbang dengan kemungkinan bobot negatif

Saya mengalami masalah berikut:

Diberikan grafik asiklik terarah dengan bobot tepi bernilai nyata, dan dua simpul s dan t, menghitung potongan minimum.

Untuk grafik umum ini adalah NP-hard, karena orang dapat dengan mudah mengurangi max-cut untuk itu hanya dengan membalik bobot edge (koreksi saya jika saya salah).

Bagaimana situasinya dengan DAG? Dapatkah min-cut (atau max-cut) diselesaikan dalam waktu polinomial? Apakah NP-keras dan, jika demikian, apakah ada algoritma perkiraan yang dikenal?

Saya mencoba mencari pekerjaan pada ini tetapi tidak dapat (mungkin saya hanya menggunakan kata kunci yang salah dalam pencarian saya), jadi saya berharap seseorang dapat mengetahui (atau menemukan) sesuatu tentang ini.

algorithms complexity-theory graph-theory weighted-graphs George
sumber

Di mana formulasi pemrograman linier dari min-cut gagal di sini?

Peter Shor

(menggunakan notasi dari en.wikipedia.org/wiki/… ): Untuk tepi dengan bobot negatif d_ {ij} dapat menjadi besar secara sewenang-wenang. Bahkan jika satu batas d_ {ij} dari atas, ia akan selalu mengambil nilai maksimum yang mungkin untuk tepi dengan bobot negatif. Jadi solusi untuk program semacam itu tidak akan selalu menghasilkan potongan yang valid. Saya mungkin salah karena saya tidak terlalu berpengalaman dengan masalah seperti itu, jika demikian tolong perbaiki saya. Pada dasarnya saya ingin tahu apakah max-cut (dengan bobot sewenang-wenang) dapat diselesaikan secara efisien untuk DAG atau tidak.

George

Untuk membuat ini berhasil, Anda harus mengubah ketidaksetaraan pertama menjadi kesetaraan:

. Saya masih tidak melihat mengapa itu gagal saat itu, tapi mungkin saya kehilangan sesuatu. Saya belum terlalu memikirkannya.

d_{i j} = p_{j} - p_{i}

$d_{ij} = p_j - p_i$

Peter Shor

Mungkin saya yang kehilangan sesuatu di sini. Apakah ini menjamin bahwa semua

mengambil nilai integral? Seseorang dapat mengikat

dari atas dengan 1, tetapi saya tidak yakin apakah ini berfungsi atau tidak. Masalahnya tampaknya bahwa jika ini dapat diselesaikan, seseorang dapat mengurangi max-cut untuk itu dengan membalikkan bobot tepi, yang seharusnya tidak mungkin karena max-cut NP-hard. Namun saya mungkin salah di sini.

p_{i}

$p_i$

p_{i}

$p_i$

George

Apakah st max-cut NP-hard untuk DAG? Jika grafiknya bukan DAG, Anda tidak bisa mengubah ketidaksetaraan itu menjadi kesetaraan, karena Anda membutuhkan ketidaksetaraan jika ada siklus. Jadi dalam kasus umum LP tidak bekerja dengan bobot negatif.

Peter Shor

Jawaban:

Anda telah memperbaiki masalah Anda lagi di komentar. Untuk lebih spesifik, Anda memiliki DAG dengan semua tepi mengalir jauh dari sumber dan menuju wastafel (yaitu, semua tepi berada di jalur dari ke ). Anda ingin menemukan potongan minimum antara dua potong DAG, di mana potongan pertama terhubung ke , dan potongan kedua terhubung ke . Untuk masalah ini, variasi dari algoritma pemrograman linier standar untuk MIN-CUT bekerja, bahkan dengan bobot tepi negatif. $s$ $t$ $s$ $t$ $s$ $t$

Kami menggunakan notasi yang sama seperti di Wikipedia . Biaya edge adalah . Kami menempatkan fungsi potensial pada setiap node, dan biarkan . LP adalah $(i,j)$ $c_{ij}$ $p_i$ $d_{ij} = p_i - p_j$

\begin{aligned} m saya n saya m saya z e & \sum_{(saya, j) \in E} c_{saya j} d_{saya j} \\ s kamu b j e c t t Hai & d_{saya j} = {hal}_{saya} - {hal}_{j} \forall (saya, j) \in E \\ d_{saya j} \geq 0 \forall (saya, j) \in E \\ {hal}_{s} = 1 \\ {hal}_{t} = 0 \end{aligned}

$\begin{align*} \mathrm{minimize\ } & \sum_{(i,j) \in E} c_{ij} d_{ij} \\ \mathrm{subject\ to\ } & \ \ \ d_{ij} = p_i - p_j \ \ \forall (i,j) \in E \\ &\ \ \ d_{ij} \geq 0 \ \ \ \ \ \ \ \ \ \ \ \, \forall (i,j) \in E \\ & \ \ \ p_s\, = 1 \\ & \ \ \ p_t \, = 0 \end{align*}$

Persamaan ini menjamin bahwa , karena setiap titik berada pada beberapa jalur - . Demikian pula, karena adalah non-negatif, potensi pada setiap jalur dari ke menurun. Kami masih perlu menunjukkan bahwa ada solusi optimal untuk LP dengan semua baik atau . Ini mengikuti dari fakta bahwa nilai untuk solusi dari LP di atas adalah nilai yang diharapkan dari pemotongan , di mana $0 \leq p_i \leq 1$ $s$ $t$ $d_{ij} = p_i - p_j$ $s$ $t$ $p_i$ $0$ $1$ $C_w$ dipilih secara acak di , dan di mana potongan diperoleh dengan menempatkan semua simpul dengan di set simpul pertama, dan semua simpul dengan di set kedua. $w$ $[0,1]$ $C_w$ $i$ $p_i\geq w$ $p_i < w$

Peter Shor
sumber

Terima kasih atas jawaban luar biasa Anda, Peter. Tidak jelas pada pandangan pertama bahwa

, tapi saya rasa saya mengerti. Namun, saya mengalami kesulitan memahami argumen tentang solusi integral.

0 \leq p_{i} l e q 1

$0 \leq p_i leq 1$

George

@ George: argumen yang sama yang menunjukkan Min-Cut LP reguler memiliki solusi integral. Seharusnya ada penjelasan yang lebih panjang (dan lebih dapat dipahami) di suatu tempat online.

Peter Shor

Ok saya akan mencarinya. Sekali lagi terima kasih banyak atas bantuan Anda!

George