Menghasilkan labirin pertahanan menara, alias Menemukan K node paling vital ("nodewise interdiction") dalam grafik grid tanpa bobot

Dalam permainan menara pertahanan, Anda memiliki kisi NxM dengan awal, akhir, dan sejumlah dinding.

Musuh mengambil jalur terpendek dari awal hingga selesai tanpa melewati dinding apa pun (mereka biasanya tidak dibatasi ke grid, tetapi demi kesederhanaan katakanlah mereka. Dalam kedua kasus itu, mereka tidak dapat bergerak melalui "lubang" diagonal)

Masalahnya (untuk pertanyaan ini setidaknya) adalah untuk menempatkan ke dinding tambahan K untuk memaksimalkan jalur yang harus diambil musuh, tanpa benar-benar memblokir mulai dari selesai. Misalnya, untuk K = 14

Saya telah menentukan bahwa ini sama dengan masalah "k most vital nodes":

Diberikan grafik tidak terarah G = (V, E) dan dua node s, t ∈ V, k-most-vital-node adalah k node yang penghapusannya memaksimalkan jalur terpendek dari s ke t.

Khachiyan et al ¹ menunjukkan bahwa, bahkan jika grafik tidak berbobot dan bipartit, bahkan mendekati panjang jalur maksimum terpendek dalam faktor 2 adalah NP-Hard (diberikan k, s, t) .

Semua tidak hilang, namun: nanti, L. Cai et al ² menunjukkan bahwa, untuk "grafik permutasi bipartit" masalah ini dapat diselesaikan dalam waktu pseudo-polinomial menggunakan "model persimpangan."

Saya belum dapat menemukan apa pun pada grafik kotak tidak tertimbang secara khusus, dan saya tidak dapat membayangkan bagaimana "grafik permutasi bipartit" saling berhubungan, jika memang ada. Apakah ada penelitian yang dipublikasikan yang berkaitan dengan masalah saya - mungkin saya mencari di tempat yang sepenuhnya salah? Bahkan algoritma aproksimasi pseudo-polinomial yang layak akan bekerja dengan baik. Terima kasih!

¹ L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf dan J. Zhao "Pada Masalah Interdiksi Jalur Singkat: Total dan Node-Wise, Larangan Terbatas," Teori Sistem Komputer 43 ( 2008), 2004-233. tautan .
² L. Cai dan J. Mark Keil, "Menemukan k node paling vital dalam grafik interval." tautan .

Catatan: pertanyaan ini merupakan tindak lanjut dari pertanyaan stackoverflow saya yang ditemukan di sini .

$\ell$$s$$f$$s$$f$$n$$m$$m-(n-1)$$s$$f$$(n-1)l+(n-2)$$s$$f$$s$$f$