LIPIcs.ISAAC.2019.32.pdf
- Filesize: 1.45 MB
- 12 pages
Document
On the Complexity of Lattice Puzzles
Authors
Koki Suetsugu 
,
Ryuhei Uehara
-
Part of:
Volume:
30th International Symposium on Algorithms and Computation (ISAAC 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-11-28
File
Document Identifiers
Author Details
Acknowledgements
The authors thank Prof. Shuji Yamada for his introduction of his original designed lattice puzzle to the first three authors. The authors also thank JCDCGGG 2017 for giving a chance to give an oral presentation of the early work on this topic, which motivated the last author to join this research. The last author thanks Hisayoshi Akiyama and Mineyuki Uyematsu who kindly taught him the history of the lattice puzzle.
Cite As Get BibTex
Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, and Ryuhei Uehara. On the Complexity of Lattice Puzzles. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 32:1-32:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.32
Abstract
In this paper, we investigate the computational complexity of lattice puzzle, which is one of the traditional puzzles. A lattice puzzle consists of 2n plates with some slits, and the goal of this puzzle is to assemble them to form a lattice of size n x n. It has a long history in the puzzle society; however, there is no known research from the viewpoint of theoretical computer science. This puzzle has some natural variants, and they characterize representative computational complexity classes in the class NP. Especially, one of the natural variants gives a characterization of the graph isomorphism problem. That is, the variant is GI-complete in general. As far as the authors know, this is the first non-trivial GI-complete problem characterized by a classic puzzle. Like the sliding block puzzles, this simple puzzle can be used to characterize several representative computational complexity classes. That is, it gives us new insight of these computational complexity classes.
Subject Classification
ACM Subject Classification
- Theory of computation → Problems, reductions and completeness
Keywords
- Lattice puzzle
- NP-completeness
- GI-completeness
- FPT algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Hisayoshi Akiyama. Cube Puzzle Book (in Japanese). Shinkigensha, 2004.
-
E. R. Berlekamp, J. H. Conway, and R. K. Guy. Winning Ways for Your Mathematical Plays, volume 1-4. A K Peters Ltd., 2001-2003.
-
M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015.
-
M.R. Garey and D.S. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, 1979.
-
R. A. Hearn and E. D. Demaine. Games, Puzzles, and Computation. A K Peters Ltd., 2009.
-
Takumi Kasai, Akeo Adachi, and Shigeki Iwata. Classes of pebble games and complete problems. SIAM Journal on Computing, 1979.
- R. Uehara, S. Toda, and T. Nagoya. Graph Isomorphism Completeness for Chordal Bipartite Graphs and Strongly Chordal Graphs. Discrete Applied Mathematics, 145(3):479-482, 2004. URL: https://doi.org/10.1016/j.dam.2004.06.008.