Générer un labyrinthe de tower defense, alias Trouver les K nœuds les plus vitaux («interdiction par nœud») dans un quadrillage non pondéré

Dans un jeu de tower defense, vous avez une grille NxM avec un départ, une arrivée et un certain nombre de murs.

Les ennemis empruntent le chemin le plus court du début à la fin sans passer par aucun mur (ils ne sont généralement pas contraints à la grille, mais pour simplifier, disons qu'ils le sont. Dans les deux cas, ils ne peuvent pas se déplacer à travers des "trous" diagonaux)

Le problème (pour cette question au moins) est de placer jusqu'à K murs supplémentaires pour maximiser le chemin que les ennemis doivent emprunter, sans bloquer complètement le départ depuis l'arrivée. Par exemple, pour K = 14

J'ai déterminé que c'est la même chose que le problème des "k nœuds les plus vitaux":

Étant donné un graphe non orienté G = (V, E) et deux nœuds s, t ∈ V, les k nœuds les plus vitaux sont les k nœuds dont la suppression maximise le chemin le plus court de s à t.

Khachiyan et al ¹ ont montré que, même si le graphique n'est pas pondéré et bipartite, même approximant la longueur du chemin le plus court max dans un facteur 2 est NP-difficile (étant donné k, s, t) .

Tout n'est cependant pas perdu: plus tard, L. Cai et al ² ont montré que, pour les "graphes de permutation bipartite", ce problème peut être résolu en temps pseudo-polynomial en utilisant le "modèle d'intersection".

Je n'ai pas pu trouver quoi que ce soit sur des graphiques en grille non pondérés en particulier, et je ne peux pas comprendre comment les "graphiques de permutation bipartite" sont liés, le cas échéant. Y a-t-il eu des recherches publiées concernant mon problème - peut-être que je regarde au mauvais endroit? Même un algorithme d'approximation pseudo-polynomiale décent fonctionnerait bien. Merci!

¹ L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf et J. Zhao "On Short Path Interdiction Problems: Total and Node-Wise Limited Interdiction", Theory of Computer Systems 43 ( 2008), 2004-233. lien .
² L. Cai et J. Mark Keil, "Trouver les k nœuds les plus vitaux dans un graphe d'intervalle." lien .

Remarque: cette question fait suite à ma question de stackoverflow trouvée ici .

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