ON THE LOCALITY OF NASH-WILLIAMS FOREST DECOMPOSITION AND STAR-FOREST DECOMPOSITION

作     者：Harris, David G. Su, Hsin-Hao Vu, Hoa T. 

作者机构：Univ Maryland Dept Comp Sci Silver Spring MD 20901 USA Boston Coll Dept Comp Sci Chestnut Hill MA 02467 USA San Diego State Univ Dept Comp Sci San Diego CA 92182 USA 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (SIAM J Discrete Math)

年 卷 期：2023年第37卷第2期

页      面：800-830页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：NSF [CCF-2008422] 

主　　题：arboricity LOCAL algorithm star-arboricity forest decomposition 

摘      要：Given a graph G = (V, E) with arboricity a, we study the problem of decomposing the edges of G into (1+\varepsilon)a disjoint forests in the distributed LOCAL model. Here G may be a simple graph or multigraph. While there is a polynomial time centralized algorithm for a-forest decomposition (e.g., [H. Imai, J. Oper. Res. Soc. Japan, 26 (1983), pp. 186-211]), it remains an open question how close we can get to this exact decomposition in the LOCAL model. Barenboim and Elkin [L. Barenboim and M. Elkin, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash Williams decomposition, Distrib. Comput., 22 (2010), pp. 363--379] developed a LOCAL algorithm to compute a (2+\varepsilon)a-forest decomposition in O(log n \varepsilon ) rounds. Ghaffari and Su [Proc. 28th ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 2505--2523] made further progress by computing a (1 + \varepsilon)a-forest decomposition in O(log3 n \varepsilon4) rounds when \varepsilon a = S2(\surda log n);i.e., the limit of their algorithm is an (a + S2 (\surda log n))-forest decomposition. This algorithm, based on a combinatorial construction of Alon, McDiarmid, and Reed [Combinatorica, 12 (1992), pp. 375--380], in fact provides a decomposition of the graph into star-forests, i.e., each forest is a collection of stars. Our main goal is to reduce the threshold of \varepsilon a in (1 +\varepsilon)a-forest decomposition. We obtain a number of results with different parameters;some notable examples are the following: (1) An O( & DBLBOND;\rho log4 n \varepsilon )-round algorithm when \varepsilon a = S2\rho(1) in multigraphs, where \rho 0 is any arbitrary constant;(2) an O(log4 n log & DBLBOND;\varepsilon )round algorithm when \varepsilon a = S2( log & DBLBOND;log log & DBLBOND;) in multigraphs;(3) an O(log4\varepsilon n )-round algorithm when \varepsilon a = S2(logn) in multigraphs (this also covers an extension of the forest-decomposition problem to list-edge coloring);(4) an O( log3 n \vare