
Calculate the degree \(d\)  of a minimum regret stable matching and truncate preference lists accordingly. A minimum regret stable matching may be found in \(O(m)\)  time [1]}. We now assume all preference lists are truncated below rank \(d\) .

Calculate the man-optimal and woman-optimal stable matchings. The Extended Gale-Shapley Algorithm takes \(O(\min \lbrace m, nd\rbrace )\)  time since the number of acceptable pairs is now \(\min \lbrace m, nd\rbrace \) .

Find all rotations using the Minimal Differences Algorithm [2]} in \(O(\min \lbrace m, nd\rbrace )\)  time, since the number of acceptable pairs is now \(\min \lbrace m, nd\rbrace \) .

Build the rotation digraph and vb-network, using the process described in Section , but where rotation profiles are reversed and negated for the building of the vb-network. We know that no man-woman pair can appear in more than one rotation. This means that the number of vertices in each of the associated rotation poset, rotation digraph and vb-network is also \(O(\min \lbrace m, nd\rbrace )\) . Identical reasoning (with adapted time complexities to suit the generous case) to that of [2]} may be used to obtain a bound of \(O(\min \lbrace m, nd\rbrace )\)  on the number of edges. This is because we have a bound of \(O(\min \lbrace m, nd\rbrace )\)  for the creation of both type 1 and type 2 edges of the rotation digraph. Therefore we may build the rotation digraph and vb-network in \(O(\min \lbrace m, nd\rbrace )\)  time.

Find a minimum cut of the vb-network using the process described in Section . With \(O(\min \lbrace m, nd\rbrace )\)  vertices and edges and a maximum length of \(d\)  for any preference list, the [4]} algorithm [4]} has a time complexity of \(O(\min \lbrace m, nd\rbrace ^2 \log n)\) , with an additional factor of \(O(d)\)  to perform operations over vectors. Hence this step takes a total of \(O(\min \lbrace m, nd\rbrace ^2 d \log n)\)  time.

Use this cut to find a maximum profile closed subset \(S\)  of the rotations in \(O(\min \lbrace m, nd\rbrace )\)  time, since the numbers of vertices and edges are bounded by \(O(\min \lbrace m, nd\rbrace )\) .

Eliminate the rotations of \(S\)  from the man-optimal matching to find the corresponding rank-maximal stable matching.

