Continuing from the last blog post, the reduction from Node Kayles to the General Poset Game is not difficult. For each vertex, v, of the Kayles graph, G, add an element (also called v, let's say) to the partially-ordered set (poset), S. Each of these elements should be incomparable with each other. Thus, if there are no edges in G, all moves are equivalent and the game's value is *k where k is the parity of the number of nodes.
What if there are edges? A-ha, then for each edge (u, v), in G, we add
two elements to S: uv+, so uv+ > v and uv+ > u; and uv-, so that
for all vertices w (in G) not equal to u or v, uv- < w.
Now the first player has a winning strategy in the Poset Game on the
resulting set S exactly when they have a winning strategy in the Node
Kayles game on G. (This is not immediately obvious!)
... almost. This construction always works if G has an odd number of
edges. This is not a terrible requirement, since Grier shows how to
create an equivalently-winnable odd-edged graph from an even one.
I would like to post some pictures to explain the results of this
reduction, but that might be wasted effort because the figures Grier
supplies in his
paper are very clear.
More Computer Jokes
1 week ago