Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds

Cheung, Yun Kuen; Goranci, Gramoz; Henzinger, Monika
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 {\$}\backslashOmega(k{\^{}}2){\~{}}/{\~{}}\backslashOmega(k{\^{}}{\{}5/4{\}}){\~{}}/{\~{}}\backslashOmega(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 {\$}O(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(\backslashlog k){\$} distortion and {\$}O(k{\^{}}{\{}2{\}}){\$} non-terminals, and any planar graph admits a minor with {\$}1+\backslashvarepsilon{\$} distortion and {\$}\backslashwidetilde{\{}O{\}}((k/\backslashvarepsilon){\^{}}{\{}2{\}}){\$} non-terminals.
Research areas:
Type of Publication:
In Proceedings
graph compression; graph minor; metric embedding; minor
Book title:
ICALP 2016
Hits: 4296

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information