Distributed Dense Subgraph Detection and Low Outdegree Orientation
Distributed Dense Subgraph Detection and Low Outdegree Orientation
复制标题
DOI：
10.4230/lipics.disc.2020.15
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Hsin-Hao Su;H. Vu
中科院分区：
文献类型：
--
作者：
Hsin-Hao Su;H. Vu
由Picard和Queyranne以及Goldberg于80年代提出的可分解子图问题是组合优化中的经典问题，有着广泛的应用。最低出度定向问题被称为其对偶问题。我们研究了在分布式环境中寻找稠密子图的问题和计算低出度方向的问题。假设$G=（V，E）$是底层网络和输入图。设$D$表示$G$的最大密度子图的密度。我们的主要结果如下。给定一个值$\tilde{D} \leq D$和$0 < \n < 1$，我们证明了在一个随机模型中，密度至少为$（1-\n）\tilde{D}$的子图可以在O（（\log n）/ \n）$轮中确定性地被识别.我们还提出了一个下界，表明我们的结果是紧到一个$O（\log n）$的因素。在CONGEST模型中，我们证明了这样的子图可以在$O（（\log^3 n）/\epsilon ^3）$轮中以高概率被识别。我们的技术还导致了一个O（直径+（\log^4 n）/\epsilon^4）$轮算法，产生一个1-\emdash $近似的denial子图。这改进了Das Sarma等人[DISC 2012]之前的$O（diameter /\cdot \log n）$轮算法，该算法仅产生$1/2-\cdot $近似值。给定一个整数$\tilde{D} \geq D$和$\Omega（1/\tilde{D}）< \n < 1/4$，我们在CONGEST模型中给出了一个确定性的$\tilde{O}（（\log^2 n）/\epsilon ^2）$-轮算法，该算法计算每个顶点的出度上界为$（1+\n）\tilde{D}$的方向。以前，Harris [FOCS 2019]的最佳确定性算法和随机化算法分别在$\tilde{O}（（\log^6 n）/\epsilon ^4）$轮和$\tilde{O}（（\log^3 n）/\epsilon ^3）$轮中运行，并且仅适用于随机模型。
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 $\tilde{D} \leq D$ and $0 < \epsilon < 1$, we show that a subgraph with density at least $(1-\epsilon)\tilde{D}$ can be identified deterministically in $O((\log n) / \epsilon)$ 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^3 n) / \epsilon^3)$ rounds with high probability. Our techniques also lead to an $O(diameter + (\log^4 n)/\epsilon^4)$-round algorithm that yields a $1-\epsilon$ approximation to the densest subgraph. This improves upon the previous $O(diameter /\epsilon \cdot \log n)$-round algorithm by Das Sarma et al. [DISC 2012] that only yields a $1/2-\epsilon$ approximation. Given an integer $\tilde{D} \geq D$ and $\Omega(1/\tilde{D}) < \epsilon < 1/4$, we give a deterministic, $\tilde{O}((\log^2 n) /\epsilon^2)$-round algorithm in the CONGEST model that computes an orientation where the outdegree of every vertex is upper bounded by $(1+\epsilon)\tilde{D}$. Previously, the best deterministic algorithm and randomized algorithm by Harris [FOCS 2019] run in $\tilde{O}((\log^6 n)/ \epsilon^4)$ rounds and $\tilde{O}((\log^3 n) /\epsilon^3)$ rounds respectively and only work in the LOCAL model.