Path puzzles: discrete tomography with a path constraint is hard

DOI10.1007/S00373-019-02092-5MaRDI QIDQ2308497zbMATH OpenOpenAlexWikidataFDO

Authors Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Roderick Kimball, Justin Kopinsky

Publication date 3 April 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.01176

zbMATH Keywords

3-dimensional matching\#P-completenessASP-completenessdiscrete tomographynumerical 3-dimensional matching

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computing methodologies for image processing (68U10)

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 for 3-Dimensional Matching and Numerical 3-Dimensional Matching.

Recommendations

• Tile-packing tomography is \({\mathbb{NP}}\)-hard
• Tile-packing tomography is \(\mathbb{NP}\)-hard
• Using graphs for some discrete tomography problems
• On the difference between solutions of discrete tomography problems
• Discrete tomography and plane partitions
• On the use of graphs in discrete tomography
• On the use of graphs in discrete tomography
• Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard: A solution to the 2-atom problem in discrete tomography
• Bounds for discrete tomography solutions
• scientific article; zbMATH DE number 1551782

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1551778 (Why is no real title available?)
• Planar 3DM is NP-complete
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems

Cited in

(4)

• Rectangular spiral galaxies are still hard
• The fewest clues problem of Picross 3D
• About the Complexity of Timetables and 3-Dimensional Discrete Tomography: A Short Proof of NP-Hardness
• Tetris with few piece types

This page was built for publication: Path puzzles: discrete tomography with a path constraint is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2308497)