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.