Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
add comment

1 Answer 1

up vote 11 down vote accepted

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.

share|improve this answer
    
Nice reduction! –  Marzio De Biasi May 8 '12 at 12:17
    
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? –  BlueRaja - Danny Pflughoeft May 8 '12 at 15:44
3  
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
    
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! –  BlueRaja - Danny Pflughoeft May 8 '12 at 21:50
    
One year and much learning (on my part) later, I now understand and agree with this proof. Thank you again :) –  BlueRaja - Danny Pflughoeft Jan 11 '13 at 5:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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