文章基本信息
- 标题：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
