Path Puzzles: Discrete Tomography with a Path Constraint is Hard

Path Puzzles: Discrete Tomography with a Path Constraint is Hard

Abstract 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...

Full description

Bibliographic Details
Main Authors: Bosboom, Jeffrey, Demaine, Erik D, Demaine, Martin L, Hesterberg, Adam, Kimball, Roderick, Kopinsky, Justin
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: Springer Japan 2021
Online Access:https://hdl.handle.net/1721.1/131806

Internet

https://hdl.handle.net/1721.1/131806

Similar Items