论文标题
紧密的有条件下限，以解决顶点连接问题
Tight Conditional Lower Bounds for Vertex Connectivity Problems
论文作者
论文摘要
我们研究了未加权的未指向图中图连通性问题的细粒度复杂性。最近的开发表明，Edge连接问题的所有变体，包括单源单链，全局，Steiner，单源和全对连接性，都可以在$ m^{1+o（1）} $时间中解决，将这些问题的复杂性崩溃到了几乎是最终的时间制度中。尽管历史上，顶点连接性要困难得多，但最近的结果表明，单源单链接和全球顶点连接都可以以$ m^{1+o（1）} $时间来求解，这使人们希望将所有顶点连接问题的变体都放入几乎很短的时间制度中。 我们表明，假设发现4个木板的猜想是不可能的。此外，我们从本质上可以通过在密集图中给组合算法的紧密界限来解决复杂性格局。共有三个不同的策略：（1）全对和施泰纳顶点连接具有复杂性$ \hatθ（n^{4}）$，（2）单源顶点连接具有复杂性$ \hatθ（n^{3}）$，和（3）单sink-single-sink-sink-sink-sink-sink-sink-sink-sink-sink和Global vertex Connectivity $hatθ（n^n^n^2）对于具有一般密度的图形，我们获得了$ \hatθ（m^{2}）$，$ \hatθ（m^{1.5}）$，$ \hatθ（m）$的紧密界限，假设可以在几乎很短的时间内计算出Gomory-hu树的元素连接性。
We study the fine-grained complexity of graph connectivity problems in unweighted undirected graphs. Recent development shows that all variants of edge connectivity problems, including single-source-single-sink, global, Steiner, single-source, and all-pairs connectivity, are solvable in $m^{1+o(1)}$ time, collapsing the complexity of these problems into the almost-linear-time regime. While, historically, vertex connectivity has been much harder, the recent results showed that both single-source-single-sink and global vertex connectivity can be solved in $m^{1+o(1)}$ time, raising the hope of putting all variants of vertex connectivity problems into the almost-linear-time regime too. We show that this hope is impossible, assuming conjectures on finding 4-cliques. Moreover, we essentially settle the complexity landscape by giving tight bounds for combinatorial algorithms in dense graphs. There are three separate regimes: (1) all-pairs and Steiner vertex connectivity have complexity $\hatΘ(n^{4})$, (2) single-source vertex connectivity has complexity $\hatΘ(n^{3})$, and (3) single-source-single-sink and global vertex connectivity have complexity $\hatΘ(n^{2})$. For graphs with general density, we obtain tight bounds of $\hatΘ(m^{2})$, $\hatΘ(m^{1.5})$, $\hatΘ(m)$, respectively, assuming Gomory-Hu trees for element connectivity can be computed in almost-linear time.
