A combinatorial algorithm for finding maximum cuts  (Page 2/3)

Formally, a cut of a graph $G(V,E)$ is a partition of the graph vertices into subsets $V_1,V_2\subseteq V$ such that $V_1\cup V_2=V$ and $V_1\cap V_2=\varnothing$ , as demonstrated by [link] . The corresponding cut set is the set of edges C such that $C=\left\{(u,v)\in E|u\in ,V_1,,,v,\in ,V_2\right\}$ . 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 [link] , 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 [link] .

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 [link] . There are, however, several types of graphs for which polynomial bounded solutions are known, such as graphs embeddable on the plane [link] . 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 [link] .

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 [link] .

Several algorithms

The most direct and straightforward way to find maximum cuts of a graph would be to perform an exhaustive search of all bipartitions of the graph vertices. The maximum cut may be found by iterating over all distinct bipartitions of the graph vertices, summing the weights of edges connecting vertices in opposite partitions to calculate the size of the corresponding cut, comparing this value to the largest cut size previously found, and updating the maximum accordingly.

The exhaustive algorithm, which has computational complexity $O\left(\right|E\left|2^{\left|V\right|}\right)$ , examines the same number of bipartitions for a tree, for which the maximum cut always equals the number of edges, as it does for a complete graph on the same number of vertices. Thus, it is clear that the exhaustive algorithm is not completely satisfactory, especially for graphs with few edges relative to other graphs with a given number of vertices.