Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Maxcuts are known to be NP-hard. Maxcuts in undirected planar graphs are known to be 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.

So is this problem solvable in polynomial time?

share|improve this question
add comment

1 Answer

This paper http://web.cs.gc.cuny.edu/~mlampis/papers/dtreewidthDO.pdf 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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