Graph Minors for Preserving Terminal Distances Approximately

Speaker:        Yun Kuen Cheung
                University of Vienna

Title:          "Graph Minors for Preserving Terminal Distances
                 Approximately"

Date:           Monday, 4 July 2016

Time:           11:00am - 12 noon

Venue:          Room 3501 (via lifts 25/26), HKUST

Abstract:

We are interested in compressing a graph using minor operations, so as to
preserve the distances among a small set of vertices (called terminals)
approximately.

This problem is readily motivated since the compressed graph can be used
as a preprocessing step for algorithms; minor operations are used since
they preserve certain graph properties (e.g., planarity).

More precisely, given a graph where vertices are partitioned into k
terminals and non-terminals, the goal is to compress the graph (i.e.,
reduce the number of non-terminals) using minor operations while
preserving terminal distances approximately. The distortion of a
compressed graph is the maximum multiplicative blow-up of distances
between all pairs of terminals. We study the trade-off between the number
of non-terminals and the distortion. This problem generalizes the Steiner
Point Removal (SPR) problem, in which all non-terminals must be removed.


We introduce a novel black-box reduction to convert any lower bound on
distortion for the SPR problem into a super-linear lower bound on the
number of non-terminals, with the same distortion, for our problem. This
allows us to show that there exist graphs such that every minor with
distortion less than 2 / 2.5/ 3 must have \Omega(k^2) / \Omega(k^{5/4}) /
\Omega(k^{6/5}) non-terminals, plus more trade-offs in between. The
black-box reduction has an interesting consequence: if the tight lower
bound on distortion for the SPR problem is super-constant, then allowing
any linear (in k) non-terminals will not help improving the lower bound to
a constant.

We also build on the existing results on spanners, distance oracles and
connected 0-extensions to show a number of upper bounds for general
graphs, planar graphs, graphs that exclude a fixed minor and bounded
treewidth graphs. Among others, we show that any graph admits a minor with
O(log k) distortion and O(k^2) non-terminals, and any planar graph admits
a minor with (1+epsilon) distortion and O(k^2 log^2 k / epsilon^2)
non-terminals.

This is joint work with Gramoz Goranci and Monika Henzinger; it will
appear in ICALP 2016.


********************
Biography:

Yun Kuen Cheung received his MPhil (Mathematics) from the Hong Kong
University of Science and Technology. He then received PhD (Computer
Science) from New York University, working generally on Theoretical
Computer Science, with focus on problems in Algorithmic Game Theory and
Equilibrium Computation. He is now a postdoctoral researcher in University
of Vienna, where he also works on problems about Graph Sparsification. He
will move to Max Planck Institute for Informatics in September 2016.