TY - GEN
T1 - Tight bounds for Gomory-Hu-like cut counting
AU - Chitnis, Rajesh
AU - Kamma, Lior
AU - Krauthgamer, Robert
PY - 2016/9/28
Y1 - 2016/9/28
N2 - By a classical result of Gomory and Hu (1961), in every edge-weighted graph G = (V, E, ω), the minimum st-cut values, when ranging over all s, t ∈ V, take at most |V|−1 distinct values. That is, these (|V|2) instances exhibit redundancy factor Ω(|V|). They further showed how to construct from G a tree (V, Eʹ, ωʹ) 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, à la the Gomory-Hu tree. We initiate this direction by giving some upper and lower bounds.
AB - By a classical result of Gomory and Hu (1961), in every edge-weighted graph G = (V, E, ω), the minimum st-cut values, when ranging over all s, t ∈ V, take at most |V|−1 distinct values. That is, these (|V|2) instances exhibit redundancy factor Ω(|V|). They further showed how to construct from G a tree (V, Eʹ, ωʹ) 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, à la the Gomory-Hu tree. We initiate this direction by giving some upper and lower bounds.
UR - http://www.scopus.com/inward/record.url?scp=84992747000&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-53536-3_12
DO - 10.1007/978-3-662-53536-3_12
M3 - Conference contribution
AN - SCOPUS:84992747000
SN - 9783662535356
T3 - Lecture Notes in Computer Science
SP - 133
EP - 144
BT - Graph-Theoretic Concepts in Computer Science
A2 - Heggernes, Pinar
PB - Springer Verlag
T2 - 42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016
Y2 - 22 June 2016 through 24 June 2016
ER -