# Graph connectivity related game

I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of edges in a single move and Runaway can move from a current vertex to an adjacent vertex (cutting an edge means that corresponding vertices became not adjacent). Runaway starts at vertex $s$ and wants to make it into vertex $t \neq s$; Police wants to interfere her. Police move first.

Let the game cost for Police be equal to the number of cutted edges. An $s-t$ minimal cut size is an obvious upper bound for this value, but sometimes Police can do better. For example, consider a $K_{n,2}$ graph ($n > 2$) where $s$ and $t$ both belong to the smaller (second) part. Minimal cut between $s$ and $t$ equals $n$, though cutting only 2 edges is enough (Police cuts empty set on her first move hence forcing Runaway to move away from $s$, then she cuts 2 edges adjacent to Runaway's location). Efficient computation of that cost seems to be an interesting problem.

I came up with a clumsy (still polynomial-time) algorithm which basically does loads of min-cut computations on $G$ subgraphs for this (however I'm not completely sure in the correctness). I wonder if it is a known problem or not, maybe there is some elegant solution? Please provide any related info.

-
Repost from cstheory.stackexchange.com/questions/9625/… –  Dmytro Korduban Jan 6 '12 at 13:19

This looks like problem J (titled "Tunnels") from the 2007 edition of a computing olympiad called the ACM ICPC; the problem statement is here and the problemsetter's solution is mirrored in this Github repository.

-
Thank you for an instantaneous hit! I had the similar idea but Derek Kisman's solution is much more clear. I wonder about possible applications of this kind of connectivity number, though. –  Dmytro Korduban Jan 7 '12 at 11:01