Arboricity and spanning-tree packing in random graphs with an application to load balancing
Pu Gao, Xavier Pérez‐Giménez, Cristiane M. Sato · Symposium on Discrete Algorithms · 2014
We study the arboricity A and the maximum number T of edge-disjoint spanning trees of the classical random graph G(n, p). For all p(n) e [0, 1], we show that, with high probability T is precisely the minimum between δ and ⌊m/(n - 1)⌋, where δ is the smallest degree of the graph and m denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for p such that: above this threshold, T equals ⌊m/(n - 1)⌋ and A equals ⌈m/(n - 1)⌉ and below this threshold, T equals δ, and we give a two-value concentration result for the arboricity A in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are sequentially added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most k in the two-choice load balancing problem, where k → ∞.