2015/11/27 by Chitnis, Rajesh, Kamma, Lior, Krauthgamer, Robert
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1511.08647
By a classical result of Gomory and Hu (1961), in every edge-weighted graph G=(V,E,w), the minimum st-cut values, when ranging over all s,t∈ V, take at most |V|-1 distinct values. That is, these \binom|V|2 instances exhibit redundancy factor Ω(|V|). They further showed how to construct from G a tree (V,E',w') that stores all minimum st-cut values. Motivated by this result, we obtain tight bounds for the redundancy factor of several generalizations of the minimum st-cut problem. 1. Group-Cut: Consider the minimum (A,B)-cut, ranging over all subsets A,B⊆ V of given sizes |A|=α and |B|=β. The redundancy factor is Ωα,β(|V|). 2. Multiway-Cut: Consider the minimum cut separating every two vertices of S⊆ V, ranging over all subsets of a given size |S|=k. The redundancy factor is Ωk(|V|). 3. Multicut: Consider the minimum cut separating every demand-pair in D⊆ V× V, ranging over collections of |D|=k demand pairs. The redundancy factor is Ωk(|V|k). 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.