A dynamic nimber week

The June 19 - June 25 week did not actually have any rounds that I'd like to mention, so let me turn back to the problem from the previous week's summary.

You are given an acyclic directed graph with n<=15 vertices and m arcs. Vertices 1 and 2 each contain a chip. Two players take alternating turns, each turn consisting of moving one of the chips along an arc of the graph. The player who can't make a valid move loses. We want to know which player wins if both play optimally. Now consider all 2^m subsets of the graph's arcs; for how many of them does the first player win if we keep only the arcs from this subset?

Without the subset part, the problem is pretty standard. We need to compute the nimbers for all vertices of the graph, and the first player wins if and only if the nimbers for the first two vertices are different.

However, we do not have the time to even iterate over all subsets, and thus we can not apply this naive algorithm. Dynamic programming comes to the rescue, allowing to reuse some computations. The dynamic programming idea that is closest to the surface is: go in a topological ordering, and keep computing the nimbers. The nimber for a vertex depends on which arcs going from this vertex are included in the subset, and on the values of nimbers for the vertices reachable from this one, so our dynamic programming state should include only the values of nimbers for the already processed vertices, reducing the running time from 2^m to something around the n-th Bell number. That is still not too little, but it turns out this approach could be squeezed to pass.

However, it turns out there is another beautiful dynamic programming idea that helps us move to the running time on the order of 3ⁿ. Instead of going vertex-by-vertex, we will now go nimber-by-nimber. For each consecutive nimber, we will try all possibilities for a subset a of vertices having this nimber. What are the requirements on such a subset? From the definition of nimbers we get:

1. For each vertex in this subset, there must be an arc to at least one vertex with each smaller nimber.
2. There must be no arcs within this subset.

Condition 2 is pretty easy to check, but condition 1 is not. However, we can notice that we can instead check:

1. For each vertex that still has no assigned nimber (and thus will eventually have a higher nimber), there must be an arc to at least one vertex in this subset.
2. There must be no arcs within this subset.

The new condition 1 guarantees that all higher nimbers will have arcs to all lower nimbers, so by the time we reach a certain nimber, we don't need to care about arcs to lower nimbers anymore. Now we can see that the state of our dynamic programming can simply be the last placed nimber and the set of vertices that do not yet have a nimber.

Finally, we can notice that the last placed nimber does not actually take part in the computations at all, so we can reduce the number of states n times more to just remembering the set of vertices that do not yet have a nimber, yielding overall complexity of O(n*3ⁿ).

Thanks for reading, and check back for the next week's summary!