<p>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.</p>

CC BY-SA 3.0
2012-05-08T12:17:12.710Z
Nice reduction!
Marzio De Biasi
CC BY-SA 3.0
2012-05-08T15:44:50.667Z
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
CC BY-SA 3.0
2012-05-08T17:09:08.017Z
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
CC BY-SA 3.0
2012-05-08T21:50:12.597Z
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
CC BY-SA 3.0
2013-01-11T05:20:03.537Z
One year and much learning (on my part) later, I now understand and agree with this proof.  Thank you again :)
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2012-05-08T01:05:06.007Z
2012-05-08T01:05:06.007Z
David Eppstein
<p>In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls.</p>

<p><img src="https://i.sstatic.net/k0wUG.png" alt="Image1"></p>

<p>Enemies take the shortest path from start to finish without passing through any walls <em>(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")</em></p>

<p><img src="https://i.sstatic.net/fbO4P.png" alt="Image2"></p>

<p>The problem <em>(for this question at least)</em> is to place <strong>up to</strong> K additional walls to maximize the path the enemies have to take, without completely blocking start from the finish.  For example, for K=14</p>

<p><img src="https://i.sstatic.net/5fdlJ.png" alt="Image3"></p>

<hr>

<p>I've determined that this is the same as the "k most vital nodes" problem:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>Khachiyan et al<sup>1</sup> showed that, even if the graph is unweighted and bipartite, <strong>even approximating the length of the max-shortest-path within a factor of 2 is NP-Hard</strong> <em>(given k,s,t)</em>.</p>

<p>All is not lost, however:  later, L. Cai et al<sup>2</sup> showed that, for "bipartite permutation graphs" this problem can be solved in pseudo-polynomial time using the "intersection model."</p>

<p>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.  <strong>Has there been any research published relating to my problem</strong> - maybe I am looking in the completely wrong place?  Even a decent pseudo-polynomial approximation algorithm would work well.  Thanks!</p>

<hr>

<p><sup>1</sup> L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf and J. Zhao <em>"On Short Path Interdiction Problems: Total and Node-Wise Limited Interdiction,"</em> Theory of Computer Systems 43 (2008), 2004-233.  <a href="http://www.mpi-inf.mpg.de/~elbassio/pub/Inappro+Dijkstra.pdf" rel="nofollow noreferrer">link</a>.<br>
<sup>2</sup> L. Cai and J. Mark Keil, <em>"Finding the k most vital nodes in an interval graph."</em>  <a href="http://homepage.usask.ca/~tsv552/WAGT2011/talk%20MK.pdf" rel="nofollow noreferrer">link</a>.</p>

<p><em>Note: this question is a follow-up to my stackoverflow question found <a href="https://stackoverflow.com/questions/10338049/generating-a-tower-defense-maze-longest-maze-with-limited-walls-near-optimal">here</a>.</em></p>

CC BY-SA 3.0
2012-05-07T18:43:35.373Z
A clarification: you're not allowed to remove a set of nodes that would completely disconnect start from finish?
David Eppstein
CC BY-SA 3.0
2012-05-07T18:45:43.373Z
@David: Yes edited, sorry for the confusion.  There must still be a solution.
BlueRaja - Danny Pflughoeft
<cc.complexity-theory><ds.algorithms><graph-theory><graph-algorithms>
Generating a tower defense maze, aka Finding the K most vital nodes ("nodewise interdiction") in an unweighted grid-graph
BlueRaja - Danny Pflughoeft
# Generating a tower defense maze, aka Finding the K most vital nodes ("nodewise interdiction") in an unweighted grid-graph

(Asked by: username_0 on 2012-05-07)

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

![Image1](https://i.sstatic.net/k0wUG.png)

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](https://i.sstatic.net/fbO4P.png)

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](https://i.sstatic.net/5fdlJ.png)

---

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](http://www.mpi-inf.mpg.de/~elbassio/pub/Inappro+Dijkstra.pdf).  
2 L. Cai and J. Mark Keil, *"Finding the k most vital nodes in an interval graph."* [link](http://homepage.usask.ca/~tsv552/WAGT2011/talk%20MK.pdf).

*Note: this question is a follow-up to my stackoverflow question found [here](https://stackoverflow.com/questions/10338049/generating-a-tower-defense-maze-longest-maze-with-limited-walls-near-optimal).*

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: A clarification: you're not allowed to remove a set of nodes that would completely disconnect start from finish?  
> **username_0**: @David: Yes edited, sorry for the confusion.  There must still be a solution.  

---

## 1 answers

### Answer by username_1 on 2012-05-08. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_2**: Nice reduction!  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: 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!  
> **username_0**: One year and much learning (on my part) later, I now understand and agree with this proof.  Thank you again :)  

---

