Complexity of Max Bisection on cubic planar graphs? - MathOverflow most recent 30 from http://mathoverflow.net2013-05-23T02:33:23Zhttp://mathoverflow.net/feeds/question/52583http://www.creativecommons.org/licenses/by-nc/2.5/rdfhttp://mathoverflow.net/questions/52583/complexity-of-max-bisection-on-cubic-planar-graphsComplexity of Max Bisection on cubic planar graphs?Mohammad Al-Turkistany2011-01-20T05:30:33Z2011-04-15T14:22:14Z
<p>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.</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="http://cstheory.stackexchange.com/questions/4323/complexity-of-max-bisection-on-cubic-planar-graphs" rel="nofollow">SE tcs</a>
<a href="http://cstheory.stackexchange.com/questions/4323/complexity-of-max-bisection-on-cubic-planar-graphs" rel="nofollow"></a></p>
http://mathoverflow.net/questions/52583/complexity-of-max-bisection-on-cubic-planar-graphs/52706#52706Answer by Igor Rivin for Complexity of Max Bisection on cubic planar graphs?Igor Rivin2011-01-21T01:57:56Z2011-01-21T01:57:56Z<p>I am pretty sure that the result in
<a href="http://rutcor.rutgers.edu/pub/rrr/reports2006/23_2006.pdf" rel="nofollow">http://rutcor.rutgers.edu/pub/rrr/reports2006/23_2006.pdf</a>
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.</p>
http://mathoverflow.net/questions/52583/complexity-of-max-bisection-on-cubic-planar-graphs/52757#52757Answer by Ryan O'Donnell for Complexity of Max Bisection on cubic planar graphs?Ryan O'Donnell2011-01-21T10:23:21Z2011-01-21T10:23:21Z<p>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:</p>
<p>On some tighter inapproximability results. In Proceedings of the 26th International Colloquium on Automata, Languages and Programming, Prague, Czech Republic, pages 200–209, 1999.</p>
<p>I wouldn't doubt it if the optimal cut is a bisection in the "yes" case of the reduction.</p>