1
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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