2026-08-17T08:01:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6267 2024-03-06T10:37:55Z ddc:004 open_access

Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds Cheung, Yun Kuen Goranci, Gramoz Henzinger, Monika Distance Approximating Minor Graph Minor Graph Compression Vertex Sparsification Metric Embedding 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yun Kuen Cheung and Gramoz Goranci and Monika Henzinger 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.131 urn:nbn:de:0030-drops-62675 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.131 eng https://creativecommons.org/licenses/by/3.0/legalcode