Graph Partitioning via Adaptive Spectral Techniques

Amin Coja-Oghlan

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

In this paper we study the use of spectral techniques for graph partitioning. Let G = (V, E) be a graph whose vertex set has a 'latent' partition V-1, ... , V-k. Moreover, consider a 'density matrix' epsilon = (epsilon(nw))(nw is an element of V) such that, for nu is an element of V-i and w is an element of V-j, the entry epsilon(rw) is the fraction of all possible V-i-V-j-edges that are actually present in G. We show that on input (G,k) the partition V-1, ... ,V-k can (very nearly) be recovered in polynomial time via spectral methods, provided that the following holds: epsilon approximates the adjacency matrix of G in the operator norm, for vertices nu is an element of V-i, w is an element of V-j not equal V-i the corresponding column vectors epsilon(r), epsilon(w) are separated, and G is sufficiently 'regular' with respect to the matrix epsilon. This result in particular applies to sparse graphs with bounded average degree as n = not equal V -> proportional to, and it has various consequences on partitioning random graphs.

Original languageEnglish
Pages (from-to)227-284
Number of pages58
JournalCombinatorics, Probability and Computing
Issue number2
Publication statusPublished - Mar 2010


Dive into the research topics of 'Graph Partitioning via Adaptive Spectral Techniques'. Together they form a unique fingerprint.

Cite this