CS Paper Radar

A Sub-$3^n$ Upper Bound on the Number of Stable Matchings

Ken-ichi Kawarabayashi, Hikaru Wada, Masataka Yoneda

cs.DS cs.DMmath.CO ·submitted 2026-11-04 14:54 UTC · v1
theory

Abstract

We study the problem of determining the maximum number of stable matchings. This classical counting problem was posed by Knuth and has been studied for five decades. We obtain a new $2.999^n$ upper bound on the number of stable matchings with $n$ men and $n$ women. This improves the best-known previous result by Palmer and Pálvölgyi. This result gets much closer to the well-known lower bound $\frac{2.28^n}{\text{poly}(n)}$. We refine their entropy-based framework by capturing broader structural relationships among stable matchings. To capture these relationships, we introduce new frameworks, including cones and supports. This establishes the $3.332^n$ bound. We also exploit relationships among local structures and use a charging argument to improve the bound to $2.999^n$.

Comment
56 pages, 12 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A $2.81^n$ upper bound on the number of stable matchings

cs.DS cs.DMmath.CO ·2026-11-04 ·Ebrahim Ghorbani, Matthias Mnich
theory similarity 0.82
Abstract

We study the maximum number ${\rm SM}(n)$ of stable matchings in an instance with $n$ men and $n$ women. Karlin, Oveis Gharan, and Weber (STOC 2018) proved the first single-exponential upper bound; their argument gives ${\rm SM}(n)\le 2^{17n}$ for sufficiently large $n$. Palmer and Pálvölgyi (FOCS 2021) improved this bound to $3.55^n+O(1)$. We prove that ${\rm SM}(n)<2.81^n$. This brings the exponential base closer to $2.28$, the base of the best known lower bound. More precisely, we bound the number of stable matchings in each instance in terms of each person's number of stable partners, where a stable partner is someone matched to that person in at least one stable matching. Our proof assigns each person a weight determined by this number and uses these weights to bound the number of stable matchings by induction.

0.23

A simplified proof of the FPRAS for counting perfect matchings

cs.DS math.CO ·2026-10-19 ·Chenghua Liu, Boning Meng
similarity 0.63
Abstract

We give a simplified, self-contained proof of OpenAI's FPRAS for counting perfect matchings in general graphs. As in the original proof, we use a restricted Poincaré inequality for two matchings to sample weighted perfect matchings and estimate their total weight. We simplify the proof of this inequality by isolating parts of alternating cycles directly on the original vertex set and controlling the resulting error terms. This avoids the auxiliary vertices and tree constructions used in the original proof. The argument preserves the required parameter bounds and yields the same FPRAS guarantee.

0.26

Fair Stable Matching: A Nash Social Welfare Approach

cs.GT cs.AI ·2026-09-02 ·Parth Desai, Rasheed M, Ganesh Ghalme, Sujit Gujar
similarity 0.62
Abstract

While traditional stable matching algorithms, such as the Gale-Shapley algorithm, prioritize stability, they may fall short of achieving equitable outcomes among participants. We study the role of \emph{Nash social welfare} (NSW) as a fairness objective in the classic \emph{stable marriage problem}. We develop \texttt{SNSW-Alg} that finds a stable matching that maximizes Nash social welfare under rank-induced utilities in $\tilde{\mathcal{O}}(n^4)$ time, where $n$ is the number of men or women. We demonstrate that \texttt{SNSW-Alg} balances equity while preserving stability. We empirically evaluate our methods across diverse preference distributions, demonstrating significant gains in fairness without substantial losses in other key measures such as regret, egalitarian criterion, and sex equality. Our findings suggest that the stable matching produced by \texttt{SNSW-Alg} is statistically Pareto-undominated by stable matchings based on other fairness measures - regret, egalitarian, and sex equality. This study offers compelling insights for designing fair-stable matching.

0.23

A 2/3-Approximation Algorithm for the Residual Maximum Matching Problem in General Graphs

