ECCC-Report TR06-116https://eccc.weizmann.ac.il/report/2006/116Comments and Revisions published for TR06-116en-usFri, 08 Sep 2006 11:45:19 +0300
Paper TR06-116
| Graph partitioning via adaptive spectral techniques |
Amin Coja-Oghlan
https://eccc.weizmann.ac.il/report/2006/116We 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.
Fri, 08 Sep 2006 11:45:19 +0300https://eccc.weizmann.ac.il/report/2006/116