Speaker: |
Kshitij Gajjar |

Organiser: |
Swapnil Singone |

Date: |
Friday, 31 Jan 2014, 14:00 to 15:00 |

Venue: |
D-405 (D-Block Seminar Room) |

(Scan to add to calendar)

(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.