Exact-Exponential Time and FPT Algorithms for the Stable Marriage Problem and its variants
Summary
Stable matching problems, such as the Stable Roommates (SR) and Stable Marriage with Ties and Incomplete lists (SMTI), have numerous applications in economics and computer science. In this thesis, we provide a 2^O(n) time algorithm to enumerate all stable matchings in instances of SR, enabling optimization variants to run with the same time complexity. We also develop fixed-parameter tractable (FPT) algorithms parameterized by the cutwidth for matching problems, including Max-SMTI, Max-SRTI, and MaxC3DSMTI.