<p>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.</p>

<blockquote>
  <p>What is the complexity of Max Bisection on cubic planar graphs? Is it $NP$-complete?</p>
</blockquote>

<p>Cross posted on <a href="https://mathoverflow.net/questions/52583/complexity-of-max-bisection-on-cubic-planar-graphs">mathOverflow</a></p>

CC BY-SA 2.5
2011-01-15T04:01:25.477Z
By "crossing edges" do you mean the edges whose endpoints are in both sets making up the bisection?
Joseph Malkevitch
CC BY-SA 2.5
2011-01-15T08:23:07.463Z
Max Bisection is MAX CUT with additional requirement that the two node sets have the same cardinality.
Mohammad Al-Turkistany
<cc.complexity-theory><max-cut>
Complexity of Max Bisection on cubic planar graphs?
Mohammad Al-Turkistany
# Complexity of Max Bisection on cubic planar graphs?

(Asked by: username_0 on 2011-01-14)

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](https://mathoverflow.net/questions/52583/complexity-of-max-bisection-on-cubic-planar-graphs)

**Tags:** cc.complexity-theory, max-cut

> **Comments:**
> **username_1**: By "crossing edges" do you mean the edges whose endpoints are in both sets making up the bisection?  
> **username_0**: Max Bisection is MAX CUT with additional requirement that the two node sets have the same cardinality.  

---

## 0 answers

