Reconstruction of binary matrices under adjacency constraints

Given a binary matrix, its horizontal and vertical projections are defined asthe sum of its elements for each row and each column, respectively. It is well-known that the basic problem,where the only constraints to verify are both projections, can be solved inpolynomial time. Numerous studies deal with this problem when additionalconstraints have to be taken into account. In this chapter we study two additional constraints for this problem. In a first part we take into account the“non-adjacency” constraint that depends on the definition of neighborhood:if a cell value is 1, then the values of each one of its neighbors must be 0. Thisproblem arises especially in statistical physics to determine the microscopicproperties (energy, density, entropy). In the model of Hard Square Gas, twoadjacent cells cannot be occupied simultaneously by particles because the energyof repulsion between them is very high.In the second part, we are concerned with a different constraint that imposesthat in every row of the binary matrix no isolated cell with value 1 ispermitted, and the maximum number of consecutive cells of value 0 is notgreater than a prescribed integer k. Taking into account this constraint, thereconstruction of binary matrices has natural applications in timetabling andworkforce scheduling