Complexity of Max Bisection on cubic planar graphs? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T02:33:23Z http://mathoverflow.net/feeds/question/52583 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52583/complexity-of-max-bisection-on-cubic-planar-graphs Complexity of Max Bisection on cubic planar graphs? Mohammad Al-Turkistany 2011-01-20T05:30:33Z 2011-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#52706 Answer by Igor Rivin for Complexity of Max Bisection on cubic planar graphs? Igor Rivin 2011-01-21T01:57:56Z 2011-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#52757 Answer by Ryan O'Donnell for Complexity of Max Bisection on cubic planar graphs? Ryan O'Donnell 2011-01-21T10:23:21Z 2011-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>