Reconstructing a binary matrix under timetabling constraints

Our focus is on the problem of reconstructing a m×n binary matrix M from its vertical and horizontal projections when the following additional constraints have to be satisfied: given an integer k⩾2, if Mij=1 then Mij−1=1 or Mij+1=1, and the maximal number of successive 0's on each row of M is not greater than k. We furnish a polynomial time algorithm for reconstructing M by reducing this problem to that of finding a path of given weight in a weighted directed acyclic graph.