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