Apakah Logical Min-Cut NP-Complete?

Definisi masalah Logical Min Cut (LMC)

Misalkan $G = (V, E)$ adalah digraf tanpa bobot, $s$ dan $t$ adalah dua simpul dari $V$ , dan $t$ dapat dijangkau dari $s$ . Masalah LMC mempelajari bagaimana kita dapat membuat $t$ tidak dapat dijangkau dari $s$ dengan menghilangkan beberapa tepi $G$ mengikuti batasan berikut:

1. Jumlah tepi yang dilepas harus minimal.
2. Kami tidak dapat menghapus setiap tepi keluar dari setiap simpul $G$ (yaitu, tidak ada simpul dengan tepi keluar dapat menghapus semua tepi keluarnya ).

Batasan kedua ini disebut penghapusan logis. Jadi kami mencari penghapusan minimal yang logis dari beberapa tepi sehingga t tidak dapat dijangkau dari s .$G$$t$$s$

Upaya solusi

Jika kita mengabaikan kendala penghapusan logis masalah LMC, itu akan menjadi masalah min-cut dalam digraf tidak tertimbang , sehingga akan dipecahkan secara polinomial (teorema min-cut max-flow).$G$

Jika kita mengabaikan batasan penghapusan minimal dari masalah LMC, itu akan dipecahkan lagi secara polinomi dalam DAG: temukan simpul sedemikian sehingga k dapat dijangkau dari s dan t tidak dapat dijangkau dari k . Kemudian pertimbangkan jalur p yang merupakan jalur arbitrer dari s ke k . Sekarang perhatikan path p sebagai subgraph dari G : jawabannya adalah setiap tepi keluar dari subgraph p . Jelas bahwa titik k dapat ditemukan oleh DFS dalam G dalam waktu polinomial. Sayangnya algoritma ini tidak berfungsi secara umum$k$$k$$s$$t$$k$$p$$s$$k$$p$$G$$p$$k$$G$ untuk grafik yang diarahkan sewenang-wenang.

Saya mencoba untuk memecahkan masalah LMC dengan teknik pemrograman dinamis tetapi jumlah negara yang diperlukan untuk memecahkan masalah menjadi eksponensial. Selain itu, saya mencoba mengurangi beberapa masalah NP-Lengkap seperti 3-SAT, max2Sat, max-cut, dan klik untuk masalah LMC yang saya tidak berhasil menemukan pengurangan.

Saya pribadi berpikir bahwa masalah LMC adalah NP-Lengkap bahkan jika adalah DAG biner (yaitu, DAG di mana tidak ada node memiliki derajat lebih besar dari 2).$G$

Pertanyaan

1. Apakah masalah LMC NP-Complete dalam digraph sembarang ? (pertanyaan utama)$G$
2. Apakah masalah LMC NP-Complete dalam DAG sewenang-wenang ?$G$
3. Apakah masalah LMC NP-Complete dalam biner DAG sembarang ?$G$

Misalkan G = (V, E) menjadi DAG tertimbang, s dan t menjadi dua simpul G, dan LSTMC = (G, s, t) menjadi contoh masalah logis min-cut. Jelas bahwa masalah LSTMC adalah NP. Sekarang, kita harus menunjukkan bahwa LSTMC adalah NP-Hard. Kami mengurangi masalah hitting-set ke masalah LSTMC. Biarkan S = {s1, s2, ..., sn} menjadi himpunan yang diberikan dan {a1, a2, ..., am} menjadi gabungan dari semua himpunan. Dengan nomor k1, masalah keputusan hitting set problem menyatakan apakah ada himpunan A dengan elemen k1 sedemikian sehingga setiap elemen S (setiap himpunan angka i = 1..n) berisi setidaknya satu elemen A. Kita menunjukkan masalah hitting set sebagai HS (S). Kami membangun DAG G weight tertimbang dari himpunan S oleh Algoritma HS2LSTMC. Algoritma ini menganggap s sebagai sumber simpul DAG G ′. Untuk setiap himpunan HS st i = 1..n, algoritma mempertimbangkan vertex yang sesuai, si, dan menambahkan tepi dengan bobot tak terbatas dari s ke setiap si. Kemudian, untuk setiap elemen aj dari penyatuan set input st j = 1..m, algoritma mempertimbangkan vertex yang sesuai, aj, dan menambahkan tepi dengan bobot nol dari setiap si ke setiap aj aj ∈si di HS. Akhirnya, algoritma mempertimbangkan dua simpul terakhir yang disebut t dan k, dan menambahkan dua sisi dari setiap ajj = 1..m ke kedua simpul akhir. Jelas bahwa G ′ dapat dibuat dalam waktu polinomial.

