Rotations in the stable -matching problem

This paper deals with the stable -matching problem on general multigraphs. We generalize the notion of singular and dual rotations and establish a one–one correspondence between stable -matchings and certain sets of rotations. This correspondence is used to find all stable edges and a minimum regret stable -matching in polynomial time. We also recall the NP-completeness of the egalitarian stable -matching problem.