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

Several researchers have published algorithms that attempt to improve performance, especially focusing on sparse graphs. Notable approaches include those of Wheeler with $O^{*}\left(2^{\left|V\right|}\right)$ [link] , Fedin and Kulikov with $O^{*}\left(2^{\left|E\right|/4}\right)$ [link] , Croce, Kaminski, and Paschos with $O^{*}\left(2^{\left|V\right|\left|E\right|/\left|V\right|+\left|E\right|}\right)$ , and Williams with $O^{*}\left(2^{\omega \left|V\right|/3}\right)$ , $\omega <2.376$ [link] . 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.

A new algorithm

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\left(\right|E\left|2^{\left|E\right|}\right)$ . 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)$ . Let E be indexed by $\mathbb{Z}[1,|E\left|\right]$ according to some ordering. Let I be indexed by $\mathbb{Z}[0,2^{\left|E\right|}-1]$ according to the bijective function $f:\mathbb{Z}[0,2^{\left|E\right|}-1]\to 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 [link] , [link] , and [link] , 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 [link] , [link] , and [link] .

Empirical testing

This new algorithm was compared to the exhaustive algorithm for performance in empirical testing as shown in [link] . The image shows a plot of average runtime for graphs with $\left|V\right|=20$ nodes and numbers of edges between 0 and $3\left|V\right|=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 $\left|E\right|<2.5\left|V\right|$ , 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.

Conclusion

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.