Reconstruction of binary matrices under adjacency constraints

Abstract. We consider a generalization of the classical binary matrix reconstruction problem by considering new constraints of adjacency between the cells: if a given cell is of value 1 then all its neighbors are of value 0. This problem arises especially on statistical physics. We consider several definitions of neighborhood and for each one we give complexity results and necessary and/or sufficient conditions for the existence of a solution.Key words and phrases: discrete tomography, matrix reconstruction, adjacency constraint