2019/06/28 by Jiehua Chen, Chen, Jiehua
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.GT
paper · pdf · doi:10.48550/arxiv.1906.12274
arxiv created 2021/02/22 · arxiv updated 2021/02/23
We study the Reaching Stable Marriage via Divorces (DivorceSM) problem of deciding, given a Stable Marriage instance and an initial matching M , whether there exists a stable matching which is reachable from M by divorce operations as introduced by Knuth [12]. Towards answering an open question of Manlove [13] and Cechlárová et al. [3], we show that for incomplete preferences without ties, DivorceSM is NP-hard. Our hardness reduction also implies that the problem remains parameterized intractable for the number κ of allowed divorce operations. It remains NP-hard even if the maximum length d of the preferences is a constant. For the combined parameter (κ, d), the problem is fixed-parameter tractable.