Spectral methods for graph bisection problems

• Published in: Computers & operations research 1998-07, Vol.25 (7-8), p.519-530
• Main Authors: Tu, Chih-Chien, Cheng, Hsuanjen
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; eigenvalue; eigenvector; Exact sciences and technology; Flows in networks. Combinatorial problems; interior point method; Mathematical models; Neighborhoods; Operational research and scientific management; Operational research. Management science; Operations research; Optimization. Search problems; semidefinite programming; Studies; subgradient method
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/S0305-0548(98)00021-5

The decision problem of graph bisection is NP-complete. The authors apply a spectral method to approximate the optimal solution. A neighborhood of the equal-sized bisection problem is studied in this paper. The neighborhood of the equal-sized bisection problem means a problem of finding the optimal bisection among a set of nearby equal-sized bisection problems. Thus, the equal-sized bisection problem is a special case of the neighborhood of the equal-sized bisection problem, i.e. without a neighborhood. Numerical experiments presented in this paper for the Boppana's equal-sized bisection algorithm coincide with theoretical proof that the presented algorithm has a good average case behavior over certain probability distributions on graphs. Our algorithm, without a projection constraint, for the neighborhood of the equal-sized bisection problem is examined with certain graphs. The computational results and complexity of our algorithm, compared with Boppana's algorithm, show that this algorithm is capable of solving the real world large-scale problems. In this paper, we study the spectral methods for graph bisection problems and conclude certain numerical results. Spectral methods contain two topics: eigenvalue bounds for graph bisection width and bisection algorithms with eigenvector space. Two graph bisection problems are mainly investigated: finding the best bisection for the equal-size graph bisection problem and choosing the best bisection among a set of graph bisection problems of specified sizes. To compute the optimal eigenvalue bounds, one needs to solve the eigenvalue optimization problem which minimizes the largest eigenvalue of an affine symmetric matrix function. The eigenvalue optimization problems are convex but usually nonsmooth. Thus, we transform the eigenvalue optimization problems into the semidefinite programming problems. Then we apply primal-dual interior point methods to solve the semidefinite programming problems. Finally, we use an eigenvector corresponding to the largest eigenvalue, which has attained the optimal bound, to bisect the graph into two pieces of specified size. The running time of our algorithm for finding the best bisection among a set of graph bisection problems of specified sizes is O(n3).