Balanced stable marriage: How close is close enough?

Balanced Stable Marriage (BSM) is a central optimization version of the classic Stable Marriage (SM) problem. We study BSM from the viewpoint of Parameterized Complexity. Informally, the input of BSM consists of n men, n women, and an integer k. Each person a has a (sub)set of acceptable partners, A (a) , whom a ranks strictly; we use p a (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) ∈ μ p m (w) , ∑ (m , w) ∈ μ p w (m) } ≤ k. In SM , all stable matchings match the same set of agents, A ⋆ which can be computed in polynomial time. As balance (μ) ≥ | A ⋆ | 2 for any stable matching μ , BSM is trivially fixed-parameter tractable (FPT) with respect to k. Thus, a natural question is whether BSM is 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 μ M and the woman-optimal μ W. Let O M = ∑ (m , w) ∈ μ M p m (w) , and O W = ∑ (m , w) ∈ μ W p w (m). In this work, we prove that • BSM parameterized by t = k − min ⁡ { O M , O W } admits (1) a kernel where the number of people is linear in t , and (2) a parameterized algorithm whose running time is single exponential in t. • BSM parameterized by t = k − max ⁡ { O M , O W } is W[1]-hard. [ABSTRACT FROM AUTHOR]