@conference{cheung2016graph,
author = "Yun Kuen Cheung and Gramoz Goranci and Monika Henzinger",
abstract = "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.",
booktitle = "ICALP 2016",
keywords = "graph compression;graph minor;metric embedding;minor",
pages = "131",
title = "{G}raph {M}inors for {P}reserving {T}erminal {D}istances {A}pproximately - {L}ower and {U}pper {B}ounds",
url = "http://arxiv.org/abs/1604.08342",
year = "2016",
}