Reconstruction of binary matrices under fixed size neighborhood constraints

Using a dynamic programming approach, we prove that a large variety of matrix reconstruction problems from two projections can be solved in polynomial time whenever the number of rows (or columns) is fixed. We also prove some complexity results for several problems concerning the reconstruction of a binary matrix when a neighborhood constraint occurs.