Single-Player and Two-Player Buttons & Scissors Games

We study the computational complexity of the Buttons & Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for C = 2 colors but polytime solvable for C = 1. Similarly the game is NP-complete if every color is used by at most F = 4 buttons but polytime solvable for F ≤ 3. We also consider restrictions on the board size, cut directions, and cut lengths. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.

keywords: Computational Geometry, Graph Drawing, Puzzles

Workshop or Poster (weakly reviewed)

Aaron Williams, Adam Hesterberg, Christiane Schmidt, Erik Demaine, Hiro Ito, Irina Kostitsyna, Kyle Burke, Maarten Löffler, Michael Hoffmann, Robert Hearn, Ryuhei Uehara, Yushi Uno
Single-Player and Two-Player Buttons & Scissors Games
Proc. 18th Japan Conference on Discrete and Computational Geometry and Graphs
(to appear), 2015

Archived Publication (not reviewed)

Aaron Williams, Adam Hesterberg, Christiane Schmidt, Erik Demaine, Harrison Gregg, Hiro Ito, Irina Kostitsyna, Jody Leonard, Kyle Burke, Maarten Löffler, Michael Hoffmann, Robert Hearn, Ryuhei Uehara, Yushi Uno
Single-Player and Two-Player Buttons & Scissors Games
1607.01826, 2016
http://arXiv.org/abs/1607.01826

back to list