# Stable Marriage with incomplete lists and ties - NP-hardness

According to [1] finding a weakly stable matching in a stable marriage (or SM) instance with incomplete lists and ties is NP-Hard.

According to [2] a weakly stable matching in a hospital-residents (or HR) instance with ties always exists and one can be found by arbitrarily breaking the ties and applying one of the known algorithms for the HR problem.

Also HR with ties is a generalization of SM with incomplete lists and ties.

Isn't there a conflict here?

[1] K. Iwama, D. Manlove, S. Miyazaki and Y. Morita. Stable Marriage with Incomplete Lists and Ties. Automata, Languages and Programming, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 1999

[2] R. W. Irving, D. F. Manlove, and S. Scott. The Hospitals/Residents Problem with Ties. Algorithm Theory - SWAT 2000. Lecture Notes in Computer Science. Springer Berlin / Heidelberg

[3] V. Bansal , A. Agrawal , V. S. Malhotra. Polynomial time algorithm for an optimal stable assignment with multiple partners. Theoretical Computer Science 379 (2007) 317–328

[4] D.F. Manlove, R.W. Irving, K. Iwama, S. Miyazaki, and Y. Morita. Hard variants of stable marriage.Theoretical Computer Science 276(1-2):261-279.

The stable marriage instance with ties is solvable in polynomial time, whereas the stable marriage instance with incomplete lists and ties is NP-hard.

The same holds for the Hospitals/Residents problem. So there is no conflict between [1] and [2].

• Thank you for your answer but isn't it true that the typical HR instance has incomplete lists anyway? At least this is the model in [2]. Commented Sep 27, 2011 at 9:19
• I think that the typical HR instance has incomplete lists and this model is more interesting. However the authors of [2] considered the complete lists model, probably because the original stable marriage problem (introduced in 1960s or before) assumes the complete lists model. Commented Sep 27, 2011 at 12:39
• If it is as you say then my question is answered but I quote [2]: "An instance of HR involves a set R of residents and a set H of hospitals, each resident r ∈ R seeking a post at one hospital, and each hospital h ∈ H having q(h) ≥ 1 posts. Each resident in R ranks a subset of H in strict order, and each hospital h ∈ H ranks its applicants in strict order. An agent p ∈ R ∪ H finds an agent q ∈ R ∪ H acceptable if q appears on p’s preference list; p finds q unacceptable otherwise" Commented Sep 27, 2011 at 12:59
• Oh, I'm sorry. I missed the statements. Going back to your original question, [1] says that the problem is NP-hard, and [2] says that there exists an algorithm that finds a feasible solution (not optimal solution in terms of the maximization problem). You can find the statement "However, the weakly stable matchings in I may be of different cardinality, and each of the problems of finding the maximum or minimum size of weakly stable matching in an HRT instance is NP-hard..." in [2]. So there is no conflict. Commented Sep 27, 2011 at 13:50
• [1] however , contains a proof that finding a feasible solution is NP-hard, if I understand correctly and not about finding a solution of maximal size, so still I don't get why there is no conflict. Commented Sep 27, 2011 at 14:02

Problem solved.

The authors of [1] consider a matching when incomplete lists are allowed to be an one-to-one mapping between all the men and all the women. So what is proved in [1] is not the NP-hardness of finding a feasible solution nor the NP-hardness of finding a maximal solution but rather the NP-harness of finding a solution of size n where n is the size of the instance. The problem of finding a maximal solution is showed to be NP-hard by the same authors in [4]. So finally there is no conflict between [1] and [2].

• That's so true. Commented Sep 28, 2011 at 15:56
• It is yes. Thank you for helping me unravel this snowie. Commented Sep 28, 2011 at 16:34