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.
Problems that are easy on bipartite but hard on general graphs
complexity theory;graphs;bipartite matching
There are several well-known NP-complete problems that become solvable in polynomial-time for bipartite graphs. For example, 3-coloring is easy as bipartite graphs are precisely the 2-colorable graphs. Another example is independent set which is made easy by Knig's theorem.Wikipedia also lists a problem that is NP-hard for general graphs but is trivially in P for bipartite graphs: the odd cycle transversal problem.