Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
We address a discrete tomography problem that arises in the study of the atomic structure of crystal lattices. A polyatomic structure \(T\) can be defined as an integer lattice in dimension \(D\geqslant 2\), whose points may be occupied by \(c\) distinct types of atoms. To ``analyze \(T,\) we conduct \(\ell\) measurements that we call discrete X-rays. A discrete X-ray in direction \(\xi\) determines the number of atoms of each type on each line parallel to \(\xi\). Given \(\ell\) such non-parallel X-rays, we wish to reconstruct \(T.\) The complexity of the problem for \(c=1\) (one atom type) has been completely determined by \textit{R. J. Gardner, P. Gritzmann} and \textit{D. Prangenberg} [(*) Discrete Math. 202, No. 1-3, 45-71 (1999; Zbl 0947.68160)], who proved that the problem is NP-complete for any dimension \(D\geqslant 2\) and \(\ell \geqslant 3\) non-parallel X-rays, and that it can be solved in polynomial time otherwise \textit{H. J. Ryser} [Combinatorial mathematics (1963; Zbl 0112.24806)]. The NP-completeness result above clearly extends to any \(c \geqslant 2\), and therefore when studying the polyatomic case we can assume that \(\ell=2\). As shown in another article by the same authors [Theor. Comput. Sci. (to appear)], this problem is also NP-complete for \(c\geqslant 6\) atoms, even for dimension \(D=2\) and axis-parallel X-rays. In (*) the authors conjecture that the problem remains NP-complete for \(c=3,4,5,\) although, as they point out, the proof idea in (*) does not seem to extend to \(c<5.\) We resolve the conjecture from (*) by proving that the problem is indeed NP-complete for \(c\geqslant 3\) in 2D, even for axis-parallel X-rays. Our construction relies heavily on some structure results for the realizations of 0-1 matrices with given row and column sums.
- On the computational complexity of determining polyatomic structures by X-rays
- scientific article; zbMATH DE number 1594509
- Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard: A solution to the 2-atom problem in discrete tomography
- On the computational complexity of reconstructing lattice sets from their X-rays
- Solving multicolor discrete tomography problems by using prior knowledge
- scientific article; zbMATH DE number 3182201 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Matrices of zeros and ones with fixed row and column sum vectors
- On the Complexity of Timetable and Multicommodity Flow Problems
- On the computational complexity of determining polyatomic structures by X-rays
- On the computational complexity of reconstructing lattice sets from their X-rays
- The reconstruction of binary patterns from their projections
- Three-dimensional Statistical Data Security Problems
- On the computational complexity of reconstructing lattice sets from their X-rays
- Tiling with bars under tomographic constraints.
- On tiling under tomographic constraints.
- On the computational complexity of determining polyatomic structures by X-rays
- On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity
- A formulation of the wide partition conjecture using the atom problem in discrete tomography
- A solvable case of image reconstruction in discrete tomography
- Using graphs for some discrete tomography problems
- scientific article; zbMATH DE number 1594509 (Why is no real title available?)
- Solving the two color problem: an heuristic algorithm
- Approximating Bicolored Images from Discrete Projections
- Reconstruction of binary matrices under adjacency constraints
- Solving some instances of the 2-color problem
- On the use of graphs in discrete tomography
- On the use of graphs in discrete tomography
- Reconstruction of domino tiling from its two orthogonal projections
- The NP-completeness of a tomographical problem on bicolored domino tilings
- Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem
- A reconstruction algorithm for a subclass of instances of the 2-color problem
- Minimal multicut and maximal integer multiflow: a survey
- Reconstruction of binary matrices under fixed size neighborhood constraints
- Reconstructing \(hv\)-convex multi-coloured polyominoes
This page was built for publication: Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941271)
