2019/07/29 by Su, Hsin-Hao, Vu, Hoa T. · 2 citations
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1907.12443
The densest subgraph problem, introduced in the 80s by Picard and Queyranne as well as Goldberg, 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 ≤ D and 0 < ε< 1, we show that a subgraph with density at least (1-ε)D 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((log3 n) / ε3) rounds with high probability. Our techniques also lead to an O(diameter + (log4 n)/ε4)-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 ≥ D and Ω(1/D) < ε< 1/4, we give a deterministic, O((log2 n) /ε2)-round algorithm in the CONGEST model that computes an orientation where the outdegree of every vertex is upper bounded by (1+ε)D. Previously, the best deterministic algorithm and randomized algorithm by Harris [FOCS 2019] run in O((log6 n)/ ε4) rounds and O((log3 n) /ε3) rounds respectively and only work in the LOCAL model.