Abstract: We ask the following question: given a network with a large number of nodes, edges with nonnegative costs on them and a small set of special nodes called terminals, by how much can we compress the graph such that the shortest distance between any pair of terminals remains the same? We are allowed to perform a sequence of the following operations:
(1) Delete an edge (this reduces the number of edges by 1)
(2) Contract (or shrink) an edge into a single node (this reduces the number of edges and number of nodes by 1)
(3) Change edge cost arbitrarily, as long as it remains nonnegative
Formally stated, for any family $\mathcal{F}$ of undirected graphs, what is the smallest $f(k,\mathcal{F})$ such that every graph $G(V,E) \in
\mathcal{F}$ with nonnegative weights on the edges and a set of terminal nodes $R \subseteq V$ having $|R|=k$ admits a distance preserving minor with at most $f(k,\mathcal{F})$ nodes? (Observe that $f$ does not depend on the total number of nodes in the original graph).
In this talk, we will be defining the terms minor and distance preserving minor with examples. If $\mathcal{G}$ is the family of all undirected
graphs, $\mathcal{P}$ is the family of all planar graphs and $\mathcal{T}$ is the family of all trees, we will show that:
$f(k,\mathcal{G}) \leq k^{4}$
$f(k,\mathcal{P}) \geq c \cdot k^{2}$ (for some constant $c$)
$f(k,\mathcal{T})=2k-2$
This is due to recent work by Robert Krauthgamer and Tamar Zondiner.
