License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.33
URN: urn:nbn:de:0030-drops-124405
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12440/
Go to the corresponding LIPIcs Volume Portal


Chuzhoy, Julia ; Parter, Merav ; Tan, Zihan

On Packing Low-Diameter Spanning Trees

pdf-format:
LIPIcs-ICALP-2020-33.pdf (0.6 MB)


Abstract

Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every k-edge connected graph G contains a collection 𝒯 of ⌊k/2⌋ edge-disjoint 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 low-diameter 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 non-trivial upper and lower bounds on the diameter of tree packing. We start by showing that, for every k-edge connected n-vertex graph G of diameter D, there is a tree packing 𝒯 containing Ω(k) trees, of diameter O((101k log n)^D), with edge-congestion at most 2. Karger’s edge sampling technique demonstrates that, if G is a k-edge 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) edge-disjoint 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 k-edge connected graphs of diameter 2D, such that any packing of k/α trees with edge-congestion η 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 edge-disjoint 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 edge-congestion O(log n). Finally, we provide several applications of low-diameter 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 Low-Diameter Spanning Trees}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{33:1--33:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12440},
  URN =		{urn:nbn:de:0030-drops-124405},
  doi =		{10.4230/LIPIcs.ICALP.2020.33},
  annote =	{Keywords: Spanning tree, packing, edge-connectivity}
}

Keywords: Spanning tree, packing, edge-connectivity
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI