Welcome to MathOverflow

Question

1

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

edited Jan 20 2011 at 5:44

asked Jan 20 2011 at 5:30

Mohammad Al-Turkistany
267●1●8

Igor Rivin · Answer 1 · 2011-01-21 01:57:56Z UTC

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.

Ryan O'Donnell · Answer 2 · 2011-01-21 10:23:21Z UTC

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.

Complexity of Max Bisection on cubic planar graphs?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.