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 dened 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.