Cheung, Yun Kuen ;
Goranci, Gramoz ;
Henzinger, Monika
Graph Minors for Preserving Terminal Distances Approximately  Lower and Upper Bounds
Abstract
Given a graph where vertices are partitioned into k terminals and nonterminals, the goal is to compress the graph (i.e., reduce the number of nonterminals) using minor operations while preserving terminal distances approximately. The distortion of a compressed graph is the maximum multiplicative blowup of distances between all pairs of terminals. We study the tradeoff between the number of nonterminals and the distortion. This problem generalizes the Steiner Point Removal (SPR) problem, in which all nonterminals must be removed.
We introduce a novel blackbox reduction to convert any lower bound on distortion for the SPR problem into a superlinear lower bound on the number of nonterminals, 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}) nonterminals, plus more tradeoffs in between. The blackbox reduction has an interesting consequence: if the tight lower bound on distortion for the SPR problem is superconstant, then allowing any O(k) nonterminals will not help improving the lower bound to a constant.
We also build on the existing results on spanners, distance oracles and connected 0extensions 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) nonterminals, and any planar graph admits a minor with
1 + epsilon distortion and ~O((k/epsilon)^2) nonterminals.
BibTeX  Entry
@InProceedings{cheung_et_al:LIPIcs:2016:6267,
author = {Yun Kuen Cheung and Gramoz Goranci and Monika Henzinger},
title = {{Graph Minors for Preserving Terminal Distances Approximately  Lower and Upper Bounds}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {131:1131:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6267},
URN = {urn:nbn:de:0030drops62675},
doi = {10.4230/LIPIcs.ICALP.2016.131},
annote = {Keywords: Distance Approximating Minor, Graph Minor, Graph Compression, Vertex Sparsification, Metric Embedding}
}
23.08.2016
Keywords: 

Distance Approximating Minor, Graph Minor, Graph Compression, Vertex Sparsification, Metric Embedding 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

23.08.2016 