Reaching Stable Marriage via Divorces is Hard

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.

No reviews yet.

No comments yet.