Problem: Maximum cut

Definition:
(decision variant)
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.

Linear

Polynomial

GI-complete

NP-hard

NP-complete

coNP-complete

Open

Unknown to ISGCI