What is the time and space complexity of the best algorithm to find Max cut of a sparse graph with maximum degree of 2.

Background: We have polynomial time algorithms for 2-SAT but for 3-SAT and above the problem becomes NP complete and no polynomial algorithms exist unless P=NP.

Similarly Max cut is known to be NP hard for graphs with maximum degree 3 or above. What about graphs with max degree 2? Do we have algorithms with polynomial runtimes for them, similar to 2-SAT.

  • $\begingroup$ Is it also from some programming competition? ~_~ $\endgroup$ – KNilesh Sep 11 at 18:19
  • $\begingroup$ No, just wondering if there are ploynomial algorithms for Max cut of graphs with max degree of 2. $\endgroup$ – rajeesh Sep 12 at 10:11

Your Answer

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

Browse other questions tagged or ask your own question.