In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls.
Enemies take the shortest path from start to finish without passing through any walls (they aren't usually constrained to the grid, but for simplicity's sake let's say they are. In either case, they can't move through diagonal "holes")
The problem (for this question at least) is to place up to K additional walls to maximize the path the enemies have to take, without completely blocking start from the finish. For example, for K=14
I've determined that this is the same as the "k most vital nodes" problem:
Given an undirected graph G = (V,E) and two nodes s,t ∈ V, the k-most-vital-nodes are the k nodes whose removal maximizes the shortest path from s to t.
Khachiyan et al1 showed that, even if the graph is unweighted and bipartite, even approximating the length of the max-shortest-path within a factor of 2 is NP-Hard (given k,s,t).
All is not lost, however: later, L. Cai et al2 showed that, for "bipartite permutation graphs" this problem can be solved in pseudo-polynomial time using the "intersection model."
I haven't been able to find anything on unweighted grid-graphs specifically, and I can't figure how "bipartite permutation graphs" are related, if at all. Has there been any research published relating to my problem - maybe I am looking in the completely wrong place? Even a decent pseudo-polynomial approximation algorithm would work well. Thanks!
1 L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf and J. Zhao "On Short Path Interdiction Problems: Total and Node-Wise Limited Interdiction," Theory of Computer Systems 43 (2008), 2004-233. link.
2 L. Cai and J. Mark Keil, "Finding the k most vital nodes in an interval graph." link.
Note: this question is a follow-up to my stackoverflow question found here.