Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I thought of this while at the Combinatorial Potlatch at Seattle University, where Peter Winkler gave an excellent talk on Cops vs Drunken Robbers. I'll just open it up to the floor. The problem formulation might need some help too.

Let $G=(V,E)$ be a loopless graph. Let $w$ be a non-negative integer (and $\infty$) edge weighting, and let $s,r$ be non-negative (finite) integer vertex weightings. Let $S$, $R$ be real functions.

At each ply of the SWAT vs Rioters game we first remove the rioters, setting $r_v=0$, at any vertex $v$ for which the SWAT, $s_v$, overpowers them. The SWAT overpowers the Rioters (and perhaps arrests them all) whenever $S(s_v) \ge R(r_v)$. Then, either the Rioters or the SWAT, according to whose turn it is, must make a move by displacing at least one available unit from at least one vertex, along an edge, to at least one of its neighbours. The weight of the edge defines the maximum number of units that may be displaced through it, and units received from other neighbours in that ply are not "available" until the next turn.

Precisely defined, the above says, for each $v$, set $r_v=0$ if and only if $S(s_v) \ge R(r_v)$, and then, if it is the SWAT's turn, create a temporary variable $s_v'$ for each vertex $v$, and set $s_v' \leftarrow 0$. For each pair of vertices $u,v$, with an arc $uv$, and some number of units $k$, with $0\le k \le \min(w_{uv},s_u)$, set $s_v' \leftarrow s_v'+k$ and $s_u\leftarrow s_u-k$. Finally, for each vertex $v$, set $s_v = s_v+s_v'$. Do the same with $r$ if it is the Rioters' turn.

I'm only vaguely familiar with the usual Cop vs Robbers problems, but I suppose we would want to characterize conditions which are SWAT win, and find the number of moves it takes for SWAT to win, as well as an algorithm.

Take for example, all edge weights equal to 2, S(k)=k^2, R(k)=k. Then perhaps 1 SWAT and 3 Rioters at each vertex. Does anyone care to propose interesting initial conditions?

Cops vs Robbers is the case where edge weights are 1, S(k) = k, R(k) = k, 1 SWAT and 1 Rioter somewhere in the graph.

share|improve this question
1  
Just a few thoughts. First, it is probably best, at least to start, to insist that $S$ and $R$ are increasing functions. It seems like the graph should be SWAT-win if SWAT can eradicate the rioters given any initial configuration. Characterizing SWAT-win graphs in a very general way seems very difficult, so I would start with the obvious first steps: Trees, cycles, outerplanar graphs. Then a first question becomes: Given a weighted graph and initial numbers of SWAT/Rioters, can we determine if it is SWAT-win in polynomial time? I suspect the answer is no, but I'm not sure. –  Andrew D. King Nov 21 '11 at 23:20
    
If it is no, then see what happens for chordal graphs, then graphs of bounded treewidth. –  Andrew D. King Nov 21 '11 at 23:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.