Skip to content

Pathery is NP-complete

February 16, 2013

Recently I’ve been playing Pathery, a game in which you place blocks to maximize the length of the shortest path in a grid (with some previously placed blocks already).

I had always been quite sure Pathery was NP-complete, but only a few days ago did I decide to really try to prove it, while out to lunch with Shaunak.  Together we came up with a simple proof.  It was much easier than I initially expected, and makes for a decent exercise, so stop reading if you don’t want this spoiled.

If you’ve checked out the game, which I recommend you do, skip this section.  Otherwise, here’s the gist:

  • There a bunch of specially marked squares, which I’ll call checkpoints.  Checkpoints are labeled (non-uniquely).  The labels are ordered (A, B, C…), and the path must touch them in order, before reaching the target (that is, it needs to touch one checkpoint for each label).
  • You cannot place blocks such that there is no valid path.

There are also other mechanics and rules which are unnecessary for this reduction.  In the game, you are given a limited number of blocks.  But for our purposes, we’ll assume we have as many blocks to place as there are spaces on the board (so effectively infinite).

And of course, although the website’s puzzles are bounded, we generalize by allowing increasing board sizes and number of checkpoints.  And as per the standard procedure for turning optimization problems into decision problems, we will ask “Is it possible to make the shortest path longer than X?”

Proof of NP-completeness:

The problem is in NP, since shortest path is in P.  To show hardness, we’ll reduce from SAT.

Let’s say I have n variables x_i, and m clauses C_j.  We’ll create checkpoints corresponding to variable assignments.  We”ll denote them by X_i and \hat{X_i}, corresponding to the assignment of variable x_i to be True or False.  Let’s first not worry about the order of checkpoints.  It turns out it won’t matter at all.

Start out by imagining a board which is entirely filled, except for a straight “main path” of length L and across the center.  There will be three types of deviations from this main path:

1. Variable assignment forks

There is one variable assignment fork for each variable.  Instead of the main path continuing straight, it is allowed two options, up and down.  The up path reaches the X_i checkpoint, and the down path reaches the \hat{X_i} checkpoint.  We cannot block both of these, since it would block the overall path.

2. Variable assignment offshoots

Variable assignment offshoots are huge orthogonal offshoots from the main path.  There is one offshoot for each variable assignment, and the corresponding checkpoint is at the end of the offshoot.  The length of the offshoot will be such that the dominant consideration for the overall path length is how many offshoots we can force the path to traverse.

We already noted that we can force at most n of the offshoots, since each assignment fork forces us to leave one variable assignment checkpoint open.  Thus the question is, can we force exactly n?  In order to do this, none of the other n variable assignment checkpoints can be easily-accessible on the rest of the board.

3. Clause forks

Almost done already.  For each clause, we will have a clause fork, a generalization of the variable assignment fork.  If we have a clause with k literal, the main path splits into k disjoint paths, before joining back up.  On these paths lie checkpoints corresponding to the literals; if the literal is true in the clause, there is a X_i checkpoint, and if it is false, there is a \hat{X_i} checkpoint.

Again, we must leave at least one of the branches open, or else we will block the path.  If the branch does not correspond to one of the “assignments” we made in the variable assignment forks, then we will hit a new checkpoint and not have to traverse its corresponding offshoot.  Thus in order to force traversing n offshoots, each clause fork must have a branch with a checkpoint corresponding to an “assignment” we already made.

Thus it is possible to force us to traverse n offshoots if and only if there is a satisfying assignment to the SAT instance!

Done!

Our main path has length O(n+m) and we have O(n) total checkpoints, and so regardless of the checkpoints’ order, we can spend at most O(n \cdot (n + m)) steps on the main path.  Thus by making the offshoots have length L = \Theta(n^2 \cdot (n + m)), we can simply set a score threshold of nL, so that being able to reach the score corresponds precisely to finding a satisfying assignment.

Food for future thought:

What if we don’t allow for arbitrarily many checkpoints?

EDIT:  It turns out planar Hamiltonian path is NP-complete, so it’s pretty much trivial to show that even with no checkpoints, it’s NP complete.

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: