文章基本信息

标题：Distributed Dense Subgraph Detection and Low Outdegree Orientation
本地全文：下载
作者：Hsin-Hao Su ; Hoa T. Vu
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：179
页码：1-18
DOI：10.4230/LIPIcs.DISC.2020.15
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The densest subgraph problem, introduced in the 80s by Picard and Queyranne [Networks 1982] as well as Goldberg [Tech. Report 1984], is a classic problem in combinatorial optimization with a wide range of applications. The lowest outdegree orientation problem is known to be its dual problem. We study both the problem of finding dense subgraphs and the problem of computing a low outdegree orientation in the distributed settings. Suppose G = (V,E) is the underlying network as well as the input graph. Let D denote the density of the maximum density subgraph of G. Our main results are as follows. - Given a value DÌf â¤ D and 0 < Îµ < 1, we show that a subgraph with density at least (1-Îµ)DÌf can be identified deterministically in O((log n) / Îµ) rounds in the LOCAL model. We also present a lower bound showing that our result for the LOCAL model is tight up to an O(log n) factor. In the CONGEST~ model, we show that such a subgraph can be identified in O((logÂ³ n) / ÎµÂ³) rounds with high probability. Our techniques also lead to an O(diameter (logâ´ n)/Îµâ´)-round algorithm that yields a 1-Îµ approximation to the densest subgraph. This improves upon the previous O(diameter /Îµ â<. log n)-round algorithm by Das Sarma et al. [DISC 2012] that only yields a 1/2-Îµ approximation. - Given an integer DÌf â¥ D and Î©(1/DÌf) < Îµ < 1/4, we give a deterministic, OÌf((logÂ² n) /ÎµÂ²)-round algorithm in the CONGEST~ model that computes an orientation where the outdegree of every vertex is upper bounded by (1 Îµ)DÌf. Previously, the best deterministic algorithm and randomized algorithm by Harris [FOCS 2019] run in OÌf((logâ¶ n)/ Îµâ´) rounds and OÌf((logÂ³ n) /ÎµÂ³) rounds respectively and only work in the LOCAL model.
关键词：Distributed Algorithms; Network Algorithms