22
$\begingroup$

In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls.

Image1

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")

Image2

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

Image3


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.

$\endgroup$
2
  • 3
    $\begingroup$ A clarification: you're not allowed to remove a set of nodes that would completely disconnect start from finish? $\endgroup$ May 7, 2012 at 18:43
  • $\begingroup$ @David: Yes edited, sorry for the confusion. There must still be a solution. $\endgroup$ May 7, 2012 at 18:45

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Nice reduction! $\endgroup$ May 8, 2012 at 12:17
  • $\begingroup$ Sure, that's what I figured given the references in the question; but I still need some solution, and I was hoping for something better than the simple "use annealing/genetic algorithms/similar." My question is, is there (like the bipartite permutation graph case above) any known pseudo-polynomial solution, or even a half-decent approximation that guarantees some bound? $\endgroup$ May 8, 2012 at 15:44
  • 3
    $\begingroup$ 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. $\endgroup$ May 8, 2012 at 17:09
  • $\begingroup$ I'm not able to follow that trail of logic, but I will take your word for it and give you a very sadface checkmark :( ✓. Thank you for taking the time to think about and answer this question, Professor Eppstein! $\endgroup$ May 8, 2012 at 21:50
  • $\begingroup$ One year and much learning (on my part) later, I now understand and agree with this proof. Thank you again :) $\endgroup$ Jan 11, 2013 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.