- Series
- ACO Student Seminar
- Time
- Friday, November 9, 2012 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Arindam Khan – College of Computing, Georgia Tech – akhan67@gatech.edu – http://www.cc.gatech.edu/~akhan67/
- Organizer
- Cristóbal Guzmán
Please Note: In this talk I will briefly survey results on Vertex Sparsification and some of our results on Mimicking network(or Exact Cut Sparsifier). 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 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, with quality 1. 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. 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$). 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. 2. There exists graphs with $k$ terminals that have no mimicking network of size smaller than $2^{\frac{k-1}{2}}$. 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}}$). The talk will be self-contained and with no prerequisite.