Maximum cut

The Maximum Cut (Max Cut) problem is a well-known problem in combinatorial optimization and graph theory. It involves a given undirected graph, where the goal is to partition the set of vertices into two disjoint subsets in such a way that the number of edges between the two subsets is maximized.