Paper by Martin L. 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)

Related webpages:
Path Puzzles Font

See also other papers by Martin Demaine.
These pages are generated automagically from a BibTeX file.
Last updated November 17, 2022 by Martin Demaine.