Sekarang, kita harus menunjukkan bahwa HS (S) memiliki jawaban dengan elemen k1 jika dan hanya jika LSTMC = (G ′, s, t) memiliki jawaban dengan beberapa tepi yang dilepas secara logis sehingga jumlah bobot dari tepi yang dihilangkan adalah k1.

Untuk mempermudah, kami melakukan bagian pembuktian ini, dengan memberikan contoh:

Pada gambar berikut, anggap bahwa S = {s1, s2, s3} sedemikian rupa sehingga s1 = {1, 2, 3}, s2 = {1, 4}, dan s3 = {2, 5}. Gambar 2 menunjukkan DAG G G tertimbang dari masalah LSTMC yang sesuai dengan masalah hitting set HS (S). Dalam contoh ini, himpunan A, yaitu penyatuan semua elemen S, adalah A = {1, 2, 3, 4, 5}. Kami punya | S | = 3 dan | A | = 5. Contoh ini menunjukkan bagaimana sebuah instance arbitrer dari hitting set problem dapat diselesaikan dengan bantuan instance spesifik dari masalah min-cut logis st dalam DAG tertimbang. Jika kita menghitung jawaban untuk LSTMC = (G ′, s, t) dan mempertimbangkan ujung-ujung yang dihapus dari jawaban yang dalam bentuk (aj, t) disebut E1 (1 ≤ j ≤ m), maka set ekor dari E1 adalah jawaban untuk HS (S). Jawaban untuk masalah LSTMC adalah set tepi E1 = {(s1, 2), (s1, 3), (s2, 4), (s3, 5), (1, t), (2, t)}. Jadi, set ekor subset E2 = {(1, t), (2,

Berikut ini (upaya at) algoritma polinomial-waktu untuk LMC pada sewenang-wenang biner DAGs .$G$

Ini menjawab Pertanyaan # 3. (Maaf atas penulisan yang berantakan sebelumnya. :))

Untuk memulai, buang "selamanya" titik mana pun yang tidak dapat dijangkau dari . Kami tidak peduli tentang ini, karena mereka bukan bagian dari jalur s - t .$s$$s$$t$

Selanjutnya, tentukan sub-DAG dan B , yang awalnya kosong. Kemudian, untuk semua simpul v ∈ G - { s , t } ,$A$$B$$v \in G-\{s, t\}$

Uji apakah ada jalur dari ke t . Jika demikian, menambahkan v ke A . Jika tidak, tambahkan v ke B .$v$$t$$v$$A$$v$$B$

Biarkan tepi dan B adalah yang diinduksi oleh simpul dalam setiap set (untuk saat ini, abaikan setiap tepi dari s ke A , dari A ke t , dan dari A ke B ; juga perhatikan tidak ada tepi dari B ke t oleh konstruksi).$A$$B$$s$$A$$A$$t$$A$$B$$B$$t$

Kemudian, menghitung penutupan transitif . Yaitu, kita tertarik dalam menemukan beberapa set simpul { a * } yang merupakan "daun" dari sub-DAG A .$A$$\{a^*\}$$A$

Memperbaiki seperti . Amati bahwa harus ada tepi diarahkan dari sebuah * ke t . Hal ini karena, dengan konstruksi, (i) ada s - t jalan melalui sebuah * , (ii) tidak ada jalur dari sebuah * melalui B , dan (iii) karena A itu sendiri merupakan DAG dan sebuah * adalah daun dari A , tidak ada jalan dari sebuah * melalui titik lain A ke t .$a^*$$a^*$$t$$s$$t$$a^*$$a^*$$B$$A$$a^*$$A$$a^*$$A$$t$

Sekarang, harus juga ada tepi terarah dari setiap simpul di ke beberapa simpul di B , atau beberapa { a ∗ } memiliki tepi tunggal ke t . Dalam kedua kasus, kami diijinkan untuk menghapus sebuah * → t tepi.$\{a^*\}$$B$$\{a^*\}$$t$$a^*\rightarrow t$

Jika = 1, maka baik kita harus menghapus tepi dari yang unik sebuah * → t , atau ada titik awal dalam s - t path yang berisi sebuah * yang memiliki dua jalur untuk t - satu melalui sebuah * dan satu langsung. Dalam hal bahwa kekuatan terus terakhir, kami merekam sebuah * → t dan lanjutkan "mundur rakus" (rincian di bawah ini).$|\{a^*\}|$$a^*\rightarrow t$$s$$t$$a^*$$t$$a^*$$a^*\rightarrow t$

Jika > 1, maka kita harus menghapus semua tepi dari { a ∗ } → t , atau ada beberapa tepi yang k < | { a ∗ } | sebelumnya dalam penutupan transitif dari A yang memutuskan semua jalur dari s melalui { a ∗ } ke t .$|\{a^*\}|$$\{a^*\}\rightarrow t$$k < |\{a^*\}|$$A$$s$$\{a^*\}$$t$

Di sinilah kami menggunakan fakta bahwa grafik adalah DAG biner.$G$

Pertimbangkan sekumpulan pendahulu . Karena masing-masing dari simpul-simpul ini memiliki derajat paling banyak dua, tepat ada tiga kasus:$\{a^*\}$

Kasus 1. Seorang pendahulunya memiliki out-tepi ke beberapa titik di dan out-tepi ke beberapa titik di B .$\{a^*\}$$B$

Dalam hal ini, tidak masalah apakah kita menghapus tepi dari pendahulunya ke titik di atau tepi dari titik di { a ∗ } ke t . Oleh karena itu, kita dapat "melewati" titik ini (dan memeriksa apakah jalur mundur bergabung dengan jalur titik lain di { a ∗ } ).$\{a^*\}$$\{a^*\}$$t$$\{a^*\}$

Kasus 2. Seorang pendahulu memiliki tepi ke sudut dalam dan pendahulu lain dari { a ∗ } .$\{a^*\}$$\{a^*\}$

Dalam hal ini, kita harus menghapus kedua tepi dari ke t , atau kita dapat menghapus satu tepi sebelumnya di jalur dari s ke pendahulunya yang memutus kedua jalur.$\{a^*\}$$t$$s$

Kasus 3. Seorang pendahulu memiliki tepi dua sudut di .$\{a^*\}$

Ini identik dengan kasus 2. Tidak masalah apakah kami menghapus salah satu dari tepi pendahulu ini dan tepi lainnya yang sesuai dari ke t , atau kedua tepi dari { a ∗ } ke t . Kami hanya ingin tahu apakah kami dapat memutuskan jalur dari s melalui pendahulu ini ke t dengan satu tepi sebelumnya di jalur dari s ke pendahulunya.$\{a^*\}$$t$$\{a^*\}$$t$$s$$t$$s$

Secara keseluruhan, ketika kita memindai mundur melalui pendahulunya dalam penutupan transitif dari , kita dengan rakus dapat melacak pilihan "terbaik sejauh ini". Yaitu, pada setiap langkah, kami memiliki pilihan yang jelas yang melibatkan penghapusan sejumlah tepi, tetapi kami ingin menunggu untuk melihat apakah opsi yang lebih baik tersedia. Setelah opsi yang lebih baik ditemukan, kita bisa "lupa" tentang opsi sebelumnya. Oleh karena itu, pilihan serakah di setiap lapisan pendahulu sudah cukup (selama kita menunggu sampai akhir berkomitmen untuk pilihan apa pun).$A$

Therefore, with some basic memoization, the time and space complexities of this process appear to be at most $O(|E|)$. This leaves out the fact that, while we can locally/greedily identify when we have found a "cheaper choice," it's a priori unclear which previously-recorded edges to remove. Therefore, we record the order in which we check edges as we go. Upon finding a better option, we repeat the search up to this point in order to find which previously-recorded edges to remove. The total time complexity of this step is $O(|E|^2)$ and space complexity $O(|E|)$.

$O(|V|\cdot(|V|+|E|))$$O(|V|^3)$$O(|E|^2)$ for the search. The total time is $O(|V|^2+|E||V|+|V|^3+|E|^2) = {\bf O(|V|^3+|E|^2)}$.

Upon completing the process, we obtain the minimum set of edges required to disconnect $s$ from $t$ while preserving at least one out-edge of every vertex in the graph (or we discover that a solution is impossible along the way, and abort).