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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Japan
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131806 |