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.


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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Dmytro Korduban Jan 7 '12 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.