[{"oa_version":"Published Version","article_number":"131","month":"08","publication":"43rd International Colloquium on Automata, Languages, and Programming","conference":{"location":"Rome, Italy","end_date":"2016-07-15","name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"2016-07-12"},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-3-95977-013-2"],"issn":["1868-8969"]},"oa":1,"type":"conference","date_published":"2016-08-23T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPICS.ICALP.2016.131"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2022-08-12T11:16:01Z","article_processing_charge":"No","publication_status":"published","intvolume":"        55","alternative_title":["LIPIcs"],"title":"Graph minors for preserving terminal distances approximately - lower and upper bounds","scopus_import":"1","_id":"11836","author":[{"last_name":"Cheung","first_name":"Yun Kuen","full_name":"Cheung, Yun Kuen"},{"first_name":"Gramoz","last_name":"Goranci","full_name":"Goranci, Gramoz"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","day":"23","arxiv":1,"doi":"10.4230/LIPICS.ICALP.2016.131","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."}],"citation":{"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.","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>.","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>","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>","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."},"year":"2016","date_updated":"2023-02-16T12:09:54Z","external_id":{"arxiv":["1604.08342"]},"volume":55,"extern":"1"}]