Let $G=(V,E)$ be a DAG and let $v_0\in V$. Alice and Bob are playing a game in which every player has his own turn and Bob is starting. In every turn $i$, the player is picking an edge $e=(v_i,x)$, then $x$ become $v_{i+1}$ and then it becomes the other player's turn. The player which doesn't have an edge to choose (the vertex $v_i$ has no out edges) is losing.

Propose an algorithm which determines if Bob has a winning strategy.

  • $\begingroup$ What do you think? What have you tried? Where did you get stuck? $\endgroup$ – Yuval Filmus Jun 30 '19 at 11:04

For a vertex $v \in V$, let $W(v)$ be the following predicate: "a player starting at $v$ wins". If $N(v)$ is the set of outward neighbors of $v$, then $$ W(v) = \bigvee_{u \in N(v)} \lnot W(u), $$ where the empty disjunction is simply false.

This suggests a strategy to compute $W(v_0)$ using dynamic programming.

| cite | improve this answer | |

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.