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.