Gerando um labirinto de defesa de torre, também conhecido como Encontrando os K nós mais vitais (“interdição de sentido idêntico”) em um gráfico não ponderado

Em um jogo de defesa de torre, você tem uma grade NxM com um início, um acabamento e várias paredes.

Os inimigos seguem o caminho mais curto do início ao fim sem passar por nenhuma parede (eles geralmente não são restritos à grade, mas por uma questão de simplicidade, digamos que sim. Em ambos os casos, eles não podem se mover através de "orifícios" na diagonal)

O problema (pelo menos para esta pergunta) é colocar até K paredes adicionais para maximizar o caminho que os inimigos devem seguir, sem bloquear completamente o início do final. Por exemplo, para K = 14

Eu determinei que isso é o mesmo que o problema "k nós mais vitais":

Dado um gráfico não direcionado G = (V, E) e dois nós s, t ∈ V, os nós mais vitais são os nós cuja remoção maximiza o caminho mais curto de s a t.

Khachiyan e cols. ¹ mostraram que, mesmo que o gráfico não seja ponderado e bipartido, até o comprimento do caminho máximo mais curto dentro de um fator de 2 é NP-Hard (dados k, s, t) .

Porém, nem tudo está perdido: mais tarde, L. Cai e cols. ² mostraram que, para "gráficos de permutação bipartidos", esse problema pode ser resolvido em tempo pseudo-polinomial usando o "modelo de interseção".

Não consegui encontrar nada especificamente em gráficos de grade não ponderados e não consigo imaginar como os "gráficos de permutação bipartidos" estão relacionados, se é que existem. Houve alguma pesquisa publicada relacionada ao meu problema - talvez eu esteja procurando um lugar completamente errado? Mesmo um algoritmo de aproximação pseudo-polinomial decente funcionaria bem. Obrigado!

¹ L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf e J. Zhao "Sobre problemas de interdição de caminho curto: interdição limitada total e limitada por nós", Teoria de sistemas de computador 43 ( 2008), 2004-233. link .
² L. Cai e J. Mark Keil, "Encontrando os k nós mais vitais em um gráfico de intervalo". link .

Nota: esta pergunta é um acompanhamento da minha pergunta sobre stackoverflow encontrada aqui .

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