Preserving Terminal Distances using Minors

Abstract

We introduce the following notion of compressing an undirected graph G with edge-lengths and terminal vertices $R\subseteq V(G)$. A distance-preserving minor is a minor G' (of G) with possibly different edge-lengths, such that $R\subseteq V(G^{\prime })$ and the shortest-path distance between every pair of terminals is exactly the same in G and in G'. 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\ast (k)\le O(k^4)$. Our main result proves that $f\ast (k)\ge \Omega (k^2)$, significantly improving over the trivial $f\ast (k)\ge 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.

Cited by in corpus (2)

• Improved Guarantees for Vertex Sparsification in Planar Graphs
• Distance-preserving Subgraphs of Interval Graphs