Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Max Bisection problem is to partition the set of nodes into two equal size sets such that the number of crossing edges is maximized. Max Bisection is $NP$-complete on cubic graphs and also on planar graphs.

What is the complexity of Max Bisection on cubic planar graphs? Is it $NP$-complete?

Cross posted on SE tcs

share|improve this question
add comment

2 Answers

I am pretty sure that the result in http://rutcor.rutgers.edu/pub/rrr/reports2006/23_2006.pdf tells us that Max-Bisection is NP-hard on bounded degree planar graphs (however, I think the bound is bigger than three) -- you would have to chase down their construction to be sure.

share|improve this answer
add comment

Max-Cut, at least, in cubic graphs is NP-hard even to approximate to some factor .997. This is due to Berman and Karpinski, 1999:

On some tighter inapproximability results. In Proceedings of the 26th International Colloquium on Automata, Languages and Programming, Prague, Czech Republic, pages 200–209, 1999.

I wouldn't doubt it if the optimal cut is a bisection in the "yes" case of the reduction.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.