On the completability of incomplete orthogonal Latin rectangles

We address the problem of completability for 2-row orthogonal Latin rectangles (OLR2OLR2). Our approach is to identify all pairs of incomplete 2-row Latin rectangles that are not completable to an OLR2OLR2 and are minimal with respect to this property; i.e., we characterize all circuits of the independence system associated with OLR2OLR2. Since there can be no polytime 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 assignment. A complexity result is also at hand: completing a set of (n−1)(n−1) incomplete MOLR2MOLR2 is NPNP-complete.