“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.

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

Shuichi Miyazaki, Suguru Tamaki · October 29, 2026 · Economics

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.

Free PDF DOI: 10.48550/arxiv.2610.39764