Spectral partitioning of random graphs
Author:
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 529-537
Abstract
Problems such as bisection, graph coloring, and clique are generally believed hard in the worst case. However, they can be solved if the input data is drawn randomly from a distribution over graphs containing acceptable solutions. In this paper we show that a simple spectral algorithm can solve all three problems above in the average case, as well as a more general problem of partitioning graphs based on edge density. In nearly all cases our approach meets or exceeds previous parameters, while introducing substantial generality. We apply spectral techniques, using foremost the observation that in all of these problems, the expected adjacency matrix is a low rank matrix wherein the structure of the solution is evident.Keywords
This publication has 15 references indexed in Scilit:
- Simulated annealing for graph bisection2002
- On clusterings-good, bad and spectral2002
- Fast computation of low rank matrix approximations2001
- Algorithms for graph partitioning on the planted partition modelRandom Structures & Algorithms, 2001
- Algorithms for Graph Partitioning on the Planted Partition Model1999
- A Spectral Technique for Coloring Random 3-Colorable GraphsSIAM Journal on Computing, 1997
- Coloring Random and Semi-Random k-Colorable GraphsJournal of Algorithms, 1995
- Almost all k-colorable graphs are easy to colorJournal of Algorithms, 1988
- Expected behavior of graph coloring algorithmsLecture Notes in Computer Science, 1977
- The Rotation of Eigenvectors by a Perturbation. IIISIAM Journal on Numerical Analysis, 1970