MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

I am pretty sure that the result in 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|cite|improve this answer

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|cite|improve this answer

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.