Zihan Tan, DIMACS

Abstract

We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph G (with edge weights) and a subset of k terminal vertices, the goal is to construct an eps-emulator, which is a small planar graph G’ that contains the terminals and preserves the distances between the terminals up to factor 1 + eps. We construct the first eps-emulators for planar graphs of near-linear size tilde O(k / poly(eps)). In terms of k, this is an improvement over the previous quadratic upper bound of Cheung, Goranci, and Henzinger, and breaks below known quadratic lower bounds for exact emulators (the case when eps = 0). Moreover, our emulators can be computed in (near-)linear time, which leads to fast (1 + eps)- approximation algorithms for basic optimization problems on planar graphs, including multiple-source shortest paths, minimum (s, t)-cut, graph diameter, and offline dynamic distance oracle.

This talk is based on joint work with Hsien-Chih Chang and Robert Krauthgamer.

See: https://theory.cs.rutgers.edu/theory_seminar