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

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

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

CC BY-SA 3.0
2012-01-06T13:19:41.103Z
Reposted to http://mathoverflow.net/questions/85051/graph-connectivity-related-game
Dmytro Korduban
CC BY-SA 3.0
2012-01-07T00:03:09.110Z
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 ?
Suresh Venkat
CC BY-SA 3.0
2012-01-07T01:42:24.233Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-07T02:27:35.907Z
Then maybe it should be closed here ? Reposting is not really encouraged.
Suresh Venkat
CC BY-SA 3.0
2012-01-07T09:42:32.420Z
@SureshVenkat Yes, in case of no ϵ-transitions it's just min cut. The answer is given [here](http://mathoverflow.net/questions/85051/graph-connectivity-related-game/85070#85070).
Dmytro Korduban
CC BY-SA 3.0
2012-01-07T14:39:49.553Z
In general we don't approve of simultaneous crossposting. In the future, please wait a day or two before crossposting. Closing now..
Suresh Venkat
<ds.algorithms><graph-theory><graph-algorithms><gt.game-theory><max-flow-min-cut>
Graph connectivity related game
Dmytro Korduban
# Graph connectivity related game

(Asked by: username_0 on 2012-01-06)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, gt.game-theory, max-flow-min-cut

> **Comments:**
> **username_0**: Reposted to http://mathoverflow.net/questions/85051/graph-connectivity-related-game  
> **username_1**: 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 ?  
> **username_2**: @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.  
> **username_1**: Then maybe it should be closed here ? Reposting is not really encouraged.  
> **username_0**: @SureshVenkat Yes, in case of no ϵ-transitions it's just min cut. The answer is given [here](http://mathoverflow.net/questions/85051/graph-connectivity-related-game/85070#85070).  
> **username_1**: In general we don't approve of simultaneous crossposting. In the future, please wait a day or two before crossposting. Closing now..  

---

## 0 answers

