Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
复制标题
DOI：
10.4230/lipics.disc.2017.10
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
K. Censor-Hillel;Seri Khoury;A. Paz
中科院分区：
文献类型：
--
作者：
K. Censor-Hillel;Seri Khoury;A. Paz
我们给出了拥塞模型中自然图问题的第一个超线性下界，回答了一个长期未解决的问题。具体地，我们证明了在拥塞模型中，任何最小顶点覆盖或最大独立集的精确计算在最坏情况下都需要$Omega(n^2/\log^2{n})$轮数，以及图的$\chi$着色算法，其中$\chi$是图的色数。通过在P中给出两个简单的图问题，我们进一步证明了这种强下界并不局限于NP-Hard问题，这两个问题需要二次和近二次轮数。最后，我们讨论了计算加权所有对最短路径(APSP)的精确解的问题，该问题可以被认为是具有超线性下界的候选者。我们给出了这个问题的一个简单的$Omega(N)$下界，它意味着加权情况和未加权情况之间的分离，因为后者的复杂性是$\theta(n/\log{n})$。我们还正式证明了标准Alice-Bob框架不能提供精确加权APSP的超线性下界，其复杂性仍然是一个有趣的开放问题。
We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires $\Omega(n^2/\log^2{n})$ rounds in the worst case in the CONGEST model, as well as any algorithm for $\chi$-coloring a graph, where $\chi$ is the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds. Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple $\Omega(n)$ lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a complexity of $\Theta(n/\log{n})$. We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.