New Abilities and Limitations of Spectral Graph Bisection

Martin R. Schuster, Maciej Liskiewicz


Spectral based heuristics belong to well-known commonly used methods which determines provably minimal graph bisection or outputs "fail" when the optimality cannot be certified. In this paper we focus on Boppana's algorithm which belongs to one of the most prominent methods of this type. It is well known that the algorithm works well in the random planted bisection model -The standard class of graphs for analysis minimum bisection and relevant problems. In 2001 Feige and Kilian posed the question if Boppana's algorithm works well in the semirandom model by Blum and Spencer. In our paper we answer this question affirmatively. We show also that the algorithm achieves similar performance on graph classes which extend the semirandom model. Since the behavior of Boppana's algorithm on the semirandom graphs remained unknown, Feige and Kilian proposed a new semidefinite programming (SDP) based approach and proved that it works on this model. The relationship between the performance of the SDP based algorithm and Boppana's approach was left as an open problem. In this paper we solve the problem in a complete way by proving that the bisection algorithm of Feige and Kilian provides exactly the same results as Boppana's algorithm. As a consequence we get that Boppana's algorithm achieves the optimal threshold for exact cluster recovery in the stochastic block model. On the other hand we prove some limitations of Boppana's approach: We show that if the density difference on the parameters of the planted bisection model is too small then the algorithm fails with high probability in the model.

Original languageEnglish
Title of host publication25th Annual European Symposium on Algorithms (ESA 2017)
EditorsKirk Pruhs, Christian Sohler
Number of pages66
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date05.01.2017
ISBN (Print)978-3-95977-049-1
Publication statusPublished - 05.01.2017
Event25th Annual European Symposium on Algorithms (ESA 2017)
- Vienna, Austria
Duration: 04.09.201708.09.2017


Dive into the research topics of 'New Abilities and Limitations of Spectral Graph Bisection'. Together they form a unique fingerprint.

Cite this