<p>The stable marriage problem with ties (a matching problem for bipartite graphs) is (trivially) solvable in polynomial time, whereas the stable roommate problem with ties (a matching problem for general graphs) is known to be NP-hard.  See <a href="http://www.sciencedirect.com/science/article/pii/0196677490900072">Eytan Ronn:
NP-Complete Stable Matching Problems. J. Algorithms 11(2): 285-304 (1990)</a> for details.</p>

CC BY-SA 3.0
2015-04-28T13:24:55.330Z
2015-04-28T13:24:55.330Z
Hiroki Yanagisawa
<p>Are there variants of matching problem (decision or optimization problem) that are polynomial time solvable for bipartite graphs but are NP-hard for general graphs?</p>

<graph-algorithms><matching>
Matching problems that are easy for bipartite graphs but hard for general graphs
Hans
# Matching problems that are easy for bipartite graphs but hard for general graphs

(Asked by: username_0 on 2015-04-28)

Are there variants of matching problem (decision or optimization problem) that are polynomial time solvable for bipartite graphs but are NP-hard for general graphs?

**Tags:** graph-algorithms, matching

---

## 1 answers

### Answer by username_1 on 2015-04-28. Score: 6 | Accepted answer

The stable marriage problem with ties (a matching problem for bipartite graphs) is (trivially) solvable in polynomial time, whereas the stable roommate problem with ties (a matching problem for general graphs) is known to be NP-hard. See [Eytan Ronn:
NP-Complete Stable Matching Problems. J. Algorithms 11(2): 285-304 (1990)](http://www.sciencedirect.com/science/article/pii/0196677490900072) for details.


---

