---
_id: '11836'
abstract:
- lang: eng
  text: "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.\r\n\r\nWe 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.\r\n\r\nWe 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\r\n1 + epsilon distortion and ~O((k/epsilon)^2) non-terminals."
alternative_title:
- LIPIcs
article_number: '131'
article_processing_charge: No
arxiv: 1
author:
- first_name: Yun Kuen
  full_name: Cheung, Yun Kuen
  last_name: Cheung
- first_name: Gramoz
  full_name: Goranci, Gramoz
  last_name: Goranci
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: 'Cheung YK, Goranci G, Henzinger MH. Graph minors for preserving terminal distances
    approximately - lower and upper bounds. In: <i>43rd International Colloquium on
    Automata, Languages, and Programming</i>. Vol 55. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2016. doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2016.131">10.4230/LIPICS.ICALP.2016.131</a>'
  apa: 'Cheung, Y. K., Goranci, G., &#38; Henzinger, M. H. (2016). Graph minors for
    preserving terminal distances approximately - lower and upper bounds. In <i>43rd
    International Colloquium on Automata, Languages, and Programming</i> (Vol. 55).
    Rome, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.ICALP.2016.131">https://doi.org/10.4230/LIPICS.ICALP.2016.131</a>'
  chicago: Cheung, Yun Kuen, Gramoz Goranci, and Monika H Henzinger. “Graph Minors
    for Preserving Terminal Distances Approximately - Lower and Upper Bounds.” In
    <i>43rd International Colloquium on Automata, Languages, and Programming</i>,
    Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. <a href="https://doi.org/10.4230/LIPICS.ICALP.2016.131">https://doi.org/10.4230/LIPICS.ICALP.2016.131</a>.
  ieee: Y. K. Cheung, G. Goranci, and M. H. Henzinger, “Graph minors for preserving
    terminal distances approximately - lower and upper bounds,” in <i>43rd International
    Colloquium on Automata, Languages, and Programming</i>, Rome, Italy, 2016, vol.
    55.
  ista: 'Cheung YK, Goranci G, Henzinger MH. 2016. Graph minors for preserving terminal
    distances approximately - lower and upper bounds. 43rd International Colloquium
    on Automata, Languages, and Programming. ICALP: International Colloquium on Automata,
    Languages, and Programming, LIPIcs, vol. 55, 131.'
  mla: Cheung, Yun Kuen, et al. “Graph Minors for Preserving Terminal Distances Approximately
    - Lower and Upper Bounds.” <i>43rd International Colloquium on Automata, Languages,
    and Programming</i>, vol. 55, 131, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2016, doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2016.131">10.4230/LIPICS.ICALP.2016.131</a>.
  short: Y.K. Cheung, G. Goranci, M.H. Henzinger, in:, 43rd International Colloquium
    on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2016.
conference:
  end_date: 2016-07-15
  location: Rome, Italy
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 2016-07-12
date_created: 2022-08-12T11:16:01Z
date_published: 2016-08-23T00:00:00Z
date_updated: 2023-02-16T12:09:54Z
day: '23'
doi: 10.4230/LIPICS.ICALP.2016.131
extern: '1'
external_id:
  arxiv:
  - '1604.08342'
intvolume: '        55'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPICS.ICALP.2016.131
month: '08'
oa: 1
oa_version: Published Version
publication: 43rd International Colloquium on Automata, Languages, and Programming
publication_identifier:
  isbn:
  - 978-3-95977-013-2
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Graph minors for preserving terminal distances approximately - lower and upper
  bounds
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 55
year: '2016'
...