[Back]

S. Gupta, S. Roy, S. Saurabh, M. Zehavi:
"Balanced stable marriage: How close is close enough?";
Theoretical Computer Science, 883 (2021), 19 - 43.

Balanced Stable Marriage (BSM)is a central optimization version of the classicStable Marriage (SM)problem. We studyBSMfrom the viewpoint of Parameterized Complexity. Informally, the input ofBSMconsists of nmen, nwomen, and an integer k. Each person ahas a (sub)set of acceptable partners, A(a), whom aranks strictly; we use pa(b)to denote the position of b ∈A(a)in a´s preference list. The objective is to decide whether there exists a stable matching μsuch that balance(μ) max{ (m,w)∈μpm(w), (m,w)∈μpw(m)} ≤k. InSM, all stable matchings match the same set of agents, A which can be computed in polynomial time. As balance(μ) ≥|A |2for any stable matching μ,BSMis trivially fixed-parameter tractable (FPT) with respect to k. Thus, a natural question is whetherBSMis FPT with respect to k −|A |2. With this viewpoint in mind, we draw a line between tractability and intractability in relation to the target value. This line separates additional natural parameterizations higher/lower than ours (e.g., we automatically resolve the parameterization k −|A |2). The two extreme stable matchings are the man-optimal μMand the woman-optimal μW. Let OM= (m,w)∈μMpm(w), and OW= (m,w)∈μWpw(m).

http://dx.doi.org/10.1016/j.tcs.2021.05.015

https://publik.tuwien.ac.at/files/publik_300321.pdf