Constrained Matchings in Bipartite Graphs

We consider some particular cases of the general problem which consists of stating if a shift vector of m elements corresponds to a permutation of the same number of objects. Shifts are defined as the steps each element in a given permutation must perform in order to reach its natural position, i.e., to its position in the fundamental permutation, (1, 2, ..., m). The problem, never studied at our knowledge, was suggested to us by a paper in which a certain number of vehicles must be moved from initial to nal positions in a grid graph in such a way that vehicles do not share the same vertex at the same time. The problem can also be stated in terms of a covering one, i.e. the vertex cover of a particular graph, with cycle using arcs of de ned lengths. Some properties of the shift vector, necessary in order to guarantee the existence of a corresponding permutation, and a general algorithm to find the permutations, if they exist, are given