3
$\begingroup$

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.

$\endgroup$

closed as off topic by Suresh Venkat Jan 7 '12 at 14:39

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Reposted to mathoverflow.net/questions/85051/… $\endgroup$ – Dmytro Korduban 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$ – Suresh Venkat 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$ – Tsuyoshi Ito Jan 7 '12 at 1:42
  • $\begingroup$ Then maybe it should be closed here ? Reposting is not really encouraged. $\endgroup$ – Suresh Venkat 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$ – Suresh Venkat Jan 7 '12 at 14:39