On mimicking networks representing minimum terminal cuts

Given a capacitated undirected graph G=(V,E)G=(V,E) with a set of terminals K⊂VK⊂V, a mimicking network   is a smaller graph H=(VH,EH)H=(VH,EH) which contains the set of terminals K   and for every bipartition [U,K−U][U,K−U] of the terminals, the cost of the minimum cut separating U   from K−UK−U in G is exactly equal to the cost of the minimum cut separating U   from K−UK−U in H.In this work, we improve both the previous known upper bound of 22k22k[1] and lower bound of (k+1)(k+1)[2] for mimicking networks, reducing the doubly-exponential gap between them to a single-exponential gap as follows:•Given a graph G, we exhibit a construction of mimicking network with at most k  'th Hosten–Morris number (≈2((k−1)⌊(k−1)/2⌋)) of vertices (independent of the size of V).•There exist graphs with k   terminals that have no mimicking network with less than 2k−12 number of vertices.