Are there any problems that are easy for bipartite graphs, but hard for general graphs?
I am asking because some classical problems are formulated in reference to people looking for a spouse, such as the marriage problem (for straight people) and the stable marriage problem (for straight people). Both are in FP.
If one removes the requirement that there are two genders and that every man has to marry exactly one women, the general stable marriage problem (my term) is the same as the stable roommates problem, and a solution is no longer guaranteed to exist. I wonder if there are other problems which are explained using similar metaphors for which there is also an increase in complexity.