The Taub Faculty of Computer Science Events and Talks

A fundamental problem in dynamic graphs is the recovery of structural information in a network whose edges occasionally fail. In a failure event, some subset of edges D are deleted and we want to quickly understand the structure of the surviving network G \ D. In particular, I will discuss the problem of quickly recovering shortest paths and a minimum spanning tree in G \ D.

Let G = (V,E) be a directed edge-weighted graph and let P be a shortest path from s to t in G. The "replacement paths" problem asks to compute, for every edge e on P, the shortest s-to-t path that avoids e. Apart from approximation algorithms and algorithms for special graph classes, the naive solution to this problem -- removing each edge e on P one at a time and computing the shortest s-to-t path each time -- was surprisingly the only known solution for directed weighted graphs, even when the weights are integrals. In particular, although the related shortest paths problem has benefited from fast matrix multiplication, the replacement paths problem has not, and still required cubic time.

For an n-vertex graph with integral edge-lengths in {-M,...,M}, I will describe an O(Mn^{2.584}) time algorithm that uses fast matrix multiplication and is sub-cubic for appropriate values of M. We also show how to construct a "distance sensitivity oracle" in the same time bounds. A query (u,v,e) to this oracle requires sub-quadratic time and returns the length of the shortest u-to-v path that avoids the edge e. Our results also apply for avoiding multiple edges and for avoiding vertices rather than edges.

The talk is based on a FOCS'10 paper with Raphael Yuster. If time permits, I will also discuss a new result with Shiri Chechick and David Peleg for maintaining a minimum spanning tree of a graph subject to edge failures.