PRESERVING TERMINAL DISTANCES USING MINORS

摘要

We introduce the following notion of compressing an undirected graph G with (non-negative) edge-lengths and terminal vertices R (∈) V(G). A distance-preserving minor is a minor G' (of G) with possibly different edge-lengths, such that R (∈) V(G') and the shortest-path distance between every pair of terminals is exactly the same in G and in G'. We ask: what is the smallest f~*(k) such that every graph G with k = |R| terminals admits a distance-preserving minor G' with at most f~*(k) vertices? Simple analysis shows that f~*(k) ≤ O(k~4). Our main result proves that f~*(k) ≥ Ω(k~2), significantly improving on the trivial f~*(k) ≥ k. Our lower bound holds even for planar graphs G, in contrast to graphs G of constant treewidth, for which we prove that O(k) vertices suffice.