The minimum bisection problem is to partition the vertices of a graph into two classes of equal size so as to minimize the number of crossing edges. The problem is NP-hard in the worst case. In this paper we analyze a spectral heuristic for the minimum bisection problem on random graphs Gn(p,p'), which are made up as follows. Partition n vertices into two classes of equal size randomly, and then insert edges inside the two classes with probability p' and edges crossing the partition with probability p independently. If n(p'-p) ≥ c0√np'In(np') for a certain constant c0 0, then with probability 1 - 0(1) as n ← ∞ the heuristic finds a minimum bisection of Gn(p,p') along with a certificate of optimality in polynomial time. Furthermore, we observe that the structure of the set of all minimum bisections of Gn(p,p') undergoes a phase transition as n(p' - p) = Θ(√np' In n). The heuristic solves instances in the subcritical, the critical, and the supercritical phase of the phase transition optimally with probability 1-o(1). These results extend the work of Boppana [5].
展开▼
机译：最小二等分问题是将图的顶点划分为大小相等的两类，以最大程度地减少交叉边的数量。在最坏的情况下，问题是NP困难的。在本文中，我们分析了由随机图 G n （ p，p'）构成的最小二分问题的频谱启发法如下。将 n 个顶点随机分为两个大小相等的类别，然后以概率 p'将边缘插入两类顶点，并以概率 p 插入穿过该划分的边缘我>独立。如果 n （ p'-p ）≥ c 0 √ np 'In （ np'）对于某个常数 c 0 > 0，则概率为1- 0 （1）当 n ←∞时，启发式算法找到 G n （ p，p'）的最小二等分多项式时间最优性证明。此外，我们观察到 G n （ p，p'）的所有最小二等分集合的结构经历了相变，因为< I> n （ p'-p ）=Θ（√ np'在 n 中）。启发式算法以概率1 o （1）最优地解决了相变的亚临界，临界和超临界相中的实例。这些结果扩展了Boppana的工作[5]。
展开▼
