The Maximum Graph Cut Problem

Description:

The Max Cut problem is a classified NP-hard optimization problem. It can be defined as:

Input:
-Undirected and unweighted graph G=(V,E).

Output:
-A partition of V into disjoint sets {V1,V2}

Question

Given a graph G, find the partition of his vertexs in two groups {V1,V2} that maximizes the cardinality of the cut, i.e., the number of edges with one end point in V1 and one endpoint in V2.

Problem Instances

In order to define an instance of this problem we need to provide all the information about the Graph. This means: his Vertex Set and the associated Edge Set between pairs of vertexs. The edges are unweighted.

Related Bibliography and Papers