Meningkatkan kapasitas untuk memaksimalkan pemotongan minimum

Pertimbangkan grafik dengan semua sisi memiliki kapasitas unit. Satu dapat menemukan potongan min di waktu polinomial.

Misalkan saya diizinkan untuk meningkatkan kapasitas setiap tepi hingga tak terbatas (setara dengan menggabungkan node di kedua sisi tepi). Apa cara optimal untuk memilih set tepi k yang optimal (yang kapasitasnya akan ditingkatkan hingga tak terbatas) untuk memaksimalkan potongan minimum?$k$$k$

Dalil. Masalah dalam posting adalah NP-hard.

Dengan "masalah dalam posting", maksud saya, diberi grafik dan integer k , untuk memilih k edge untuk meningkatkan kapasitas sehingga dapat memaksimalkan potongan minimum pada grafik yang dimodifikasi.$G=(V,E)$$k$$k$

Idenya adalah mengurangi dari Max Cut. Secara kasar, grafik yang diberikan memiliki ukuran potong maksimum s jika dan hanya jika Anda dapat meningkatkan kapasitas tepi n - 2 sehingga grafik yang dihasilkan memiliki ukuran potongan minimum s . Idenya adalah bahwa n - 2 edge hanya cukup untuk memaksa grafik yang dihasilkan hanya memiliki satu pemotongan kapasitas hingga, dan itu dapat berupa potongan apa pun yang Anda pilih.$G=(V,E)$$s$$n-2$$s$$n-2$

Gagasan ini tidak cukup berhasil karena untuk mendapatkan potongan yang diberikan , Anda memerlukan subgraf yang diinduksi oleh C dan V ∖ C masing-masing untuk dihubungkan. Tapi Anda bisa mengatasinya dengan gadget yang sesuai.$(C, V\setminus C)$$C$$V\setminus C$

Bukti. Diberikan grafik terhubung , tentukan potongan yang terhubung menjadi potongan ( C , V ∖ C ) sedemikian rupa sehingga subgraf yang diinduksi oleh C dan oleh V ∖ C masing-masing terhubung. Definisikan Max Connected Cut menjadi masalah menemukan potongan yang terhubung (dalam grafik terhubung yang diberikan) memaksimalkan jumlah tepi yang melintasi potongan.$G=(V,E)$$(C,V\setminus C)$$C$$V\setminus C$

Kami menunjukkan bahwa Max Connected Cut mengurangi masalah di pos. Lalu kami menunjukkan bahwa Max Cut tanpa bobot mengurangi ke Max Connected Cut.

Lemma 1. Max Connected Cut mengurangi waktu poli untuk masalah yang ditentukan dalam posting.

Bukti. Diberikan instance Max-Connected-Cut , misalkan k = | V | - 2 . Untuk membuktikan lemma, kami membuktikan hal berikut:$G=(V,E)$$k=|V|-2$

Klaim 1: Untuk setiap , ada pemotongan terhubung ( C , V ∖ C ) dalam kapasitas G setidaknya s , IFF dimungkinkan untuk meningkatkan kapasitas tepi k dalam G hingga tak terbatas sehingga grafik yang dihasilkan memiliki potongan minimum kapasitas setidaknya s .$s>0$$(C,V\setminus C)$$G$$s$$k$$G$$s$

HANYA JIKA: Misalkan ada pemotongan terhubung kapasitas setidaknya s . Biarkan T 1 dan T 2 be subpohon mencakup, masing-masing, C dan V ∖ C , kemudian menaikkan kapasitas tepi di T 1 dan T 2 . (Perhatikan bahwa | T 1 | + | T 2 | = | C | - 1 + | V ∖ $(C,V\setminus C)$$s$$T_1$$T_2$$C$$V\setminus C$$T_1$$T_2$ .) Satu-satunya pemotongan kapasitas terbatas yang tersisa dalam grafik adalah ( C , V ∖ C ) , dengan kapasitas setidaknya s , sehingga grafik yang dihasilkan memiliki kapasitas pemotongan minimum setidaknya s .$|T_1|+|T_2|=|C|-1 + |V\setminus C|-1 = |V|-2 = k$$(C, V\setminus C)$$s$$s$

JIKA: Misalkan dimungkinkan untuk meningkatkan kapasitas edge dalam G sehingga grafik yang dihasilkan memiliki kapasitas minimum pemotongan paling tidak s . Pertimbangkan subgraf yang dibentuk oleh k yang terangkat. Tanpa kehilangan sifat umum, anggaplah subgraf ini asiklik. (Kalau tidak, "unraise" satu sisi dari siklus tepi yang ditinggikan dan alih-alih menaikkan beberapa tepi yang tidak terangkat yang menggabungkan dua komponen yang terhubung dari subgraf. Ini hanya meningkatkan potongan minimum pada grafik yang dihasilkan.) Dengan pilihan k = n - 2 , subgraf dari tepi yang ditinggikan memiliki dua komponen yang terhubung, katakanlah C dan V ∖ $k$$G$$s$$k$$k=n-2$$C$$V\setminus C$, jadi satu-satunya pemotongan kapasitas terbatas dalam grafik yang dihasilkan adalah . Dan potongan ini memiliki kapasitas setidaknya s , seperti yang terjadi pada grafik aslinya.$(C,V\setminus C)$$s$

Ini membuktikan klaim (dan lemma). (QED)

Untuk kelengkapan, kami menunjukkan bahwa Max Connected Cut adalah NP-complete, dengan reduksi dari Max Cut yang tidak tertimbang.

Lemma 2. Max Cut yang tidak tertimbang mengurangi waktu poli menjadi Max Connected Cut .

Bukti. Untuk setiap bilangan bulat , mendefinisikan grafik P ( N ) terdiri dari dua jalur A dan B , masing-masing panjang N , dengan tepi dari setiap titik dalam A ke setiap sudut di B . Kami membiarkannya sebagai latihan bagi pembaca untuk memverifikasi bahwa potongan maksimum dalam P ( N ) ( A di satu sisi, B di sisi lain) memiliki ukuran N 2 , dan tidak ada potongan lain yang memiliki ukuran lebih besar dari, katakanlah, N 2 - N / 100 .$N\ge 1$$P(N)$$A$$B$$N$$A$$B$$P(N)$$A$$B$$N^2$$N^2-N/100$

$G=(V,E)$$G'=(V',E')$$n=|V|$$N = 100(n^2 + 2n)$$G$$P(N)$$A$$B$$v\in V$$A$$B$

$s\ge 0$$(C,V\setminus C)$$G$$s$$G'$$s+N^2+n$

$(C,V\setminus C)$$G$$s$$(A\cup C, B\cup V\setminus C)$$G'$$G'$$s$$C$$V\setminus C$$N^2$$A$$B$$n$$2n$$V$$A\cup B$

$G'$$s+N^2+n$$A$$B$$P(N)$$N^2-N/100$$P(N)$$N^2-N/100 + |E| + 2|V| \le N^2 - N/100 + n^2 + 2n = N^2$$C$$V$$A$$N^2$$A$$B$$n$$V$$A\cup B$$s$$C$$V\setminus C$

Ini membuktikan klaim dan Lemma 2. (QED)

Oleh Lemmas 1 dan 2, karena Max Cut yang tidak tertimbang adalah NP-hard, masalah dalam postingan juga NP-hard.