Paper by Erik D. Demaine

Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Roderick Kimball, and Justin Kopinsky, “Path Puzzles: Discrete Tomography with a Path Constraint is Hard”, Graphs and Combinatorics, volume 36, 2020, pages 251–267.

We prove that path puzzles with complete row and column information—or equivalently, 2D orthogonal discrete tomography with Hamiltonicity constraint—are strongly NP-complete, ASP-complete, and #P-complete. Along the way, we newly establish ASP-completeness and #P-completeness for 3-Dimensional Matching and Numerical 3-Dimensional Matching.

This paper is available as arXiv:1803.01176 and from SpringerLink.

The paper is 16 pages.

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

Related papers:
PathPuzzles_JCDCGGG2017 (Path Puzzles: Discrete Tomography with a Path Constraint is Hard)

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