On the completability of incomplete orthogonal Latin rectangles

We address the problem of completability for 2-row orthogonal Latin rectangles (OLR2). Our approach is to identify all pairs of incomplete 2-row Latin rectangles that are not com- pletable to an OLR2 and are minimal with respect to this property; i.e., we characterize all circuits of the independence system associated with OLR2. Since there can be no poly- time algorithm generating the clutter of circuits of an arbitrary independence system, our work adds to the few independence systems for which that clutter is fully described. The result has a direct polyhedral implication; it gives rise to inequalities that are valid for the polytope associated with orthogonal Latin squares and thus planar multi-dimensional assign- ment. A complexity result is also at hand: completing a set of (n - 1) incomplete MOLR2 is NP-complete.