Single-Player and Two-Player Buttons & Scissors GamesShow others and affiliations
2016 (English)In: DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 / [ed] Akiyama, J., Ito, H., Sakai, T., Uno, Y., SPRINGER INT PUBLISHING AG , 2016, Vol. 9943, p. 60-72Conference paper, Published paper (Refereed)
Abstract [en]
We study the computational complexity of the Buttons amp; 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 amp;lt;= 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.
Place, publisher, year, edition, pages
SPRINGER INT PUBLISHING AG , 2016. Vol. 9943, p. 60-72
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-133774DOI: 10.1007/978-3-319-48532-4_6ISI: 000389794000006ISBN: 9783319485324 (electronic)ISBN: 9783319485317 (print)OAI: oai:DiVA.org:liu-133774DiVA, id: diva2:1063058
Conference
18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG2)
2017-01-092017-01-092019-11-07Bibliographically approved