Algorithms and complexity of strongly stable non-crossing matchings

Given a set of n men, a set of n women, and their preference lists containing persons of the opposite gender in strict order of preference, a matching is a set of man–woman pairs such that no two men (resp. women) are matched with the same woman (resp. man). A blocking pair of a matching is a man–woman pair, say ( m , w ), where m ’s (resp. w ’s) preference list contains w (resp. m ), such that m is either unmatched or prefers w to his current partner, and w is either unmatched or prefers m to her current partner. A matching is called stable if it has no blocking pair. A matching is called non-crossing if it does not have any pair of edges that cross each other when all men and women are aligned on two parallel vertical lines with men ordered (in a fixed manner) on one line and women ordered on the other. A matching which is both stable and non-crossing is called a strongly stable non-crossing matching (SSNM). It is known that the problem of determining the existence of an SSNM is NP-complete in the presence of ties in the lists. We show that this problem is fixed-parameter tractable (FPT) when parameterized by the sum of lengths of all ties . We study two new alignments other than the parallel-lines alignment and show that this problem remains NP-complete on one but becomes polynomial-time solvable on the other. Next, we introduce a new notion of stable non-crossing matching, namely semi-strongly stable non-crossing matching (SSSNM). We prove that the problem of determining the existence of an SSSNM is NP-complete even if the size of every man’s preference list is at most two. On the positive side, we show that this problem is linear-time solvable if the size of every man’s preference list is at most one, with no restriction on the sizes of women’s preference lists.