论文标题
确定性的小顶点连接几乎是线性时间
Deterministic Small Vertex Connectivity in Almost Linear Time
论文作者
论文摘要
在顶点连接问题中，给定一个无方向性的$ n $ vertex $ m $ - edge图$ g $，我们需要计算删除它们后可以断开$ g $的最小顶点。这个问题是最深入的图形问题之一。从2019年开始，新的工作[Nanongkai等人〜Stoc'19; Soda'20; Stoc'21]使用随机技术打破了二次时屏障，最近，通过Chen Et的最近宣布的MaxFlow Algorithm，以几乎是线性的时间算法达到顶峰。相反，所有已知的确定性算法都慢得多。最快的算法[Gabow focs'00]取$ O（m（n+\ min \ {c^{5/2}，cn^{3/4} \}））$时间，其中$ c $是顶点连接。是否存在任何常数$ c> 3 $的次级时间确定性算法，它仍然保持开放。 在本文中，我们为所有常数$ c $提供了第一个确定性的几乎线性时间顶点连接算法。我们的运行时间是$ m^{1+o（1）} 2^{o（c^{2}）} $ time，对于所有$ c = o（\ sqrt {\ log n}）$几乎是linear。这是第一种打破$ o（n^{2}）$的确定性算法 - 在稀疏图上绑定的时间，其中$ m = o（n）$，这是50多年前[Kleitman'69]闻名的。为了我们的结果，我们为顶点扩展器提供了一个新的还原框架，从而利用了我们模仿网络的新的几乎线性的时间构建，以建立顶点连接。 Kratsch和Wahlström[focs'12]的先前结构需要大的多项式时间，并且是随机的。
In the vertex connectivity problem, given an undirected $n$-vertex $m$-edge graph $G$, we need to compute the minimum number of vertices that can disconnect $G$ after removing them. This problem is one of the most well-studied graph problems. From 2019, a new line of work [Nanongkai et al.~STOC'19;SODA'20;STOC'21] has used randomized techniques to break the quadratic-time barrier and, very recently, culminated in an almost-linear time algorithm via the recently announced maxflow algorithm by Chen et al. In contrast, all known deterministic algorithms are much slower. The fastest algorithm [Gabow FOCS'00] takes $O(m(n+\min\{c^{5/2},cn^{3/4}\}))$ time where $c$ is the vertex connectivity. It remains open whether there exists a subquadratic-time deterministic algorithm for any constant $c>3$. In this paper, we give the first deterministic almost-linear time vertex connectivity algorithm for all constants $c$. Our running time is $m^{1+o(1)}2^{O(c^{2})}$ time, which is almost-linear for all $c=o(\sqrt{\log n})$. This is the first deterministic algorithm that breaks the $O(n^{2})$-time bound on sparse graphs where $m=O(n)$, which is known for more than 50 years ago [Kleitman'69]. Towards our result, we give a new reduction framework to vertex expanders which in turn exploits our new almost-linear time construction of mimicking network for vertex connectivity. The previous construction by Kratsch and Wahlström [FOCS'12] requires large polynomial time and is randomized.
