Abstract
We consider the stable matching problem when the preference lists are not given explicitly but are represented in a succinct way and ask whether the problem becomes computationally easier. We give subquadratic algorithms for finding a stable matching in special cases of two very natural succinct representations of the problem, the d-attribute and d-list models. We also give algorithms for verifying a stable matching in the same models. We further show that for d = \omega(\log n) both finding and verifying a stable matching in the d-attribute model requires quadratic time assuming the Strong Exponential Time Hypothesis. The d-attribute model is therefore as hard as the general case for large enough d.
Joint work with Stefan Schneider and Ramamohan Paturi.