1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ What research have you done? If you read the Wikipedia article on bipartite graphs, you will immediately find a description of a problem that is NP-hard for general graphs but is trivially in P for bipartite graphs: en.wikipedia.org/wiki/Bipartite_graph#Odd_cycle_transversal. If your question is answered in the obvious place on Wikipedia, you probably haven't done enough research before asking. $\endgroup$ – D.W.♦ Jun 30 '16 at 8:02
  • 2
    $\begingroup$ I edited the question to tone down irrelevant references to sociological issues that only obscure the CS problem. (FWIW, you seem to still be assuming that everybody has to marry exactly one other person -- how very inclusive of you! ;P) $\endgroup$ – Raphael♦ Jul 6 '16 at 10:21
  • $\begingroup$ @Raphael Thank you, and yes, assuming everyone has to marry exactly one other person was an oversight. $\endgroup$ – Demi Jul 6 '16 at 20:09
  • 1
    $\begingroup$ And we didn't even start with changing relationships over time, or the presumption that everybody (w|c)ould order everybody else linearly by preference! The real world is far too complex to be nailed down by such simplistic models, which is why the "marriage problem" uses the metaphor without any claims to model reality. Which is why your initial post came across as weird: no CSist in their right mind would derive from the presentation of the "marriage problem" that there is only one type of admissible relationship. $\endgroup$ – Raphael♦ Jul 6 '16 at 22:35
7
$\begingroup$

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 König'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.

Improve this answer
$\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.