Fast Tree Approximations of Graphs

EADS Talk by Harald Räcke, Technische Universität München

Abstract

Given a graph G=(V,E,c) with edge capacities, a cut-sparsifier for G is a graph H=(V',E',c') with V⊇V' that approximates the mincuts of G in the following sense. Given any bipartition U,V-U of the vertex set of G the mincut separating U and V-U is approximately (up to a factor of q) the same in G as in H.

This talk focuses on the construction of a sparsifier H for a given undirected graph G that not only obtains a good quality but has the additional property that H is a tree. Such tree approximations of graphs play an important role in the design of oblivious routing strategies and also form the basis for approximation and online algorithms for various cut problems in graphs. We give the first algorithm for constructing such a sparsifier that obtains close to linear running.

Harald Räcke graduated from Paderborn University in 2003 under the supervision of Friedhelm Meyer auf der Heide. After holding Postdoc positions at Carnegie Mellon University, and Toyota Technological Institute at Chicago, he became an Assistant Professor at the University of Warwick. Currently, he is an Associate Professor in the Efficient Algorithms Group at the Technical University Munich.

He shared the Best Paper award at FOCS 2002 and STOC 2008. His main interests include the design and analysis of routing and graph partitioning algorithms, the theory of metric embeddings, and algorithmic game theory.

See the complete presentation here