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$ 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 that you have read and understand our privacy policy and code of conduct.

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