Paper by Erik D. Demaine
- Erik D. Demaine, Jayson Lynch, Mikhail Rudoy, and Yushi Uno, “Yin-Yang Puzzles are NP-complete”, in Proceedings of the 33rd Canadian Conference in Computational Geometry (CCCG 2021), Halifax, Nova Scotia, Canada, August 10–12, 2021, to appear.
We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru
pencil-and-paper puzzles. Viewed as a graph partitioning problem,
we prove NP-completeness of partitioning a rectangular grid graph
into two induced trees (normal Yin-Yang),
or into two induced connected subgraphs (Yin-Yang without 2 × 2
rule), subject to some vertices being pre-assigned to a specific tree/subgraph.
- This paper is also available as arXiv:2106.15585.
- The paper is available in PDF (917k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 21, 2021 by