Finding the maximum cut of a graph is a difficult to compute problem in combinatorial optimization with several applications in the world of engineering and physics. This research develops and evaluates an exact branch and bound algorithm for the maximum cut of unweighted graphs that is designed for improved performance on sparse graphs.

The module provides a general overview of the problem along with necessary mathematical background in "The Maxcut Problem" and a brief note on various approaches to the problem in "Several Algorithms". "A New Algorithm" describes a new algorithm for finding maximum cuts. Results of empirical performance evaluation appear in "Empirical Testing", which "Conclusion" further discusses.

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.

Figure 2: Two example graphs appear above.

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₁ 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₁. An example of an edge induced subgraph is shown in Figure 3.

Figure 3: The subgraph induced by the red colored edges is shown on the right.

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.

Figure 4: In the above bipartite graph, the vertices are colored red or blue to highlight the vertex partitions.

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.

Figure 5: The closed curve represented by the dotted line crossing the graph corresponds to a cut of the graph.

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.

Figure 6: The partitions of graph vertices that correspond to this cut are highlighted in red and blue.

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.

Figure 7: Maximum cuts for the two example graphs are shown above.

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.

Figure 8: The complement of the minimum set (red) of edges intersecting all odd cycles of a graph is the maximum cut set.

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

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(|E|2|V|)O(|E|2|V|), 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.

Several researchers have published algorithms that attempt to improve performance, especially focusing on sparse graphs. Notable approaches include those of Wheeler with O*(2|V|)O*(2|V|)[6], Fedin and Kulikov with O*(2|E|/4)O*(2|E|/4)[3], Croce, Kaminski, and Paschos with O*(2|V||E|/|V|+|E|)O*(2|V||E|/|V|+|E|), and Williams with O*(2ω|V|/3)O*(2ω|V|/3), ω<2.376ω<2.376[2]. Although the last algorithm has the best computational complexity, it requires exponential space while the others require only polynomial bounded space. Due to limited memory storage capacity, algorithms requiring only polynomial bounded space are highly preferable.

In attempt to improve performance for sparse graphs, this research presents a new exact algorithm for finding maximum cuts of unweighted graphs that will now be described. It requires polynomial bounded space and has computational complexity O(|E|2|E|)O(|E|2|E|). The general approach that this algorithm takes is to separate the graph into its connected components and calculate initial upper and lower bounds for the maximum cut of each connected component. Those initial bounds are then used with a branch and bound algorithm to find a maximum cut of each connected component, and the maximum cuts of the connected components are be combined to find the maximum cut of the original graph.

In order to accomplish this, let I be the set of edge induced subgraphs of graph G(V,E)G(V,E). Let E be indexed by Z[1,|E|]Z[1,|E|] according to some ordering. Let I be indexed by Z[0,2|E|-1]Z[0,2|E|-1] according to the bijective function f:Z[0,2|E|-1]→If:Z[0,2|E|-1]→I such that

This indexing provides the advantage that the size of each element is the number of zeros in the binary representation of the index. Thus, it enables the use of the edge and graph indices to rapidly eliminate subgraphs that cannot be bipartite and surpass the current lower bound for the maximum cut.

Within this framework, the algorithm searches for the lowest indexed element of I that is bipartite and larger than the current lower bound by iterating over the edges in order, adding each edge to the cut set if it passes a parity check and stopping when the final edge is reached or the number of edges not cut ensures the result will not exceed the lower bound. If such an element is found, the size of the graph is a new lower bound for the maximum cut, and the search continues by removing last cut edge with at least one vertex not colored by a lesser indexed edge before last two edges not in cut set. Continue iterating from that edge if such an edge is found, but terminate if no such edge exists or a cut equal to the upper bound is reached. Otherwise, the search ends and the final lower bound is the size of the maximum cut.

This process can be visualized as a directed graph, like those in Figure 9, Figure 10, and Figure 11, where each step represents a decision whether to include an edge in the cut set. A movement directly downward from a node indicates that the corresponding edge is not cut, while a movement diagonally downward indicates that the corresponding edge is cut. Each path from the top node to one of the bottom nodes corresponds to an edge induced subgraph of the graph being examined. The number of the final node reached (from left to right starting with 0) is the number of edges included. The algorithm seeks to find a path corresponding to a bipartite subgraph that leads farthest to the right. The red line to the left represents the lower bound, and all nodes below this line cannot be part of a path that leads farther right than the lower bound. The red line to the right represents the upper bound, and all nodes to the right of this line can only be a part of paths that exceed the upper bound. Therefore these regions need not be explored. An illustrative example, corresponding to an instance of K₄ with an edge ordering conductive to demonstration where a lower bound of 2 and an upper bound of 4 have been initially calculated (poor lower bound chosen for purpose of demonstration), is shown in Figure 9, Figure 10, and Figure 11.

Figure 9: This image illustrates the process for a K₄ (with poorly estimated lower bound for purposes of demonstration). Each step represents a decision on including the corresponding edge. Each path from top to bottom, like that in blue, corresponds to an edge induced subgraph. The red lines correspond to upper and lower bounds.

Figure 10: The algorithm searches for paths that lead further to the right than previously found. There is no need to search in regions beyond the red lines indicating bounds, which have been updated from the initial lower bound after finding a larger solution in the previous figure.

Figure 11: Finally, a solution leading further right is found. Because this solution is of equal size to the upper bound, the search ends since there cannot be a larger cut.

This new algorithm was compared to the exhaustive algorithm for performance in empirical testing as shown in Figure 12. The image shows a plot of average runtime for graphs with |V|=20|V|=20 nodes and numbers of edges between 0 and 3|V|=603|V|=60. Each data point for each algorithm is the average of runtimes for five randomly generated graphs with the same number of vertices. In the testing, the new algorithm outperformed the exhaustive algorithm at low densities about until |E|<2.5|V||E|<2.5|V|, successfully improving performance over the exhaustive algorithm at sufficiently low densities. However, no comparison to other algorithms developed by other researchers has been performed, and the algorithm is not expected to match or improve upon their performance.

Figure 12: This image shows a plot of average runtime for graphs with |V|=20|V|=20 nodes and numbers of edges between 0 and 3|V|=603|V|=60. Each data point for each algorithm is the average of runtimes for five randomly generated graphs with the same number of vertices.

Finding the maximum cut of a graph is a difficult to compute problem in combinatorial optimization with several applications in the world of engineering and physics. This research develops and evaluates an exact branch and bound algorithm for the maximum cut of unweighted graphs that was designed for improved performance on sparse graphs. Although the algorithm developed provides a performance improvement over the exhaustive algorithm, it is not expected to perform as well or better than other algorithms developed by other researchers. Thus, further improvement of the algorithm, focusing on investigating the effect of edge orderings on the performance of the algorithm and finding additional measures to reduce the number of edge induced subgraphs traversed by the algorithm, and more extensive empirical evaluation are necessary.