From Trees to Cuts: Statistical Insights into Spanning-Tree-Based Max-Cut Algorithms
Ho-Jun Jang, Yong-Hyuk Kim · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2025
We investigate the statistical properties of bases derived from spanning trees in edge-based genetic algorithms for the Max-Cut problem. Edge-based algorithms represent solutions as combinations of basis elements, each formed by removing an edge from a spanning tree. We analyze how the distribution of flip sizes—defined as the number of edges whose cut status changes when a basis element is combined with a candidate solution via XOR (exclusive or) operator—affects algorithm performance. Experiments on graphs using Kruskal-like, depth-first search, and breadth-first search spanning trees show a moderate to strong positive correlation between higher frequencies of small flip sizes and improved solution quality. These results suggest intentionally promoting small flip sizes could enhance the performance of genetic algorithms for the Max-Cut problem.