Yin-Yang Puzzles are NP-complete

06/29/2021
by   Erik D. Demaine, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset