1
$\begingroup$

MAXCUT is NPC but is known to be polynomial for, say, planar graphs. Are there any other graph families where it is known MAXCUT is polynomial? (Please don't say "bipartite graphs" :) )

Improve this question
$\endgroup$
1
  • $\begingroup$ Weakly bipartite graphs ;-) (see Grötschel 81, and Guenin 01 for a characterization). $\endgroup$
    – Nathan Lindzey
    Feb 21, 2019 at 8:40

1 Answer 1

Reset to default
5
$\begingroup$

On the complexity of the maximum cut problem (2005)

The complexity of the SIMPLE MAXCUT problem (MAX CUT with all edge weights equal to unity) is investigated for several special classes of graphs. It is shown that this problem is NP-complete when restricted to one of the following classes: chordal graphs, undirected path graphs, split graphs, tripartite graphs, and graphs that are the complement of a bipartite graph. The problem can be solved in polynomial time, when restricted to graphs with bounded treewidth, or cographs. We also give large classes of graphs that can be seen as generalizations of classes of graphs with bounded treewidth and of the class of the cographs, and allow polynomial time algorithms for the SIMPLE MAX CUT problem.

Improve this answer
$\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.