Создание защитного лабиринта башни, или Нахождение K наиболее важных узлов («узловой запрет») в невзвешенном сеточном графике

В игре Tower Defense у вас есть сетка NxM с началом, финишем и несколькими стенами.

Враги выбирают кратчайший путь от начала до конца, не проходя сквозь стены (обычно они не привязаны к сетке, но для простоты, скажем, так. В любом случае они не могут перемещаться через диагональные «дыры»)

Задача (по крайней мере, для этого вопроса) состоит в том, чтобы разместить до K дополнительных стен, чтобы максимизировать путь, по которому должны идти враги, без полного блокирования старта с конца. Например, для К = 14

Я определил, что это то же самое, что и проблема «k самых важных узлов»:

Для неориентированного графа G = (V, E) и двух узлов s, t ∈ V k-самыми важными узлами являются k узлов, удаление которых максимизирует кратчайший путь из s в t.

Хачиян и др. ¹ показали, что, даже если график невзвешенный и двудольный, аппроксимация длины максимального кратчайшего пути с коэффициентом 2 является NP-трудной (учитывая k, s, t) .

Однако еще не все потеряно: позднее Л. Кай и др. ² показали, что для «двудольных графов перестановок» эта проблема может быть решена за псевдополиномиальное время с помощью «модели пересечений».

Мне не удалось найти что-либо конкретно на невзвешенных графах сетки, и я не могу понять, как связаны «двудольные графы перестановок», если вообще связаны. Было ли опубликовано какое-либо исследование, касающееся моей проблемы - может быть, я смотрю в совершенно неправильном месте? Даже приличный алгоритм псевдополиномиальной аппроксимации будет работать хорошо. Благодарность!

¹ Л. Хачиян, Э. Борос, К. Борис, К. Эльбассиони, В. Гурвич, Г. Рудольф и Дж. Чжао. «О проблемах , препятствующих короткому пути: полный и узловатый ограниченный запрет», Теория компьютерных систем 43 ( 2008), 2004-233. ссылка .
² Л. Кай и Дж. Марк Кейл, «Нахождение k наиболее важных узлов в интервальном графе». ссылка .

Примечание: этот вопрос является продолжением моего вопроса о стековом потоке, найденного здесь .

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