Before discussing the maxcut problem, it is necessary to provide some background information regarding relevant concepts in graph theory, the most fundamental of which is the graph itself. A graph G(V,E)G(V,E) is an ordered pair comprised of a set of vertices *V* and a set of edges *E* that connect pairs of distinct vertices in *V*. Two examples are shown in Figure 2. Graphs may be either weighted, in which a real value is assigned to each edge, or unweighted, in which all edges have equal value. Although the former is more broadly applicable, further discussion will focus almost exclusively on the latter.

Unsurprisingly, a subgraph G1(V1,E1)G1(V1,E1) of graph G(V,E)G(V,E) is a graph with vertex set V1⊆VV1⊆V and edge set E1⊆EE1⊆E. Of particular usefulness will be the subgraph of G(V,E)G(V,E) induced by a given set of edges E1⊆EE1⊆E, known as edge induced subgraph, which consists of that given set of edges *E*_{1} along with all vertices V1=v|(u,v)∈E1,u∈VV1=v|(u,v)∈E1,u∈V that occur as an endpoint of at least one edge in *E*_{1}. An example of an edge induced subgraph is shown in Figure 3.

One class of graphs that will be especially important to discussion of the maxcut problem is bipartite graphs. A graph G(V,E)G(V,E) is bipartite, like the example in Figure 4, if there are sets V1,V2⊆VV1,V2⊆V such that V1∪V2=VV1∪V2=V, V1∩V2=∅V1∩V2=∅, and (u,v)∈E(u,v)∈E only if u∈V1,v∈V2u∈V1,v∈V2 or v∈V1,u∈V2v∈V1,u∈V2. Additionally, a graph is bipartite if and only if it has no subgraph that is a cycle of odd length.

A cut of a graph can be informally understood and visualized as a closed curve crossing some realization of the graph where each edge can be crossed at most once, as seen in Figure 5. Notice that the curve partitions the graph vertices into two disjoint subsets located to each side of the curve.

Formally, a cut of a graph G(V,E)G(V,E) is a partition of the graph vertices into subsets V1,V2⊆VV1,V2⊆V such that V1∪V2=VV1∪V2=V and V1∩V2=∅V1∩V2=∅, as demonstrated by Figure 6. The corresponding cut set is the set of edges *C* such that C=(u,v)∈E|u∈V1,v∈V2C=(u,v)∈E|u∈V1,v∈V2. Hence, the cut set induces a bipartite subgraph.

The size of a cut equals the sum of the weights of edges in the cut set, which in the case of unweighted graphs is simply the number of edges in the cut set. With this definition of size, the maximum cut of a graph, like those shown in Figure 7, is a cut not smaller than any other cut in the graph, and it corresponds to the largest bipartite subgraph of the graph. The maximum cut of a graph is not necessarily unique and is not unique in either of the examples.

Alternatively, the problem can be formulated in terms of the edges in the complement of the cut set. The complement of a set of edges that intersects every odd cycle in a graph induces a graph with no subgraphs that are odd cycles, which is therefore a bipartite graph. Thus, the complement of the minimum set of edges intersecting every odd cycle induces the largest bipartite subgraph of the graph and hence is the maximum cut set, as illustrated in Figure 8.

Finding the maximum cut of a graph was one of the earliest problems proven to be np-complete, which, ignoring the formal details of what that means, indicates that no currently known algorithms terminate in a polynomial bounded number of operations in all cases [5]. There are, however, several types of graphs for which polynomial bounded solutions are known, such as graphs embeddable on the plane [2]. Since computing the maxcut of large graphs often requires extremely long lengths of time, randomized *ρ*-approximation algorithms, such as that of Goemans and Williamson, may be employed for situations in which optimality is not required and a good estimate will suffice [4].

Applications of the maxcut problem include minimization of number of holes on circuit boards or number of chip contacts in VLSI circuit layout design, energy minimization problems in computer vision programs, and modeling of the interactions of spin glasses with magnetic fields in statistical physics [1].