Deterministic Small Vertex Connectivity in Almost Linear Time Thatchaphol SaranurakSorrachai Yingchareonthawornchai Abstract

2025-05-06 0 0 1.1MB 51 页 10玖币
侵权投诉
Deterministic Small Vertex Connectivity in Almost Linear Time
Thatchaphol Saranurak∗Sorrachai Yingchareonthawornchai†
Abstract
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{c5/2, cn3/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
m1+o(1)
2
O(c2)
time, which is almost-linear for all
c
=
o
(
√log n
). This is the first deterministic algorithm that breaks the
O
(
n2
)-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.
∗thsa@umich.edu. University of Michigan, USA
†sorrachai.yingchareonthawornchai@aalto.fi. Aalto University, Finland
arXiv:2210.13739v1 [cs.DS] 25 Oct 2022
Contents
1 Introduction 1
1.1 OurApproach........................................ 1
1.2 NewMimickingNetworks ................................. 3
1.3 Organization ........................................ 3
2 Preliminaries 4
3 Vertex Connectivity Algorithm 5
4 Expanders or Terminals 9
4.1 Overview .......................................... 9
4.2 A Divide-and-Conquer Lemma for Vertex Cuts . . . . . . . . . . . . . . . . . . . . . 9
4.3 An Algorithm for Expanders-or-Terminal Pair . . . . . . . . . . . . . . . . . . . . . . 12
4.4 A Fast Implementation of Algorithm 2.......................... 13
5c-Vertex Connectivity Mimicking Networks 16
5.1 VertexClosureOperation ................................. 16
5.2 Proof of Lemma 5.7 .................................... 17
5.3 Proof of Lemma 5.3 .................................... 18
6 Computing a (T, c)-Covering Sets 19
6.1 Proof of Theorem 5.2 .................................... 20
6.2 Proof of Lemma 6.4 .................................... 21
7 Computing a (T, c)-Reducing-or-Covering Partition-Set Pair 23
7.1 Divide-and-Conquer Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.2 Computing a (T, c)-Reducing-or-Covering Separators-Set Pair . . . . . . . . . . . . . 27
7.3 A Partition from the Recursion Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.4 Fast Implementation for Few Terminals . . . . . . . . . . . . . . . . . . . . . . . . . 33
7.5 Fast Implementation for Expanders with Many Terminals . . . . . . . . . . . . . . . 35
7.6 ImplementationDetails .................................. 39
7.7 TheFinalAlgorithm.................................... 41
8 Open Problems 44
A Omitted Proofs 47
A.1 Proof of Claim 6.5 ..................................... 47
A.2 Proof of Lemma 7.41 .................................... 48
1 Introduction
Vertex connectivity is one of most fundamental measures for robustness of graphs. For any
n
-vertex
m
-edge graph
G
= (
V, E
), the vertex connectivity
κG
of
G
is the minimum number of vertices
that can disconnect
G
after removing them. Fast algorithms for computing vertex connectivity has
been extensively studied [
Kle69
,
Pod73
,
ET75b
,
Eve75
,
Gal80
,
EH84
,
Mat87
,
BDD+82
,
LLW88
,
CR94
,
NI92
,
CT91
,
Hen97
,
HRG00
,
Gab06
,
CGK14
]. (See [
NSY19
] for a discussion.) Since 2019, a
new line of work [
NSY19
,
FNS+20
,
LNP+21
] has used randomized techniques to break the long-
standing quadratic-time barrier and, very recently, culminated in an almost-linear time algorithm
via the recently announced maxflow algorithm by [
CKL+22
]. However, these new algorithms are all
Monte-Carlo and, thus, can make errors.
In contrast, all known deterministic algorithms are much slower. Improved upon previous
deterministic algorithms [
ET75a
,
HRG00
], in 2000, Gabow [
Gab06
] gave the previously fastest
deterministic algorithm with
O
(
m
(
n
+
min{c5/2, cn3/4}
)) time where
c
is the vertex connectivity.
While linear-time algorithms are known when c≤3[Tar72,HT73], 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 algorithm for computing vertex
connectivity for all constants
c
. To state our result precisely, we need some terminology. We say
(
L, S, R
)is a vertex cut if
L, S, R
partition a vertex set
V
but there is no edge between
L
and
R
.
The size of a vertex cut (
L, S, R
)is
|S|
. Note that a vertex cut of size less than
c
certifies that
κG< c
. If there is no such cut, then
κG≥c
, and we say that
G
is
c
-connected. Our main result is
as follows:
Theorem 1.1.
There is a deterministic algorithm that, given an undirected graph
G
, in
m1+o(1)
2
O(c2)
time either outputs a vertex cut of size less than cor concludes that Gis c-connected.
When focusing on sparse graphs where
m
=
O
(
n
), the
O
(
n2
)-time bound was shown for more
than 50 years ago [Kle69]. Theorem 1.1 is the first that deterministically breaks this barrier.
Related Works.
Significant effort has been devoted to devising deterministic algorithms that
is as fast as their randomized counterparts. Examples include the line of work on deterministic
minimum edge cut algorithm [
KT15
,
HRW17
,
Sar21
,
LP20
] where, recently, Li [
Li21
] showed a
deterministic almost-linear time algorithm for minimum edge cuts even in weighted graphs. Another
example are deterministic expander decomposition algorithms and their applications to deterministic
Laplacian solvers and approximate max flow [CGL+20].
Historical Note.
The previous version of this paper [
GLN+19
] contains two results: deterministic
subquadratic-time algorithms for balanced cuts and vertex connectivity. The paper was split into
two newer papers. The newer version of the balanced cut algorithms is [
CGL+20
], which gave the
first almost-linear time deterministic balanced cut algorithm. Our paper is the new version of the
vertex connectivity algorithms from [GLN+19].
1.1 Our Approach
Towards our main result (Theorem 1.1), we develop two main algorithmic components. Below, we
explain how their combination immediately implies Theorem 1.1. Suppose our goal is just to check
whether Gis c-connected for c=O(1).
1
“Almost” Reduction to Vertex Expanders.
Our starting point is the observation that
c
-
connectivity can be checked fast on vertex expanders. For any vertex cut (
L, S, R
)of
G
, its expansion
is
h
(
L, S, R
) =
|S|
|S|+min{|L|,|R|}
. When
h
(
L, S, R
)is small, we say that the cut is sparse. We say
G
is a
φ
-vertex expander if
min(L,S,R)h
(
L, S, R
)
≥φ
and we simply call it a vertex expander when
φ≥
1
/no(1)
. Observe that for any vertex cut (
L, S, R
)of size less than
c
in a vertex expander
must be very unbalanced, i.e.,
min{|L|,|R|} ≤ cno(1)
. Suppose we are given a vertex
x∈L
where
|L| ≤ cno(1)
, the local flow algorithms can find the cut of size less than
c
in
poly
(
cno(1)
)time
[
NSY19
] or in
cO(c)no(1)
time [
CHI+17
]. Thus, by simply calling the local flow algorithm from every
vertex, one can check
c
-connectivity of a vertex expander in almost-linear total time. However, in
general the graph might contain a very sparse cut. This is exactly the hard instance of all previous
deterministic algorithms.
Now, our new framework essentially allows us to assume that the input graph is a vertex expander.
More precisely, give any graph
G
= (
V, E
), our subroutine
ExpandersOrTerminal
(
G, c, φ
)
computes in
m1+o(1)/φ
time a collection
G
of
φ
-vertex expanders and a terminal set
T⊂V
with
the following guarantee:
1. G
is
c
-connected iff every
H∈ G
is
c
-connected and the Steiner connectivity of
T
is at least
c
(i.e. there is no vertex cut of size less than cseparating any terminal pair x, y ∈T).
2. Ghas almost-linear total size, i.e., PH∈G |V(H)|=n1+o(1).
3. |T| ≤ φn1+o(1).
See details in Definition 3.2 and Theorem 3.3. We will set φ= 1/no(1) so that |T|  nis small.
We employ the reduction as follows. Given
G
, we call
ExpandersOrTerminal
(
G, c, φ
)and
check
c
-connectivity of all vertex expanders
H∈ G
in almost-linear total time, since their total size
is almost-linear. If any
H∈ G
is not
c
-connected, then we are done. Otherwise, we still need to
check the Steiner connectivity of
T
. Therefore, in almost-linear time, the framework allows us to
“focus” on a small terminal set Tand this is where our second algorithmic component can help.
Mimicking Network for Vertex Connectivity.
Given any
G
= (
V, E
)and terminal set
T
,
our second subroutine
VertexSparsify
(
G, T, c
)computes a small graph
H
of size proportional to
T
and
H
preserves all minimum vertex cuts between terminals
T
up to size
c
. More precisely, let
µG
(
A, B
)be the minimum number of vertices that, after removing from
G
, there is no path from
A
to
B
left (we allow removing vertices in
A
and
B
). The guarantees of
H
is that, for any
A, B ⊆T
,
min{µG
(
A, B
)
, c}
=
min{µH
(
A, B
)
, c}
. We also require that
κH≥min{κG, c}
(otherwise, there
might be a new minimum vertex cut in
H
). We call
H
a
c
-vertex connectivity mimicking network
or, for short a (T, c)-sparsifier for G. Below, we show that VertexSparsify can be implemented
in almost-linear time. See Definition 3.4 and Theorem 3.5 for details.
Theorem 1.2.
Our subroutine
VertexSparsify
(
G, T, c
)computes a (
T, c
)-sparsifier
H
for
G
of
size |E(H)|=|T|2O(c2)in m1+o(1)2O(c2)time.
How do we exploit this sparsifier? Let
T
be the terminal set from
ExpandersOrTerminal
and
H
=
VertexSparsify
(
G, T, c
).
1
Since
H
preserves all minimum vertex cuts between
T
and
also does not introduce any new minimum cut, it suffices to check if
H
is
c
-connected. By setting
φ= 1/2O(c2)no(1), we have |T| ≤ n/2O(c2)and so |E(H)| ≤ n/2. Thus, we have reduced the vertex
1
For a technical reason, we actually need to compute
H
=
VertexSparsify
(
G, T 0, c
)where
T0
=
∪v∈TNc
G
(
v
)and
Nc
G(v)is an arbitrary set of cneighbors of v. See Section 3for details.
2
connectivity problem to a graph of half the size in almost-linear time. By repeating this framework at
most
O
(
log n
)rounds, we are done. That completes the explanation how the high-level components
fit together.
1.2 New Mimicking Networks
The new mimicking network in Theorem 1.2 can be of independent interest.
Let us compare Theorem 1.2 with related results on mimicking network literature. Kratsch and
Wahlström [
KW20
] showed an algorithm that computes a (
T, c
)-sparsifier (without the condition that
κH≥min{κG, c}
) of size
O
(
|T|3
)in some large polynomial time and their algorithm is randomized.
In our applications it is crucial that the size is linear in
|T|
and the algorithm is deterministic.
When we consider edge cuts instead of vertex cuts,
c
-edge-connectivity mimicking networks of size
|T|poly(c)can be computed in m1+o(1)cO(c)time [CDK+21] or nO(1) time [Liu20].
Theorem 1.2 can be viewed as an adaptation of
c
-edge connectivity mimicking networks from
[
LPS19
,
CDK+21
] to
c
-vertex connectivity, but there are many technical obstacles we need to
overcome. Basically, this is because not all techniques for edge cuts generalize to vertex cuts. Even
when they do generalize, they require careful and complicated definitions and arguments in order to
carry out the approach. For concrete examples, we observe that the “cut enumeration” approach of
[
CDK+21
] fails completely for vertex cuts.
2
So, instead, we take the approach based on covering sets
and intersecting sets of [
LPS19
]. To order to generalize this approach, we arrive at a complicated
and delicate definition of reducing-or-covering partition-set pair (See Definition 6.1). Nonetheless,
while trying to overcome these technical obstacles in constructing mimicking networks, we believe
that there is one technical lesson that might be useful beyond this work.
Fast Closure Oracles via Hypergraphs.
In our algorithm, we need to perform an operation
that is analogous to contracting an edge
e
, but we do it on a vertex
v
. This operation is called
neighborhood closure, or just closure, for short. The closure has been use as an important primitive
in [
KW20
]. Given a graph
G
with a vertex
v
,closing
v
in
G
is to add a clique between all neighbors
of
v
, and remove
v
from
G
. This operation clearly takes a lot of time when
v
has large degree. We
observe that if we “lift” the problem to hypergraphs, it turns out that the equivalent operation is as
follows: closing
v
on a hypergraph
H
is to merge all hyperedges
e
containing
v
into one hyperedge,
i.e. insert
e0
=
∪e3ve
and remove all
e
that contains
v
. This simple equivalence is formalized in
Observation 7.26.
Now, it turns out that the closure operation on hypergraph is very easy to (implicitly) implement,
for example, by using the union-find data structure. More specifically, our algorithm in Section 7
will need to implement a data structure on a graph that handle closure operations in an online
manner. The key technique that enables our algorithm to run in almost-linear time is to “lifting”
the graph into a hypergraph and implementing closure operations on the hypergraph.
1.3 Organization
We describe necessary background and terminologies in Section 2. We describe the full vertex
connectivity algorithm in Section 3. Then, we explain in Section 4how to implement the reduction
to vertex expanders, i.e. the subroutine
ExpandersOrTerminal
(
G, c, φ
). For the rest of the
2
In [
CDK+21
], they only show a fast algorithm for enumerating cuts (
S, V \S
)whose one side induced a connected
graph (i.e.
G
[
S
]is connected), and then argue that this kind of cuts suffice for their construction. This is not true for
vertex cuts. We would need to list vertex cuts (
L, S, R
)where
G
[
L
]is not connected too. While listing cut where
G[L∪S]is connected suffices, it is not clear how to do it fast.
3
摘要：

DeterministicSmallVertexConnectivityinAlmostLinearTimeThatchapholSaranurak*SorrachaiYingchareonthawornchai„AbstractInthevertexconnectivityproblem,givenanundirectedn-vertexm-edgegraphG,weneedtocomputetheminimumnumberofverticesthatcandisconnectGafterremovingthem.Thisproblemisoneofthemostwell-studiedgr...

展开>> 收起<<
Deterministic Small Vertex Connectivity in Almost Linear Time Thatchaphol SaranurakSorrachai Yingchareonthawornchai Abstract.pdf

共51页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：51 页 大小：1.1MB 格式：PDF 时间：2025-05-06

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 51
评分 收藏
分享
立即下载
客服
关注