Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-116 | 19th July 2006 00:00

Graph partitioning via adaptive spectral techniques


Authors: Amin Coja-Oghlan
Publication: 8th September 2006 11:45
Downloads: 2035


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'' E=(E_vw)_{v,w in V} such that for v in V_i and w in V_j the entry E_{vw} 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 (almost) be recovered in polynomial time via spectral methods, provided (essentially) that E approximates the adjacency matrix of G sufficiently well. This result in particular applies to sparse graphs with bounded average degree as n=#V tends to infinity, and it yields interesting consequences on partitioning random graphs.

ISSN 1433-8092 | Imprint