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

“A Single-Exponential Time Algorithm for the Maximum-Cardinality Weakly Stable Matching Problem with Ties and Incomplete Lists” (2026), by Shuichi Miyazaki et al. Economics research paper. Original abstract below, unchanged. A free PDF is available.

- Authors: Shuichi Miyazaki, Suguru Tamaki
- Published: October 29, 2026
- Field: Economics
- DOI: https://doi.org/10.48550/arxiv.2610.39764
- Free PDF: https://arxiv.org/pdf/2610.39764

## 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ⁿ) time. To the best of our knowledge, this is the first exact algorithm for this problem running in single-exponential time.

Canonical page: https://nerdi.pages.dev/paper/W7224741306
Read three real papers a day in Nerdi (iPhone): https://apps.apple.com/app/apple-store/id6813826387?pt=128757794&ct=web-paper&mt=8