By a classical result of Gomory and Hu (1961), in every edge-weighted graph @math , the minimum @math -cut values, when ranging over all @math , take at most @math distinct values. That is, these @math instances exhibit redundancy factor @math . They further showed how to construct from @math a tree @math that stores all minimum @math -cut values. Motivated by this result, we obtain tight bounds for the redundancy factor of several generalizations of the minimum @math -cut problem. 1. Group-Cut: Consider the minimum @math -cut, ranging over all subsets @math of given sizes @math and @math . The redundancy factor is @math . 2. Multiway-Cut: Consider the minimum cut separating every two vertices of @math , ranging over all subsets of a given size @math . The redundancy factor is @math . 3. Multicut: Consider the minimum cut separating every demand-pair in @math , ranging over collections of @math demand pairs. The redundancy factor is @math . This result is a bit surprising, as the redundancy factor is much larger than in the first two problems. A natural application of these bounds is to construct small data structures that stores all relevant cut values, like the Gomory-Hu tree. We initiate this direction by giving some upper and lower bounds.
Another relevant notion here is that of mimicking networks, introduced by Hagerup, Katajainen, Nishimura, and Ragde @cite_11 . A mimicking network for @math and a terminals set @math is a graph @math where @math and for every @math , the minimum @math -cut in @math and in @math have the exact same value. They showed that every graph has a mimicking network with at most @math vertices. Some improved bounds are known, e.g., for graphs that are planar or have bounded treewidth, as well as some lower bounds @cite_9 @cite_1 @cite_4 . Mimicking networks deal with the problem for all @math ; we consider @math of bounded size, and thus typically achieve much smaller bounds.
@cite_9 @cite_1 @cite_4 @cite_11
1572185923 2951159514 2068727899
A mimickingnetwork for a k -terminal network, N , is one whose realizable external flows are the same as those of N . Let S(k) denote the minimum size of a mimicking network for a k -terminal network. In this paper we give new constructions of mimicking networks and prove the following results (the values in brackets are the previously best known results): S(4)=5 [2 16 ] , S(5)=6 [2 32 ] . For bounded treewidth networks we show S(k)= O(k) [2^ 2 k ] , and for outerplanar networks we show S(k) ( )10k-6 [k 2 2 k+2 ] . Given a large edge-weighted network @math with @math terminal vertices, we wish to compress it and store, using little memory, the value of the minimum cut (or equivalently, maximum flow) between every bipartition of terminals. One appealing methodology to implement a compression of @math is to construct a : a small network @math with the same @math terminals, in which the minimum cut value between every bipartition of terminals is the same as in @math . This notion was introduced by Hagerup, Katajainen, Nishimura, and Ragde [JCSS '98], who proved that such @math of size at most @math always exists. Obviously, by having access to the smaller network @math , certain computations involving cuts can be carried out much more efficiently. We provide several new bounds, which together narrow the previously known gap from doubly-exponential to only singly-exponential, both for planar and for general graphs. Our first and main result is that every @math -terminal planar network admits a mimicking network @math of size @math , which is moreover a minor of @math . On the other hand, some planar networks @math require @math . For general networks, we show that certain bipartite graphs only admit mimicking networks of size @math , and moreover, every data structure that stores the minimum cut value between all bipartitions of the terminals must use @math machine words. Given a capacitated undirected graph G=(V,E) with a set of terminals [email protected]?V, a mimicking network is a smaller graph H=(V"H,E"H) which contains the set of terminals K and for every bipartition [U,K-U] of the terminals, the cost of the minimum cut separating U from K-U in G is exactly equal to the cost of the minimum cut separating U from K-U in H. In this work, we improve both the previous known upper bound of 2^2^^^k[1] and lower bound of (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 2^k^-^1^2 number of vertices.