2021/06/29 by Erik D. Demaine, Demaine, Erik D., Jayson Lynch +5
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2106.15585
openalex publication_date 2021/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.