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?
1 Answer
$\begingroup$
$\endgroup$
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) for details.
