## Vertex Sparsification and Mimicking Network

Series:
ACO Student Seminar
Friday, November 9, 2012 - 13:00
1 hour (actually 50 minutes)
Location:
Skiles 005
,
College of Computing, Georgia Tech
,

In this talk I will briefly survey results on Vertex Sparsification and some of our results on Mimicking network(or Exact Cut Sparsifier).&nbsp;Ankur Moitra introduced the notion of vertex sparsification to construct a smaller graph which preserves the properties of a huge network that are relevant to the terminals. Given a capacitated undirected graph $G=(V,E)$ with a set of terminals $K \subset V$, a &nbsp;vertex cut sparsifier is a smaller graph $H=(V_H,E_H)$ that approximately(quality f>=1) preserves all the minimum cuts between the terminals. Mimicking networks are the best quality vertex cut sparsifiers i.e, &nbsp;with quality 1. &nbsp; &nbsp;&nbsp;We improve both the previous upper($2^{2^{k}}$ ) and lower bounds($k+1$) for mimicking network reducing the doubly-exponential gap between them to a single-exponential gap. &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1. Given a graph $G$, we exhibit a construction of mimicking network with at most $k$'th Hosten-Morris number ($\approx 2^{{(k-1)} \choose {\lfloor {{(k-1)}/2} \rfloor}}$) of vertices (independent of size of $V$). &nbsp; &nbsp; Furthermore, we show that the construction is optimal among all {\itrestricted mimicking networks} -- a natural class of mimicking networks that are obtained by clustering vertices together. &nbsp; &nbsp; &nbsp; &nbsp;2. There exists graphs with $k$ terminals that have no mimicking network of size smaller than $2^{\frac{k-1}{2}}$. &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;3. We also exhibit constructions of better mimicking networks for trees($\lfloor(\frac{3k}{2})-1\rfloor$), outerplanar graphs($5k-9$) and graphs of bounded($t$) tree-width($k 2^{(2t+1) \choose {(2t+1)/2}}$). &nbsp; &nbsp; &nbsp; &nbsp;The talk will be self-contained and with no prerequisite.