Given a graph $G=(V,E)$, capacities $w(e)$ on edges, and a subset of terminals $\mathcal{ T} \subseteq V: |\mathcal{ T}| = k$, a mimicking network for $(G,\mathcal{ T})$ is a graph $(H,w')$ that contains copies of $\mathcal{ T}$ and preserves the value of minimum cuts separating any subset $A, B \subseteq \mathcal{ T}$ of terminals. Mimicking networks of size $2^{ 2^k}$ are known to exist and can be constructed algorithmically, while the best known lower bound is $2^{ \Omega(k)}$; therefore, an exponential size is required if one aims at preserving cuts exactly. In this paper, we study mimicking networks that preserve connectivity of the graph exactly up to the value of $c$, where $c$ is a parameter. This notion of mimicking network is sufficient for some applications, as we will elaborate. We first show that a mimicking of size $3^c \cdot k$ exists, that is, we can preserve cuts with small capacity using a network of size linear in $k$. Next, we show an algorithm that finds such a mimicking network in time $2^{ O(c^2)} \operatorname{ poly}(m)$.
Categories: cs.DS