Tag Archives: Difficulty 5

Planar Geography

In the process of reading up on the next problem in the appendix, I saw this nice reduction for a generalization of Geography that we used last week and will use next week.  So I thought it would make a nice addition to post it here.

The problem: Planar Geography.  This problem is not in the appendix (though the reference to this problem and the paper with this reduction appears in the notes to the “Generalized Geography” problem).

The description: Given an instance of the Generalized Geography problem, but where the graph G is planar, does Player 1 have a forced win?

Example: The example we had in the Generalized Geography problem is actually a planar graph:

Reduction: The paper by Lichtenstein and Sipser which has the reduction for next week’s NxN Go problem has this in the ramp-up.

What we’re doing to do is re-build the graph that was created in the Generalized Geography reduction.  That graph may not be planar. Any time the graph has two edges that cross:

We replace it with the following construction

(figures are on pages 395 and 396 of the paper).

The important things to realize are these:

1) If we use this on the graph generated from the original Geography Construction, it will never be the case that we will use both crossing edges in one solution.  This is an important point that isn’t really addressed in the paper.  The Lichtenstein and Sipser paper has a slightly different reduction for Generalized Geography where it’s easier to see.

2) Suppose it’s player 1’s turn, and they enter the intersection going up.  Then it will be their turn again once they hit the middle point.  The point of the extra loop structures (instead of just adding a vertex at the intersection point) is to create a situation where if player 1 decides to turn right, player 2 can turn down, and make player 1 lose.  This works in both directions.

Difficulty: I was hoping that this would be a good difficulty 4 or so problem in the middle of all of these really hard ones, but the whole “you’ll never use this intersection twice” problem makes the construction hard to see, and it’s a tough thing to think about why it matters, even if you told the student the rule.  Maybe this is a 5 if you give them that information.

Protected: Sequential Truth Assignment

This content is password protected. To view it please enter your password below:

Protected: Algebraic Equations over GF[2]

This content is password protected. To view it please enter your password below:

Protected: Partially Ordered Knapsack

This content is password protected. To view it please enter your password below:

Protected: Minimum Weight Solution to Linear Equations

This content is password protected. To view it please enter your password below:

Protected: Quadratic Programming

This content is password protected. To view it please enter your password below:

Protected: Job-Shop Scheduling

This content is password protected. To view it please enter your password below:

Protected: Flow-Shop Scheduling

This content is password protected. To view it please enter your password below:

Protected: Open-Shop Scheduling

This content is password protected. To view it please enter your password below:

Protected: Linear Bounded Automaton Acceptance

This content is password protected. To view it please enter your password below: