It’s spring break here- I was expecting to take the week off, but got this post done anyway. This might mean I skip *next* week though.

**The problem: **Generalized Geography. This is problem GP2 in the appendix.

**The description: **Given a directed graph G=(V,A) and a starting vertex v_{o}. Players alternate choosing edges that leave the current vertex (starting with v_{0}. The next current vertex is the one at the end of the edge leaving from v_{o}. You can’t choose an edge that is already chosen. The first player to be unable to choose an edge loses. Does Player 1 have a forced win?

**Example: **This is the “geography” game kids play in the car, where you have to think of a place that has as its first letter the last letter of the previous choice. As a graph problem, vertices correspond to letters, and edges to locations:

Note that the vertices can have self-loops, and (at least in the actual game) could have multiple edges between pairs of vertices. There is no requirement to have any edges leave a vertex either- I remember instituting the “Phoenix rule” on car trips because nobody could think of a place that started with X.

Anyway, if we start at E, player 1 has a forced win- they have to take “Egypt” to T, and then player 2 has to take “Texas” to S, and if player 1 chooses “Singapore” we’re in vertex E, it’s player 2’s turn, and they have no place left to pick. (The actual game has many more edges, of course)

**Reduction:** Schaefer says he’s building off of the Sequential Truth Assignment problem from last time, but his instance looks more like an instance of QBF. (I think this is a result of his claim that they’re basically the same problem). So 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 ∃)

We then go on to build a graph. Each positive and negative literal gets a vertex. Each variable x_{1} gets 4 vertices in the graph:

- x
_{i}corresponding to a positive literal - ~x
_{i}corresponding to a negative literal - 2 vertices u and v that control the “entrance” and “exit” for the setting of one of the 2 literal values.

We have a vertex for each clause (y_{i}), and an additional vertex u_{n+1} so the last v_{i} has someplace to go.

Each set of these 4 vertices are set up in a diamond, with edges from u_{i} to both x_{i }and ~x_{i}, and then from both of those to v_{i}. v_{i} then connects to u_{i+1}, making a chain of diamonds. The final u_{n+1} connects to each y vertex, and each y vertex connects to the literals that are in its clause.

Here’s the example picture from the paper:

Player 1 starts on vertex u_{1}. The player chooses whether to make variable x_{1} positive or negative by going to that vertex (simulating a “there exists”), and player 2 has no choice but to move on to the v_{1} vertex, and player 1 has no choice to move to the next u_{2 }(simulating a “for all”). This alternating process continues until we hit vertex u_{n+1}. Since there are an odd number of variables, it is now player 2’s turn.

If the setting of the variables has not satisfied some clause, player 2 can move to the y vertex of that unsatisfied clause. Then player 1 has to go to one of the 3 literals that appear in that clause. Since the clause was not satisfied, all of these variables have not been chosen, so the edge from that literal to the v vertex is available for player 2 to pick. But after that, the vertex from the v vertex to the next u vertex has already been chosen, so player 1 loses.

If the setting of the variables has satisfied every clause, then player 2 has to pick a move to a y vertex that has a literal chosen by a player to satisfy it. When player 1 moves to that vertex, the only edge exiting that vertex has already been chosen, so player 2 loses.

**Difficulty: **7. I think this is very slick and elegant, but I don’t see a student getting there without lots of help.