cs.DS ·2026-10-20 ·Quanlong Niu, Riheng Jia
theory similarity 0.61
Abstract

The residual maximum matching problem asks for a maximum matching whose deletion leaves a graph with the largest possible matching number. For unweighted graphs, previous work provides a $1/2$-approximation guarantee in general graphs and a $2/3$ guarantee in graphs with a perfect matching. We present a $2/3$-approximation algorithm running in $O(n^5)$ time, extending the latter guarantee to general graphs. The algorithm improves the residual matching number through single-edge exchanges involving free vertices. We prove that, for any maximum matching that admits no further improvement by such exchanges, the residual matching number is at least $2/3$ of the optimum, and we give an example showing that this bound is tight.

0.09

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

cs.DS ·2026-10-29 ·Shuichi Miyazaki, Suguru Tamaki
similarity 0.61
Abstract · 13 pages

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.

0.54

Capacity Modification for Matching with Couples: An Integer Programming and Computational Study

cs.GT ·2026-10-23 ·Zexiao Wu, Genjiu Xu, Péter Biró
similarity 0.61
Abstract · 31 pages, 4 figures

We study capacity modification in the Hospitals/Residents problem with Couples, in which hospital capacities and a stable matching are jointly determined. Exact and Cutoff integer programming formulations are developed for the resulting problem. We assume that, for each couple, either both members are matched or neither is. For arbitrary strict preferences, every instance admits a stable matching after changing each hospital capacity by at most two. Total capacity increases by at most one, and this bound is tight. Under sub-responsive and sub-complete couple preferences, a stable matching exists after adding at most one position to each hospital. The total number of additions is at most the number of couples, and this bound is also tight. Computational experiments show that Exact formulations are modestly faster at fixed capacities, whereas Cutoff formulations perform substantially better in the minimum repair experiments and attain higher completion rates in markets with up to 30,000 doctors. Across 96,000 synthetic and reconstructed markets, small capacity changes restore existence whenever no stable matching exists at the original capacities.

0.25

A Matroid Generalization of Weighted Popular Matching: Characterization and Algorithm

cs.GT cs.DS ·2026-10-13 ·Yuni Iwamasa, Yusuke Kobayashi, Ryoga Mahara, Kenjiro Takazawa
similarity 0.60
Abstract

We study a problem that unifies two major generalizations of popular matchings in the one-sided preference model. In a bipartite graph in which each vertex, or applicant, on one side has preferences over the adjacent vertices, a matching is called popular if it does not lose a head-to-head election against any other matching. Since the seminal work of Abraham, Irving, Kavitha, and Mehlhorn, who gave the first polynomial-time algorithm for finding a popular matching, numerous generalizations of the popular matching problem have been investigated. Two prominent directions are weighted popular matchings, in which each applicant is assigned a voting weight, and popularity problems under matroid constraints. The former admits a polynomial-time algorithm due to Mestre, while the most general form of the latter is the popular common independent set problem, for which a polynomial-time algorithm is given by Kavitha, Makino, Schlotter, and Yokoi. In this paper, we introduce the weighted popular common independent set problem, which simultaneously generalizes weighted popular matchings and popular common independent sets. Our main result is the first polynomial-time algorithm for this problem. A key ingredient of the algorithm is a solution-independent characterization of weighted popular common independent sets, which we establish in this paper. As consequences of our algorithmic result, we obtain polynomial-time algorithms for several previously unresolved problems, including weighted popular matchings with matroid constraints and weighted popular branchings.

0.12

Maximum Cardinality Matching in $n^{2+o(1)}$ Time

cs.DS ·2026-10-29 ·George Z. Li, Jason Li, Junkai Zhang
similarity 0.60
Abstract

We consider the maximum cardinality matching problem in general graphs, and give an $n^{2+o(1)}$-time algorithm for the problem. Our work builds on recent work on combinatorial algorithms for maximum flow and extends the techniques to skew-symmetric flow problems which capture general matchings as a special case.

0.23