Efficient algorithms for graph sparsification

Abstract: Graphs occur everywhere in discrete mathematics, but also in practical problems in logistics, the internet, social networks, etc. Sparse graphs (i.e., ones with few edges) are easier to handle than dense graphs: they take less space to store and are often cheaper to compute on. A long line of work by Karger, Spielman, Teng, and others resulted in nearly-linear-time algorithms that can sparsify any given n-vertex graph G to another n-vertex graph H whose number of edges is only O(n), while preserving many important properties of G. This then gives nearly-linear-time algorithms for solving various cut problems in graphs, for graph partitioning, and for solving Laplacian linear systems. We will describe these developments, and end with our recent work with Simon Apers showing that *quantum* algorithms can even compute such a good graph sparsification in sublinear time.

Mathematics

Audience: general audience

Heilbronn Annual Conference 2020