<p>Problem solved.</p>

<p>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]. </p>

CC BY-SA 3.0
2011-09-28T15:56:53.320Z
That's so true.
Snowie
CC BY-SA 3.0
2011-09-28T16:34:59.867Z
It is yes. Thank you for helping me unravel this snowie.
gstat
CC BY-SA 3.0
2011-09-28T11:55:17.783Z
2011-09-28T11:55:17.783Z
gstat
<p>The stable marriage instance with ties is solvable in polynomial time, whereas the stable marriage instance with <strong><em>incomplete lists</em></strong> and ties is NP-hard.</p>

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

CC BY-SA 3.0
2011-09-27T09:19:05.257Z
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].
gstat
CC BY-SA 3.0
2011-09-27T12:39:15.860Z
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.
Snowie
CC BY-SA 3.0
2011-09-27T12:59:24.010Z
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"
gstat
CC BY-SA 3.0
2011-09-27T13:50:10.747Z
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.
Snowie
CC BY-SA 3.0
2011-09-27T14:02:15.313Z
[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.
gstat
CC BY-SA 3.0
2011-09-27T15:50:04.733Z
[1] says that the maximization problem is NP-hard.  Actually there are many polynomial time algorithms that finds a feasible solution for the stable marriage with ties and incomplete list.  An example is the polynomial time approximation algorithm: Zoltán Király, "Better and Simpler Approximation Algorithms for the Stable Marriage Problem," ESA 2008.
Snowie
CC BY-SA 3.0
2011-09-27T18:33:34.563Z
I don't think what you say is true. I quote [1]: We focus on the three possible relaxations
concerning these two restrictions. All these problems (including the original one)
ask if there exists a stable matching. The first three problems are known to be in
P [2,4]. Our main result is the NP-completeness of the last one, shown in Sec.3.
SMP-CLTO:stable marriage problem with complete list and total order
SMP-ILTO:stable marriage problem with incomplete list and total order.
SMP-CLT:stable marriage problem with complete list and ties
SMP-ILT:stable marriage problem with incomplete list and ties
gstat
CC BY-SA 3.0
2011-09-27T18:46:13.463Z
I quote also [3]: "Variants of this problem have been studied by Gusfield
and Irving [6] amongst others, including cases where the orderings are over partial lists or contain ties. It is known
that a stable matching can be found in each of these cases individually in polynomial time (Gale and Sotomayor [5],
Gusfield and Irving [6]). However in the case of simultaneous occurrence of incomplete lists and ties, the problem
becomes NP-hard (Iwama et al. [10])"
gstat
CC BY-SA 3.0
2011-09-28T01:17:44.847Z
In general, if someone says "some problem is NP-hard", this actually means finding an *optimal* solution (in terms of maximization or minimization) is NP-hard.  If some problem is really hard to find a *feasible* solution (it rarely happens), we clearly state like "the problem is NP-hard to find a feasible solution."
Snowie
CC BY-SA 3.0
2011-09-28T08:14:54.227Z
If you follow the reduction in section 3.6 of [1] you will see that from an instance of EXACT MAXIMAL MATCHING they create an instance I of SMP-ILT and I quote: "We claim that G has a
maximal matching of size exactly K if and only if I has a stable matching."
gstat
CC BY-SA 3.0
2011-09-28T11:55:01.593Z
I got your point.  Section 3.6 of [1] might be wrong. (Actually I don't think the proof in Section 3.6 is correct.)  You may want to contact the authors of [1].
Snowie
CC BY-SA 3.0
2011-09-27T09:00:39.200Z
2011-09-27T09:00:39.200Z
Snowie
<p>According to [1] finding a weakly stable matching in a stable marriage (or SM) instance with incomplete lists and ties is NP-Hard.</p>

<p>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.</p>

<p>Also HR with ties is a generalization of SM with incomplete lists and ties.</p>

<p>Isn't there a conflict here?</p>

<p>[1] K. Iwama, D. Manlove, S. Miyazaki and Y. Morita. <a href="http://dx.doi.org/10.1007/3-540-48523-6_41" rel="nofollow">Stable Marriage with Incomplete Lists and Ties</a>. Automata, Languages and Programming, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 1999</p>

<p>[2] R. W. Irving, D. F. Manlove, and S. Scott. <a href="http://dx.doi.org/10.1007/3-540-44985-X_24" rel="nofollow">The Hospitals/Residents Problem with Ties</a>. Algorithm Theory - SWAT 2000. Lecture Notes in Computer Science. Springer Berlin / Heidelberg</p>

<p>[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</p>

<p>[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.</p>

<co.combinatorics><np-hardness>
Stable Marriage with incomplete lists and ties - NP-hardness
gstat
# Stable Marriage with incomplete lists and ties - NP-hardness

(Asked by: username_0 on 2011-09-27)

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](http://dx.doi.org/10.1007/3-540-48523-6_41). 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](http://dx.doi.org/10.1007/3-540-44985-X_24). 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.

**Tags:** co.combinatorics, np-hardness


---

## 2 answers

### Answer by username_0 on 2011-09-28. Score: 2 | Accepted answer

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].

> **Comments:**
> **username_1**: That's so true.  
> **username_0**: It is yes. Thank you for helping me unravel this snowie.  

---

### Answer by username_1 on 2011-09-27. Score: 4

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].

> **Comments:**
> **username_0**: 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].  
> **username_1**: 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.  
> **username_0**: 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"  
> **username_1**: 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.  
> **username_0**: [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.  
> **username_1**: [1] says that the maximization problem is NP-hard.  Actually there are many polynomial time algorithms that finds a feasible solution for the stable marriage with ties and incomplete list.  An example is the polynomial time approximation algorithm: Zoltán Király, "Better and Simpler Approximation Algorithms for the Stable Marriage Problem," ESA 2008.  
> **username_0**: I don't think what you say is true. I quote [1]: We focus on the three possible relaxations concerning these two restrictions. All these problems (including the original one) ask if there exists a stable matching. The first three problems are known to be in P [2,4]. Our main result is the NP-completeness of the last one, shown in Sec.3. SMP-CLTO:stable marriage problem with complete list and total order SMP-ILTO:stable marriage problem with incomplete list and total order. SMP-CLT:stable marriage problem with complete list and ties SMP-ILT:stable marriage problem with incomplete list and ties  
> **username_0**: I quote also [3]: "Variants of this problem have been studied by Gusfield and Irving [6] amongst others, including cases where the orderings are over partial lists or contain ties. It is known that a stable matching can be found in each of these cases individually in polynomial time (Gale and Sotomayor [5], Gusfield and Irving [6]). However in the case of simultaneous occurrence of incomplete lists and ties, the problem becomes NP-hard (Iwama et al. [10])"  
> **username_1**: In general, if someone says "some problem is NP-hard", this actually means finding an *optimal* solution (in terms of maximization or minimization) is NP-hard.  If some problem is really hard to find a *feasible* solution (it rarely happens), we clearly state like "the problem is NP-hard to find a feasible solution."  
> **username_0**: If you follow the reduction in section 3.6 of [1] you will see that from an instance of EXACT MAXIMAL MATCHING they create an instance I of SMP-ILT and I quote: "We claim that G has a maximal matching of size exactly K if and only if I has a stable matching."  
> **username_1**: I got your point.  Section 3.6 of [1] might be wrong. (Actually I don't think the proof in Section 3.6 is correct.)  You may want to contact the authors of [1].  

---

