# Generating a tower defense maze, aka Finding the K most vital nodes (“nodewise interdiction”) in an unweighted grid-graph

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.

• A clarification: you're not allowed to remove a set of nodes that would completely disconnect start from finish? – David Eppstein May 7 '12 at 18:43
• @David: Yes edited, sorry for the confusion. There must still be a solution. – BlueRaja - Danny Pflughoeft May 7 '12 at 18:45

This appears to be NP-complete by a reduction from Hamiltonian cycle in planar graphs of degree at most three. Hamiltonian cycle should still be hard in planar graphs of degree at most three that contain two adjacent degree-two nodes (this is the part I haven't checked very carefully). Embed the given planar graph into the grid in such a way that each vertex becomes a grid point, each edge becomes a grid path, and all edges have the same length $\ell$ (pad the shorter ones by zigzagging if necessary to achieve this). Let $s$ and $f$ be two adjacent degree-two nodes. Include walls in the initial placement of walls so that only the vertices and edges of the embedding remain available to connect $s$ to $f$. Let $n$ and $m$ be the numbers of vertices and edges in the original graph. Then, the original graph has a Hamiltonian cycle if and only if it is possible to place $m-(n-1)$ more walls in such a way that the new shortest path from $s$ to $f$ has length $(n-1)l+(n-2)$. A path of that length must be a Hamiltonian path in the original graph which together with the edge from $s$ to $f$ forms a Hamiltonian cycle, and conversely if the graph contains a Hamiltonian cycle then you can force the path from $s$ to $f$ to be that long by placing a wall in each other edge.
• Strong NP-completeness makes a pseudopolynomial solution unlikely. And the reduction above, together with the fact that there's no good approximation known for longest path (best known approx is $O(n/polylog)$ and there's an $\Omega(n^{1-\epsilon})$ inapproximability result for the directed case) together imply that a good provably approximation for this problem is also likely to be difficult to find. – David Eppstein May 8 '12 at 17:09