1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What do you think? What have you tried? Where did you get stuck? $\endgroup$ Commented Jun 30, 2019 at 11:04

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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