Abstract
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̃ ≤ 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((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̃ ≥ D and Ω(1/D̃) < ε < 1/4, we give a deterministic, Õ((log² n) /ε²)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 Õ((log⁶ n)/ ε⁴) rounds and Õ((log³ n) /ε³) rounds respectively and only work in the LOCAL model.
BibTeX  Entry
@InProceedings{su_et_al:LIPIcs:2020:13093,
author = {HsinHao Su and Hoa T. Vu},
title = {{Distributed Dense Subgraph Detection and Low Outdegree Orientation}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {15:115:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771689},
ISSN = {18688969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13093},
URN = {urn:nbn:de:0030drops130938},
doi = {10.4230/LIPIcs.DISC.2020.15},
annote = {Keywords: Distributed Algorithms, Network Algorithms}
}
Keywords: 

Distributed Algorithms, Network Algorithms 
Collection: 

34th International Symposium on Distributed Computing (DISC 2020) 
Issue Date: 

2020 
Date of publication: 

07.10.2020 