Paper by Erik D. Demaine

Reference:
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.

Abstract:
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.

Comments:
This paper is also available as arXiv:2106.15585.

Availability:
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 BibTeX file.
Last updated July 21, 2021 by Erik Demaine.