Paper by Erik D. Demaine

Reference:

Kyle Burke, Erik Demaine, Robert Hearn, Adam Hesterberg, Michael Hoffmann, Hiro Ito, Irina Kostitsyna, Maarten Löffler, Yushi Uno, Christiane Schmidt, Ryuhei Uehara, and Aaron Williams, “Single-player and two-player Buttons & Scissors games”, in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 60–72.

Abstract:

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 sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (4478k).

See information on file formats.

[Google Scholar search]

Related papers:

Buttons_JCDCGG2015 (Single-player and two-player Buttons & Scissors games)