Mimicking Networks Parameterized by Connectivity
share
Given a graph G=(V,E), capacities w(e) on edges, and a subset of terminals T⊆ V: |T| = k, a mimicking network for (G,T) is a graph (H,w') that contains copies of T and preserves the value of minimum cuts separating any subset A, B ⊆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^Ω(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 · 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)poly(m).
READ FULL TEXT