Chuzhoy, Julia ;
Parter, Merav ;
Tan, Zihan
On Packing LowDiameter Spanning Trees
Abstract
Edge connectivity of a graph is one of the most fundamental graphtheoretic concepts. The celebrated tree packing theorem of Tutte and NashWilliams from 1961 states that every kedge connected graph G contains a collection 𝒯 of ⌊k/2⌋ edgedisjoint spanning trees, that we refer to as a tree packing; the diameter of the tree packing 𝒯 is the largest diameter of any tree in 𝒯. A desirable property of a tree packing for leveraging the high connectivity of a graph in distributed communication networks, is that its diameter is low. Yet, despite extensive research in this area, it is still unclear how to compute a tree packing of a lowdiameter graph G, whose diameter is sublinear in V(G), or, alternatively, how to show that such a packing does not exist.
In this paper, we provide first nontrivial upper and lower bounds on the diameter of tree packing. We start by showing that, for every kedge connected nvertex graph G of diameter D, there is a tree packing 𝒯 containing Ω(k) trees, of diameter O((101k log n)^D), with edgecongestion at most 2.
Karger’s edge sampling technique demonstrates that, if G is a kedge connected graph, and G[p] is a subgraph of G obtained by sampling each edge of G independently with probability p = Θ(log n/k), then with high probability G[p] is connected. We extend this result to show that the diameter of G[p] is bounded by O(k^(D(D+1)/2)) with high probability. This immediately gives a tree packing of Ω(k/log n) edgedisjoint trees of diameter at most O(k^(D(D+1)/2)). We also show that these two results are nearly tight for graphs with a small diameter: we show that there are kedge connected graphs of diameter 2D, such that any packing of k/α trees with edgecongestion η contains at least one tree of diameter Ω((k/(2α η D))^D), for any k,α and η. Additionally, we show that if, for every pair u,v of vertices of a given graph G, there is a collection of k edgedisjoint paths connecting u to v, of length at most D each, then we can efficiently compute a tree packing of size k, diameter O(D log n), and edgecongestion O(log n). Finally, we provide several applications of lowdiameter tree packing in the distributed settings of network optimization and secure computation.
BibTeX  Entry
@InProceedings{chuzhoy_et_al:LIPIcs:2020:12440,
author = {Julia Chuzhoy and Merav Parter and Zihan Tan},
title = {{On Packing LowDiameter Spanning Trees}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {33:133:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12440},
URN = {urn:nbn:de:0030drops124405},
doi = {10.4230/LIPIcs.ICALP.2020.33},
annote = {Keywords: Spanning tree, packing, edgeconnectivity}
}
29.06.2020
Keywords: 

Spanning tree, packing, edgeconnectivity 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 