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 talk is available on YouTube and the slides are available on GitHub.

The paper is available in PDF (917k).
See information on file formats.
[Google Scholar search]

Related webpages:
Yin-Yang Font
Yin-Yang Font: CCCG Puzzle

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated October 17, 2021 by Erik Demaine.