Lindley Hall 102 (4:15pm-4:45pm)

Eric McDermid
University of Wisconsin at Milwaukee

Hardness Results on the Man-Exchange
Stable Marriage Problem with Short Preference Lists

We present two hardness results on a variant of the well known Stable Marriage Problem, called the Man-Exchange Stable Marriage Problem: given n men and n women, each having a list of the individuals of the opposite sex in strict order of preference, we wish to find a matching M of the men and women that has no man-woman pair who prefer each other over their spouses, and also no pair of men prefer each other's spouses over their own in M . We first show that it is NP-Complete to determine whether a given instance admits such a matching even if the men's and women's preference lists are restricted to have lengths at most k and k' , respectively, for any k that is at least four, and k' that is at least three. This result settles Irving's recent conjecture that the problem is NP-Complete when the men's preference lists are restricted to have length at most four. We then prove that a related minimization problem remains NP-hard if the lists are restricted to even shorter lengths.

Joint work with C. Cheng and I. Suzuki