Polarium Advance is NP-complete


In the spirit of Tetris, Sudoku, Minesweeper, and other games, we recently determined at the C&O open problem session that the game Polarium Advance is NP-complete. There is a pretty straightforaward reduction from “Hamiltonian path in induced subgraph of a grid graph” to Polarium Advance. That problem can be reduced from “Hamiltonian path in bipartite planar graph of maximum degree 3” as was shown in a 1982 paper by Itai, Papadimitriou and Szwarcfiter. While it would be nice to have developed a paper, it is somewhat encouraging to know that their paper used basically the same idea that we were developing, we were just a quarter of a century too late.

Here’s the formal statement of Polarium Advance.
Input: Integers m, n; an m-by-n grid graph; a (not necessarily proper) 2-colouring of the grid.
Question: Is there a simple path on the graph, such that after inverting the colours on that path, every row is monochromatic?

No Responses Yet to “Polarium Advance is NP-complete”

  1. 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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: