most recent 30 from http://mathoverflow.net 2013-05-22T08:04:04Z http://mathoverflow.net/feeds/question/80532 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80532/maximum-graph-cut-in-directed-planar-graphs Evgeniy 2011-11-09T23:19:38Z 2012-02-16T05:22:12Z

<p>Maxcuts are known to be NP-hard. Maxcuts in undirected planar graphs are known to be P.</p> <p>I think I've seen somewhere an approximate solution to maxcuts in directed planar graphs but I've never heard of an exact algorithm. And I've never seen the answear if it is NP or not.</p> <p>So is this problem solvable in polynomial time?</p>

http://mathoverflow.net/questions/80532/maximum-graph-cut-in-directed-planar-graphs/80534#80534 Michael Biro 2011-11-09T23:44:25Z 2011-11-09T23:44:25Z

<p>This paper <a href="http://web.cs.gc.cuny.edu/~mlampis/papers/dtreewidthDO.pdf" rel="nofollow">http://web.cs.gc.cuny.edu/~mlampis/papers/dtreewidthDO.pdf</a> proves MAX DICUT hard for DAGs, among other things. Not quite what you're looking for, but support for the idea that it's hard.</p>