Input: undirected graph $G$, starting node $j$ for Justin Bieber (JB), and starting nodes for 4 fans $f_1, f_2, f_3, f_4$.

This problem has turns: for every turn, JB can either stay at his current node or move 1 node adjacent. Fans are working together and follow the same rules, but can share the same node. The fans are trying to occupy the same node as JB, and if any one of them achieves this, JB loses (Yes, you are on Justin's side for this problem!).

If both JB and his fans always have knowledge of the locations of everyone else, decide if it's possible for JB to avoid his fans indefinitely, no matter what his fans' strategies are. Your pseudo-code algorithm must be bound by a polynom in graph size $n+m = |V|+|E|$

This was a tricky, original problem from our algorithms class I'm really interested in. I was thinking that one way JB could avoid all the fans was if the graph was laid out in a way so that he and all his fans would go in a cycle forever, with JB at the front. But we weren't given the strategies for the fans though, so I'm just assuming they move in whatever direction that brings them closer to JB's location (but could there be a more complicated strategy they use, like box him in somehow?) I'm thinking for the pseudo code it should somehow decide whether JB and his fans can make such a cycle, but any help would be greatly appreciated.

  • $\begingroup$ In the literature, this problem is usually stated in terms of police men and robbers. $\endgroup$ – Raphael Jun 29 '17 at 5:12

Hint: What's the size of the state space?

The state of the world at any point is determined by _____. Therefore, there are ____ many possible states.

Fill in the blanks, then think about how to use those facts to help you devise an algorithm.


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.