In computer science, the problem of finding the way to partition a network of points (a graph) so that the maximum possible number of edges are crossed by the cut. Many other problems of interest can reformulated as a MaxCut problem. Finding the optimal solution is hard (the problem is known to be NP-complete).