Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems
Dan Spielman, MIT
Friday, March 25th, 2005, 4:30 pm
Newell Simon Hall 3305

In our effort to develop new algorithms for solving linear systems, we have been inspired to invent some novel graph algorithms. These include algorithms for finding clusters in graphs, partitioning graphs, and finding sparse approximations of graphs. In this talk I will survey these algorithms and explain some of their more interesting consequences.

Our algorithm for finding clusters in graphs solves the following problem: given a graph that contains a cluster, and given a vertex in the interior of that cluster, find a cluster containing that vertex. The novelty of the algorithm is that its running time is proportional to the size of the cluster it outputs, and consequently it does not need to look at the whole graph.Using this clustering algorithm, we develop the first nearly-linear time algorithm for partitioning graphs that finds sparse cuts of nearly optimal balance.

We then turn our attention to graph sparsification. After defining what it means for one graph to approximate another, we will show how to use our graph partitioning algorithm, along with random sampling, to approximate any graph by a sparse subgraph. Finally, we will explain how these algorithms can be used to solve symmetric diagonally-dominant linear systems in nearly-linear time.

Joint work with Shang-Hua Teng.