I hadn’t heard of this game before encountering this problem. It sort of feels a lot like Nim to me.

**The problem: **Generalized Kayles. This is problem GP3 in the appendix.

**The description: **Given a graph G=(V,E). Players take turns removing vertices and all vertices adjacent to it from the graph. The first player to have no vertices left loses.

**Example: **Here’s a graph:

Suppose player 1 chooses vertex c. Then we also remove s,b, d, and t. All that is left are vertices a and e. Whichever vertex player 2 chooses, player 1 can choose the other one, and win.

**Reduction: **This one is again by Schaefer, and again uses the same problem which is either Sequential Truth Assignment or QBF, depending on how you look at it.

Just like last time, we’re given a formula: (∃ x_{1}) (∀ x_{2}) (∃ x_{3}) … (∃ x_{n)} (A_{1} ∧ A_{2} ∧ … A_{m}), where each A_{i} is a disjunction of literals. We’ll further assume n is odd (so the last quantifier is ∃). The graph is built as follows:

- Each clause k in the formula gets a vertex x
_{0,k}. These vertices are all connected to each other. - Each variable x
_{i}in the formula gets two vertices: x_{i}and ~x_{i, }that have an edge between them. We also get y vertices: y_{i,j}for all j 0 <= j < i - We add an edge between x
_{i}and x_{0,k}if x_{i}appears as a literal in clause k. Similarly, we add an edge between ~x_{i}and x_{0,k}if ~x_{i}appears as a literal in clause k. - Each y
_{i,j}vertex connects to all x_{k }vertices where k <= i. Each y_{i,j}vertex also connects to all y_{a,b}vertices where a < i and b < a.

Here’s a picture from the paper of what we get:

One main point that comes out of this construction is that players need to take their first n moves playing the x (or ~x) vertices in order. If you go out of order, the opponent can play a y vertex and remove everything. If you play a y vertex, the opponent can play an x vertex (or an x_{0} vertex) and remove everything.

If the original formula was satisfiable, player 1 (who is the ∃ player) starts by choosing either x_{1} or ~x_{1}. No matter which of x_{2} or ~x_{2} is chosen by the opponent (the ∀ player), player3 will have a way to set x_{3} to keep the formula satisfiable. This process continues for all variables. Once player 1 plays the last variable (x_{n} or ~x_{n}), all vertices have been removed from the graph- most importantly, all of the x_{0} vertices have been removed, because there is an edge from each one to each variable whose setting would satisfy the clause. Thus, player 2 has no place to play, and player 1 wins.

If the formula is not satisfiable, then after taking turns choosing x_{i} or ~x_{i} for all i, there is still some x_{0} vertex in the graph (corresponding to a clause not satisfied by the variable choices made). Player 2 can select that vertex, removing all x_{0} vertices from the graph, and will win.

**Difficulty: **7. I can see what the “jobs” of each vertex are: The x_{i} set the truth values of a variable, the x_{0} ensure that each clause is satisfied by a variable setting, and the y vertices are there to force players to choose the x_{i} vertices in order. I don’t think I could have come up with this though.