Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. 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 maximum. 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 mathOverflow

share|cite|improve this question
By "crossing edges" do you mean the edges whose endpoints are in both sets making up the bisection? – Joseph Malkevitch Jan 15 '11 at 4:01
Max Bisection is MAX CUT with additional requirement that the two node sets have the same cardinality. – Mohammad Al-Turkistany Jan 15 '11 at 8:23

Your Answer


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

Browse other questions tagged or ask your own question.