The soldiers and the canyon can be modeled as an undirected graph ~G~: Let each soldier be represented by one vertex, where there is an edge between two vertices if and only if areas visible by the two corresponding soldiers intersect or touch, i.e. the distance between the two soldiers is less than or equal to ~200~. Let there be two additional vertices ~s~ and ~t~, where ~s~ represents the northern side of the canyon and ~t~ the southern side of the canyon. Let these vertices be connected to all vertices representing soldiers who can see the respective side of the canyon, i.e. whose distance from the side is at most ~100~ meters.

Now it is fairly easy to decide if the canyon can be passed safely. Just perform either depth-first-search or breadth-first-search to check whether there is a path between ~s~ and ~t~ in ~G~. If that is the case, then there exists a continuous chain of areas visible by some soldier that connects the northern and southern sides of the canyon, thus keeping the prisoners from passing it. Vice versa, if there is no such chain of visible areas, the canyon can clearly be passed safely.

Deciding how many soldiers must be eliminated in order to pass the canyon safely is a bit more complicated. Since the canyon can be passed safely if and only if there is a path between ~s~ and ~t~ in ~G~, one has to find ~(s-t)~-vertex-connectivity of ~G~, i.e. how many vertices in ~G~ have to be deleted in order to disconnect ~s~ and ~t~. This is essentially a minimum cut problem. It can be solved by setting edge capacities to ~\infty~, vertex capacities to ~1~ and finding the maximum flow from ~s~ to ~t~ (contrary to the standard minimum cut problem for edges, where vertex capacities are set to ~\infty~ and edge capacities to ~1~). To make a standard maximum flow algorithm applicable, vertex capacities have to be eliminated, though. This can be done relatively easily by constructing a directed graph ~G'~, where each vertex of ~G~ except ~s~ and ~t~ is replaced by two vertices, in-vertex and out-vertex. If edges in ~G'~ are set according to figure 2.1 below, then the maximum flow from ~s~ to ~t~ in ~G~ will be equal to the maximum flow from ~s~ to ~t~ in ~G'~. Since there are no vertex capacities in ~G'~, this maximum flow and hence ~(s-t)~-vertex-connectivity of ~G~ can now be found using standard maximum flow algorithm.

Figure 2.1: Converting a vertex capacity (a) to an edge capacity (b)