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.

  • 1
    $\begingroup$ Reposted to mathoverflow.net/questions/85051/… $\endgroup$ Jan 6 '12 at 13:19
  • $\begingroup$ The rule forcing Runaway to always make a move (i.e no $\epsilon$-transitions) seems a little strange. Is it true that if this is not enforced, that the min cut is the optimal solution ? $\endgroup$ Jan 7 '12 at 0:03
  • $\begingroup$ @Suresh: I thought the same thing at first, but no, it is not strange. The game models the assumptions that Police can choose to wait until Runaway moves and that Runaway cannot wait forever without moving. By the way, the problem is basically already solved on MathOverflow by Maurício Collares Neto, who noticed that this is the same as a problem in ACM ICPC. $\endgroup$ Jan 7 '12 at 1:42
  • $\begingroup$ Then maybe it should be closed here ? Reposting is not really encouraged. $\endgroup$ Jan 7 '12 at 2:27
  • 2
    $\begingroup$ In general we don't approve of simultaneous crossposting. In the future, please wait a day or two before crossposting. Closing now.. $\endgroup$ Jan 7 '12 at 14:39