Distributed Dense Subgraph Detection and Low Outdegree Orientation
share
The maximum density 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. We give the following results: Given a value D̃≤ D and 0 < ϵ < 1, we show that a subgraph of density at least (1-ϵ)D̃ can be identified deterministically in O(( n) / ϵ) rounds in the LOCAL model. Using randomization, we show that such subgraph can be identified in O((^3 n) / ϵ^3) rounds in the CONGEST model with high probability. We also give a Ω(1/ϵ)-round lower bound which shows that our result for the LOCAL model is tight up to a O( n) factor. Moreover, our result can be extended to solve the directed version of the problem introduced by Kannan and Vinay KV99. Given an integer D̃≥ D and Ω(1/D̃) < ϵ < 1/4, we give an O(^2 n · (^2.71Δ) /ϵ^2)-round deterministic 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 for this problem is by Harris Harris19 that runs in Õ((^6 n) / ϵ^4) rounds in the model.
READ FULL TEXT