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.
