5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.