文章基本信息

标题：On Packing Low-Diameter Spanning Trees
本地全文：下载
作者：Julia Chuzhoy ; Merav Parter ; Zihan Tan 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：33:1-33:18
DOI：10.4230/LIPIcs.ICALP.2020.33
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 âOSk/2âO< 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.
关键词：Spanning tree; packing; edge-connectivity