Title: Graph Minors for Preserving Terminal Distances Approximately

Speaker: Yun Kuen Cheung
University of Vienna

Time/Date: Monday, July 4, 11-12

Location: 3501

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.


Bio: 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.