Terkecil Kedua -

Apakah ada yang diketahui tentang - terkecil - terpotong dalam aliran jaringan? Atau, lebih umum, tentang masalah ini: $s$ $t$

Input: Jaringan dan angka , semuanya dalam biner. Output: Sebuah th terkecil - cut. $N$ $k$
$k$ $s$ $t$

Sebuah th terkecil - cut adalah setiap - dipotong, sehingga ada persis - luka yang kapasitas $k$ $s$ $t$ $(S,T)$ $s$ $t$ $k-1$ $s$ $t$

berbeda berpasangan dan
benar-benar lebih kecil dari kapasitas . $(S,T)$

Saya ingin tahu bagaimana hal itu dapat dihitung dan apakah ini dapat dilakukan secara efisien untuk kasus . $k=1$

cc.complexity-theory optimization max-flow-min-cut flow-problems Oliver Witt
sumber

Anda dapat menemukan potongan terkecil kedua dengan menambahkan

bobot ke semua tepi dalam potongan terkecil dan kemudian menghitung potongan terkecil yang baru. Ini mungkin bekerja selama

dikodekan dalam unary (dan tentunya untuk konstanta

ϵ

$\epsilon$

k

$k$

k

$k$

Yuval Filmus

Saya tidak melihat bagaimana itu membantu. Bayangkan sebuah jaringan jalur yang terdiri dari tiga node

hanya dengan dua sisi

dan

. Selanjutnya, biarkan kapasitas menjadi

dan

. Jelas, potongan min-cut

dan potongan terkecil terkecil

s

$s$

v

$v$

t

$t$

(s, v)

$(s,v)$

(v, t)

$(v,t)$

c (s, v) = 1

$c(s,v)=1$

c (v, t) = 2

$c(v,t)=2$

(s, v)

$(s,v)$

. Meningkatkan kapasitas seperti yang Anda gambarkan lagi akan menghasilkan

(v, t)

$(v,t)$

sebagai min-cut dengan kapasitas

. Bagaimana saya menyimpulkan potongan terkecil kedua dari itu?

(s, v)

$(s,v)$

1 + ϵ

$1+\epsilon$

Oliver Witt

Menambahkan batas bawah pada tutup potongan adalah ketidaksamaan linier, cukup tambahkan satu epsilon lebih besar dari tutup min dan jalankan LP. Anda dapat mengulanginya k kali untuk mendapatkan apa yang Anda inginkan. Ini mungkin dapat disusun kembali sebagai modifikasi pada jaringan tetapi saya belum berhasil.

Kaveh

Saya melihat cara kerjanya jika

dalam pengkodean unary. Apa, jika itu biner? Dalam hal ini, modifikasi jaringan tidak dapat dilakukan dalam

iterasi.

k

$k$

k

$k$

Oliver Witt

Saya ragu ada solusi mudah jika k adalah biner. Kita dapat memeriksa apakah ada potongan c seperti yang saya jelaskan. Tampaknya bagi saya bahwa pada dasarnya menghitung jumlah kemungkinan c, mungkin disediakan untuk berhubungan dengan menghitung jumlah kecocokan dan mungkin # P-lengkap. (Ini hanya intuisi saya, bukan argumen.)

Kaveh

Pemotongan terkecil kedua, dan lebih umum pemangkasan terkecil, dapat ditemukan dalam polinomial waktu dalam dan ukuran jaringan. Lihat: $k$ $k$

HW Hamacher. Sebuah algoritma untuk menemukan potongan terbaik dalam jaringan. Oper. Res. Lett. 1 (5): 186–189, 1982, doi: 10.1016 / 0167-6377 (82) 90037-2 . $(K\cdot n^4)$ $k$

HW Hamacher, J.-C. Picard, dan M. Queyranne. Pada menemukan pemotongan terbaik dalam jaringan. Oper. Res. Lett. 2 (6): 303–305, 1984, doi: 10.1016 / 0167-6377 (84) 90083-X . $K$

HW Hamacher dan M. Queyranne. $K$ solusi terbaik untuk masalah optimisasi kombinatorial. Ann. Oper. Res. 4 (1-4): 123–143, 1985, doi: 10.1007 / BF02022039 .

David Eppstein
sumber

Tidakkah ini memungkinkan bobot yang sama di antara top

? Pertanyaannya tampaknya bertanya tentang berat

th terkecil , yang seperti yang disarankan Kaveh berbau lebih seperti masalah # P-complete.

k

$k$

k

$k$

András Salamon

Saya mengerti seperti itu juga: bobot yang sama diizinkan. Ini sepertinya tidak menjawab pertanyaan. Namun demikian, saya tidak mengetahui makalah ini, terima kasih untuk itu.

Oliver Witt

Pertanyaannya adalah worded bad, karena ia meminta satu hal ( potongan terkecil

) dan kemudian menambahkan batasan yang mengubah pertanyaan menjadi sesuatu yang lain ( bobot terkecil

terkecil). Saya setuju bahwa versi bobot masalah yang berbeda cenderung $ P-complete.

k

$k$

k

$k$

David Eppstein

Terkecil Kedua -

Jawaban: