Reconstructing 3-colored grids from horizontal and vertical projections is NP-Hard: a solution to the 2-Atom problem in discrete tomography

Abstract

We consider the problem of coloring a grid using k colors with the restriction that each row and each column has a specific number of cells of each color. This problem has been known as the (k - 1)-atom problem in the discrete tomography community. In an already classical result, Ryser obtained a necessary and sufficient condition for the existence of such a coloring when two colors are considered. This characterization yields a linear time algorithm for constructing such a coloring when it exists. Gardner et al. showed that for k >= 7 the problem is NP-hard. Afterward Chrobak and Durr improved this result by proving that it remains NP-hard for k >= 4. We close the gap by showing that for k = 3 colors the problem is already NP-hard. In addition, we give some results on tiling tomography problems.