License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.131
URN: urn:nbn:de:0030-drops-62675
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6267/
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 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 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(log k) distortion and O(k^2) non-terminals, and any planar graph admits a minor with
1 + epsilon distortion and ~O((k/epsilon)^2) non-terminals.
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:1--131:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6267},
URN = {urn:nbn:de:0030-drops-62675},
doi = {10.4230/LIPIcs.ICALP.2016.131},
annote = {Keywords: Distance Approximating Minor, Graph Minor, Graph Compression, Vertex Sparsification, Metric Embedding}
}
|
Keywords: |
|
Distance Approximating Minor, Graph Minor, Graph Compression, Vertex Sparsification, Metric Embedding |
|
Collection: |
|
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
23.08.2016 |
