Reconstructing binary matrices with timetabling constraints

This paper deals with the reconstruction of binary matrices having specific local constraints, called Timetable Constraints, imposed on their elements. In the first part of the paper, we show that instances of this problem with some fixed parameters are solvable in linear time by means of a greedy approach. In the following, thanks to a slight relaxation of one of the Timetable Constraints, we define a second and more complex greedy algorithm that solves a much wider family of instances. In both of these cases the computational complexity of our algorithms is linear in the dimension of the reconstructed matrix. Finally, we complete the framework by proving that all but one the remaining cases are NP-complete.