A Single-Exponential Time Algorithm for the Maximum-Cardinality Weakly Stable Matching Problem with Ties and Incomplete Lists

Abstract

We study Stable Marriage with Ties and Incomplete lists (SMTI) under weak stability. For an instance with $n$ agents on each side, we give an exact algorithm that returns a maximum-cardinality weakly stable matching in $O^*(22.74^n)$ time. To the best of our knowledge, this is the first exact algorithm for this problem running in single-exponential time.