On the (Parameterized) Complexity of Almost Stable Marriage

Sushmita Gupta, Pallavi Jain, Sanjukta Roy, Saket Saurabh, Meirav Zehavi

Introduction

In the classic Stable Marriage problem, the goal is to find a matching where no two agents prefer each other over their assigned partners. However, the Rural Hospital Theorem establishes a fundamental limitation: in markets with incomplete preference lists, every stable matching matches the exact same set of agents. To increase the size of the matching—a critical objective in applications like medical residency or school choice—one must inevitably sacrifice stability.

This paper investigates the computational trade-off in the Almost Stable Marriage (ASM) problem: finding a matching at least $t$ edges larger than a stable one, while allowing at most $k$ blocking edges. The authors also explore a Local Search (LS-ASM) variant, which seeks such a matching within a symmetric difference distance $q$ of an existing stable matching.

Hardness Reductions and Complexity

The authors demonstrate that the stability-size trade-off is computationally brutal. Using polynomial-time many-to-one reductions from the Multicolored Clique (MCQ) problem, they prove that ASM and its local search variant are W[1]-hard. This intractability holds even when the parameters $k, t,$ and $q$ are combined, and even in graphs with a maximum degree of four.

Extracted figure from page 8 of On the (Parameterized) Complexity of Almost Stable Marriage

The hardness results stem from the fact that the structure of preferences causes local changes to propagate globally in unpredictable ways. The intricate gadgets shown in the reduction illustrate how the problem can encode complex combinatorial structures, making it difficult to find even slightly larger matchings with minimal instability.

Parameterized Tractability

To overcome this intractability, the paper identifies the maximum degree ($d$) of the preference graph as a key parameter. While the problem is hard for $k+q+t$, it becomes fixed-parameter tractable (FPT) when $d$ is included. The authors develop a deterministic FPT algorithm for LS-ASM with a running time of $2^{O(q \log d) + o(dq)} \cdot n^{O(1)}$.

This algorithm utilizes a technique called Random Separation:

  1. Vertex and Edge Coloring: Vertices and edges are randomly colored to isolate the specific changes between the stable matching and the new solution.
  2. Size-Fitting: The problem is reduced to a Two-Dimensional Knapsack (2D-KP) problem to find the optimal set of augmenting paths and cycles that maximize size while minimizing blocking pairs.
  3. Derandomization: The process is made deterministic using $n-p-q$-lopsided universal families, ensuring a "perfect" coloring is found within a small family of hash functions.

Key Insights and Future Work

The study reveals that local search is not a "silver bullet"; the problem remains hard unless the graph is relatively sparse (low $d$). In dense markets where agents have long preference lists, the trade-off remains computationally expensive.

Future research directions include exploring alternative stability measures, such as the sum of regrets or egalitarian measures, and extending these results to the Stable Roommates problem (general graphs). The current findings suggest that even highly structured preferences, such as those derived from global master lists, do not necessarily simplify the fundamental difficulty of balancing stability and size.

Summary updated

BibTeX
@inproceedings{gupta2020parameterized,
  author = {Sushmita Gupta and Pallavi Jain and Sanjukta Roy and Saket Saurabh and Meirav Zehavi},
  title = {{On the (Parameterized) Complexity of Almost Stable Marriage}},
  booktitle = {FSTTCS},
  year = {2020},
  url = {https://openreview.net/forum?id=sMzsXb1Sfn},
}
Figure