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, pages 97–106.

BibTeX

@InProceedings{YinYang_CCCG2021,
  AUTHOR        = {Erik D. Demaine and Jayson Lynch and Mikhail Rudoy and Yushi Uno},
  TITLE         = {{Yin-Yang} Puzzles are {NP}-complete},
  BOOKTITLE     = {Proceedings of the 33rd Canadian Conference in Computational Geometry (CCCG 2021)},
  bookurl       = {https://projects.cs.dal.ca/cccg2021/},
  ADDRESS       = {Halifax, Nova Scotia, Canada},
  MONTH         = {August 10--12},
  YEAR          = 2021,
  PAGES         = {97--106},

  unrefereed    = 1,
  dblp          = {https://dblp.org/rec/conf/cccg/DemaineLRU21},
  comments      = {This paper is also available from the <A HREF="https://projects.cs.dal.ca/cccg2021/wordpress/wp-content/uploads/2021/08/CCCG2021.pdf#page=107">electronic proceedings</A> and as <A HREF="https://arXiv.org/abs/2106.15585">arXiv:2106.15585</A>.
                   <P>
                   The talk is available on <A HREF="https://youtu.be/TOErsTzTeuk">YouTube</A>
                   and the slides are available on <A HREF="https://github.com/edemaine/talk-yin-yang">GitHub</A>.},
  webpages      = {fonts/yinyang; fonts/yinyang/cccg.html},
}

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 from the electronic proceedings and as arXiv:2106.15585.

The talk is available on YouTube and the slides are available on GitHub.

Availability:

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