【免费】增量式单源最短路径1资源-CSDN文库

需积分: 0 89 浏览量 2022-08-03 19:26:27 上传评论收藏 936KB PDF 举报

增量式单源最短路径（Incremental Single-Source Shortest Paths, ISSSP）问题是一个在图理论和算法设计中常见的动态问题。在这个问题中，我们有一张加权有向图 𝐺=(𝑉,𝐸)，其中节点集合𝑉 和边集合𝐸 可能会经历边的插入和删除操作。给定一个源节点 𝑠 ∈ 𝑉，目标是维护从源节点到图中所有其他节点的距离𝑑(𝑠,𝑡)。在动态图算法领域，对于精确的动态SSSP和近似完全动态SSSP已经有许多研究，并且通过精细复杂性分析得到了一些强下界。然而，对于有向图的近似部分动态SSSP问题，目前还没有比经典的ES树（ES-Tree）算法效率更高的确定性算法。ES树是由Edmonds和Johnson在1981年提出的，它提供了一种有效的方法来处理动态最短路径问题，但其性能在某些情况下可能不是最优的。本文提出了一种新的确定性数据结构，用于处理加权有向图中的增量SSSP问题。这个数据结构的总更新时间是 ˜𝑂(𝑛2 log𝑊 /𝜖𝑂(1))，这在非常稠密的图中接近最优，其中 𝑊 是图中最大权重与最小权重的比例。该算法在边数𝑚为𝑛1.1阶时，相对于Henzinger等人在STOC'14和ICALP'15中提出的最佳部分动态随机算法有所改进。此外，文章还提供了对现有算法的条件性下界。Henzinger等人在STOC'15中利用OMv假设证明了在无向图中，部分动态精确的𝑠-𝑡最短路径问题需要有平均更新或查询时间𝑚1/2−𝑜(1)，前提是允许多项式预处理时间。作者们提出了一个新的关于寻找团（Clique）的假设，从而将具有多项式预处理时间的算法的更新和查询下界提升到𝑚0.626−𝑜(1)。进一步地，基于𝑘-Cycle假设，他们展示了任何部分动态SSSP算法都需要至少这样的时间复杂度。这篇文章贡献了一个在有向图增量SSSP问题上的突破性算法，提高了效率，并且通过引入新的假设和下界，推动了动态最短路径问题的研究边界。这对于理解动态图算法的潜力以及限制，以及未来算法设计的方向都有着重要意义。

资源详情

资源评论

资源推荐

New Algorithms and Hardness for Incremental Single-Source

Shortest Paths in Directed Graphs

∗

Maximilian Probst Gutenberg

University of Copenhagen

Copenhagen, Denmark

maximilian.probst@outlook.com

Virginia Vassilevska Williams

MIT

USA

Nicole Wein

MIT

USA

ABSTRACT

In the dynamic Single-Source Shortest Paths (SSSP) problem, we are

given a graph

𝐺 = (𝑉, 𝐸)

subject to edge insertions and deletions

and a source vertex

𝑠 ∈ 𝑉

, and the goal is to maintain the distance

𝑑 (𝑠, 𝑡) for all 𝑡 ∈ 𝑉 .

Fine-grained complexity has provided strong lower bounds for

exact partially dynamic SSSP and approximate fully dynamic SSSP

[ESA’04, FOCS’14, STOC’15]. Thus much focus has been directed

towards nding ecient partially dynamic

(

+ 𝜖)

-approximate

SSSP algorithms [STOC’14, ICALP’15, SODA’14, FOCS’14, STOC’16,

SODA’17, ICALP’17, ICALP’19, STOC’19, SODA’20, SODA’20]. De-

spite this rich literature, for directed graphs there are no known

deterministic algorithms for

(

+ 𝜖)

-approximate dynamic SSSP

that perform better than the classic ES-tree [JACM’81]. We present

the rst such algorithm.

We present a deterministic data structure for incremental SSSP in

weighted directed graphs with total update time

𝑂 (𝑛

log𝑊 /𝜖

𝑂 (1)

)

which is near-optimal for very dense graphs; here

𝑊

is the ratio of

the largest weight in the graph to the smallest. Our algorithm also

improves over the best known partially dynamic randomized algo-

rithm for directed SSSP by Henzinger et al. [STOC’14, ICALP’15] if

𝑚 = 𝜔 (𝑛

1.1

Complementing our algorithm, we provide improved conditional

lower bounds. Henzinger et al. [STOC’15] showed that under the

OMv Hypothesis, the partially dynamic exact

𝑠

𝑡

Shortest Path

problem in undirected graphs requires amortized update or query

time

𝑚

1/2−𝑜 (1)

, given polynomial preprocessing time. Under a new

hypothesis about nding Cliques, we improve the update and query

lower bound for algorithms with polynomial preprocessing time to

𝑚

0.626−𝑜 (1)

. Further, under the

𝑘

-Cycle hypothesis, we show that

any partially dynamic SSSP algorithm with

𝑂 (𝑚

2−𝜖

)

preprocess-

ing time requires amortized update or query time

𝑚

1−𝑜 (1)

, which

∗

The rst author was visiting Massachusetts Institute of Technology, Massachusetts,

US, when the work was done and is supported by Thorup’s Investigator Grant from the

Villum Foundation under Grant No. 16582 and by STIBOFONDEN’s IT Travel Grant

for PhD Students. The second author is supported by an NSF CAREER Award, NSF

Grants CCF-1528078 and CCF-1514339, a BSF Grant BSF:2012338, a Sloan Research

Fellowship and a Google faculty fellowship. The third author is supported by an NSF

Graduate Fellowship and NSF Grant CCF-1514339.

Permission to make digital or hard copies of all or part of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for prot or commercial advantage and that copies bear this notice and the full citation

on the rst page. Copyrights for components of this work owned by others than the

author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or

republish, to post on servers or to redistribute to lists, requires prior specic permission

and/or a fee. Request permissions from permissions@acm.org.

STOC ’20, June 22–26, 2020, Chicago, IL, USA

ACM ISBN 978-1-4503-6979-4/20/06.. . $15.00

https://doi.org/10.1145/3357713.3384236

is essentially optimal. All previous conditional lower bounds that

come close to our bound [ESA’04,FOCS’14] only held for “combina-

torial” algorithms, while our new lower bound does not make such

restrictions.

CCS CONCEPTS

• Theory of computation → Dynamic graph algorithms

; Data

structures design and analysis.

KEYWORDS

dynamic algorithm, shortest path, single source shortest path, con-

ditional lower bound

ACM Reference Format:

Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole

Wein. 2020. New Algorithms and Hardness for Incremental Single-Source

Shortest Paths in Directed Graphs. In Proceedings of the 52nd Annual ACM

SIGACT Symposium on The ory of Computing (STOC ’20), June 22–26, 2020,

Chicago, IL, USA. ACM, New York, NY, USA, 14 pages. https://doi.org/10.

1145/3357713.3384236

1 INTRODUCTION

A dynamic graph

𝐺

is a sequence of graphs

𝐺

, 𝐺

, . . . , 𝐺

𝑡

such

that

𝐺

is the initial graph that is subsequently undergoing edge

updates such that every two consecutive versions

𝐺

𝑖

and

𝐺

𝑖+1

the dynamic graph

𝐺

dier only in one edge (or the weight of one

edge). If the sequence of update operations consists only of edge

deletions and weight increases, we say that

𝐺

is a decremental graph

and if the update operations are restricted to edge insertions and

weight decreases, we say that G is incremental. In either case, we

say that

𝐺

is partially dynamic and if the update sequence is mixed

we say 𝐺 is fully dynamic.

In the study of dynamic graph algorithms, we are concerned

with maintaining properties of

𝐺

eciently. More precisely, we are

concerned with designing a data structure that supports update and

query operations such that after the

𝑖

𝑡ℎ

edge update is processed,

an adversary can query properties of 𝐺

𝑖

We consider the problem of (approximate) Single-Source Shortest

Paths (SSSP) in a partially dynamic graph

𝐺

. In this problem, a

dedicated source vertex

𝑠 ∈ 𝑉

is given on initialization and the

query operation takes as input any vertex

𝑡 ∈ 𝑉

and outputs the

(approximate) shortest-path distance estimate

𝑑 (𝑠, 𝑡)

from

𝑠

𝑡

the current version of

𝐺

. We say that distance estimates have stretch

𝛼 ≥

1, if the algorithm guarantees that

𝑑 (𝑠, 𝑡) ≤

𝑑 (𝑠, 𝑡) ≤ 𝛼𝑑(𝑠, 𝑡 )

is satised for every distance estimate where

𝑑 (𝑠, 𝑡)

denotes the

distance from 𝑠 to 𝑡 in the current version of 𝐺.

When proving lower bounds for partially dynamic SSSP, we also

consider a potentially easier problem,

𝑠

𝑡

Shortest Path (

𝑠

𝑡

SP), thus

153

STOC ’20, June 22–26, 2020, Chicago, IL, USA Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein

obtaining stronger lower bounds. In

𝑠

𝑡

SP, one wants to maintain

a shortest path from 𝑠 to 𝑡 for some xed 𝑠 and 𝑡.

1.1 Motivation

Partially dynamic SSSP is a well-motivated problem with wide-

ranging applications:

•

Partially dynamic data structures are often used as internal

data structures to solve the fully dynamic version of the

problem (see for example [

] for applications of par-

tially dynamic SSSP) which in turn can be used to maintain

properties of real-world graphs undergoing changes.

•

Partially dynamic SSSP is often employed as internal data

structure for related problems such as maintaining the di-

ameter in partially dynamic graphs [

] or matchings in

incremental bipartite graphs [20].

•

Many static algorithms use partially dynamic algorithms as

a subroutine. For example, incremental All-Pairs Shortest

Paths can be used to construct light spanners [

] and greedy

spanners. Moreover, a recent line of research shows that

many ow problems can be reduced to decremental SSSP,

and recent progress has already led to faster algorithms

for multi-commodity ow [

], vertex-capacitated ow, and

sparsest vertex-cut [27].

1.2 Prior Work

In this section we discuss prior work directly related to our results.

We use

𝑂

notation to suppress factors of

log 𝑛

and assume constant

𝜖

in the approximation. For a more detailed discussion of prior

results, we refer the reader to the full version of the article.

Let

𝑚

be the maximum number of edges and let

𝑛

be the max-

imum number of vertices

in any version of the dynamic input

graph

𝐺

. If

𝐺

is weighted, we denote by

𝑊

the aspect ratio of the

graph, which is the largest weight divided by the smallest weight in

the graph. For partially dynamic algorithms, we follow the conven-

tion of stating the total update time rather than the time for each

individual update. Unless otherwise stated, queries take worst-case

constant time.

Algorithms for partially dynamic directed SSSP.

For directed

graphs, the classic ES-tree data structure by Even and Shiloach

[

] and its later extensions by Henzinger and King [

] initi-

ated the eld, with total update time

𝑂 (𝑚𝑛𝑊 )

for exact incremen-

tal/decremental directed SSSP. Using an edge rounding technique

[

], the ES-tree can further handle edge weights

more eciently, giving an

𝑂 (𝑚𝑛 log𝑊 )

time algorithm for incre-

mental/decremental

(

+𝜖)

-approximate directed SSSP. This result

has been improved to total update time

𝑚𝑛

9/10+𝑜 (1)

log𝑊

by the

breakthrough results of Henzinger, Forster, and Nanongkai [

Their algorithm is Monte Carlo and works against an oblivious

adversary (an adversary that xes the entire graph sequence of up-

dates in advance). Whilst presented only in the decremental setting,

this algorithm appears to extend to the incremental setting.

Very recently, Probst and Wul-Nilsen [

] improved upon this

result and presented a randomized data structure for decremental

directed SSSP against an oblivious adversary with total update time

Some algorithms allow vertex updates, therefore the number of vertices might be due

to change.

𝑂 (min{𝑚𝑛

3/4

log𝑊 , 𝑚

3/4

𝑛

5/4

log𝑊 })

. They also give a Las Vegas

algorithm with total update time

𝑂 (𝑚

3/4

𝑛

5/4

log𝑊 )

that works

against an adaptive adversary. They also get slightly improved

bounds for unweighted decremental graphs. We point out, however,

that their data structure cannot return approximate shortest paths

to the adversary as it would reveal the random choices. Further,

unlike the data structure by Henzinger et al., their approach cannot

be extended to the incremental setting since it relies heavily on

nding ecient separators and on maintaining the topological

order of vertices in the graph.

In summary, all known partially dynamic algorithms for directed

graphs that are faster than ES-trees are randomized, and their amor-

tized update time even for 𝑚 ∼ 𝑛

insertions is at least some poly-

nomial. Moreover, it is unclear how to extend the result from [

] to

the incremental setting. This is in stark contrast to the undirected

setting where the currently best bounds for decremental graphs

[

] extend straight-forwardly to incremental graphs. This

is reminiscent of the connectivity problem, which in undirected

incremental graphs is almost trivial while the problem of main-

taining strong-connectivity in directed graphs is solved to near-

optimality in decremental graphs [

] but still not fully understood

in incremental graphs [

]. We believe that understand-

ing strong-connectivity might be a preliminary for understanding

single-source shortest paths in directed graphs.

Lower bounds.

Conditional lower bounds for partially dynamic

SSSP were rst studied by Roditty and Zwick [

]. They showed

that in the weighted setting, APSP can be reduced to partially

dynamic SSSP with

𝑂 (𝑛

)

updates and queries, thus implying that

the amortized query/update time must be

𝑛

1−𝑜 (1)

, unless APSP can

be solved in truly subcubic time (i.e. 𝑛

3−𝜖

for constant 𝜖 > 0).

For unweighted SSSP in the partially dynamic setting, there is a

weaker lower bound [

]: Under the Boolean Matrix Multiplication

(BMM) hypothesis, any combinatorial incremental/decremental

algorithm for unweighted SSSP requires amortized

𝑛

1−𝑜 (1)

up-

date/query time. Abboud and Vassilevska Williams [

] modied

the [

] construction to give stronger lower bounds even for the un-

weighted

𝑠

𝑡

SP problem: any combinatorial incremental/decremental

algorithm for unweighted

𝑠

𝑡

SP requires either amortized

𝑛

1−𝑜 (1)

update time or 𝑛

2−𝑜 (1)

query time.

We point out that the unweighted SSSP lower bounds of [

] are weak in two ways: (1) they are only for combinatorial

algorithms, and (2) they hold only when the number of edges

𝑚

quadratic in the number of vertices, so in terms of

𝑚

, the update

lower bound is merely

𝑚

0.5−𝑜 (1)

. Henzinger et al. [

] aimed to

rectify (1). They introduced a very believable assumption, the OMv

Hypothesis, which is believed to hold for arbitrary algorithms,

not merely combinatorial ones. Henzinger et al. [

] showed that

under the OMv Hypothesis, incremental/decremental

𝑠

𝑡

SP (in the

word-RAM model) requires

𝑚

0.5−𝑜 (1)

amortized update time

𝑚

1−𝑜 (1)

query time, thus obtaining the same lower bounds as under

the BMM Hypothesis, but now for not necessarily combinatorial

algorithms.

Similar to the lower bounds based on BMM, the Henzinger et al. [

] lower bound on

the update time is

𝑛

1−𝑜 (1

)

but the number of edges in the construction is quadratic in

𝑛, so that in terms of 𝑚, the lower bound is 𝑚

0.5−𝑜 (1)

154

New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs STOC ’20, June 22–26, 2020, Chicago, IL, USA

1.3 Results

Our main result is a new elegant algorithm for the incremental

SSSP problem in weighted digraphs.

Theorem 1.1. There is a deterministic algorithm that given a

weighted digraph

𝐺 = (𝑉, 𝐸)

subject to

edge insertions and weight

decreases, a vertex

𝑠 ∈ 𝑉

, and

𝜖 >

0, maintains for every vertex

𝑣

an estimate

𝑑 (𝑣)

such that after every update

𝑑 (𝑠, 𝑣) ≤

𝑑 (𝑣) ≤

(

+ 𝜖)𝑑 (𝑠, 𝑣)

, and runs in total time

𝑂 (𝑛

log𝑊 /𝜖

2.5

+ Δ)

. Path

queries are answered take time linear in the number of path edges.

Our result is the rst deterministic partially dynamic directed

SSSP algorithm to improve over the long-standing

𝑂 (𝑚𝑛)

time

bound achieved by the ES-tree [

]. Our result is essentially optimal

for very dense graphs, and is the rst algorithm with essentially

optimal update time for any density in directed graphs. Furthermore,

our algorithm further improves on the randomized

𝑚𝑛

0.9+𝑜 (1)

log𝑊

time algorithm of Henzinger et al. [

] if

𝑚 = 𝜔 (𝑛

1.1

)

(their paper

presents only in the decremental setting, but it appears to extend

to the incremental setting as well).

A further strength of our algorithm is that in addition to re-

turning distance estimates, it can also return the corresponding

approximate shortest paths, i.e. it is path-reporting. Previously

known path-reporting dynamic SSSP algorithms in the directed

setting except for the ES-tree are randomized against an oblivious

adversary. In this setting, we in fact also improve for undirected

graphs where the only path-reporting deterministic (or adaptive)

algorithms are the

𝑂 (𝑚

7/4

𝑛

1/4

)

update time algorithm by Hen-

zinger, Forster and Nanongkai [

], and the randomized algorithm

for decremental graphs by by Chuzhoy and Khanna [

] which has

update time

𝑛

2+𝑜 (1)

and which even more recently derandomized

[

]. However, the latter algorithm works only in the restricted

setting of vertex deletions and requires 𝑛

1+𝑜 (1)

query time.

Our second contribution includes several new ne-grained lower

bounds for the partially dynamic SSSP and

𝑠

𝑡

-SP problems in un-

weighted undirected graphs. The only known conditional lower

bounds for partially dynamic SSSP and

𝑠

𝑡

-SP in unweighted graphs

give an update time lower bound of

𝑚

0.5−𝑜 (1)

. While the ES-tree

data structure does achieve an

𝑂 (

√

𝑚)

amortized update/query

time upper bound whenever

𝑚 = Θ(𝑛

)

, this upper bound does not

improve for lower sparsities. This motivates the following question:

Is partially dynamic SSSP solvable with amortized update/query time

𝑂 (

√

𝑚) for all sparsities 𝑚?

Our work answers this question with the tools of ne-grained

complexity. Our rst result is based on the following

𝑘

-Cycle hy-

pothesis (see [11, 48]).

Hypothesis 1.2

(

𝑘

-Cycle Hypothesis)

In the word-RAM model

with

𝑂 (log𝑚)

bit words, for any constant

𝜖 >

0, there exists a constant

integer

𝑘

, so that there is no

𝑂 (𝑚

2−𝜖

)

time algorithm that can detect

a 𝑘-cycle in an 𝑚-edge graph.

Our rst result says that under the

𝑘

-Cycle Hypothesis, if the

preprocessing time of a partially dynamic

𝑠

𝑡

-SP algorithm is sub-

quadratic

𝑂 (𝑚

2−𝜖

)

for

𝜖 >

0, then in fact the algorithm cannot

achieve truly sublinear,

𝑂 (𝑚

1−𝜖

′

)

amortized update and query time

for any

𝜖

′

0. This is a quadratic improvement over the previous

known lower bounds, and it is also tight, as trivial recomputation

achieves amortized update/query time 𝑂 (𝑚).

Theorem 1.3. Under Hypothesis 1.2, there can be no constant

𝜖 >

such that partially dynamic

𝑠

𝑡

SP in undirected graphs can be solved

with

𝑂 (𝑚

2−𝜖

)

preprocessing time, and

𝑂 (𝑚

1−𝜖

)

update and query

time, for all graph sparsities 𝑚.

A consequence of the proof of Theorem 1.3 above is that (under

Hypothesis 1.2) the

𝑂 (𝑚𝑛)

total update time achieved by ES-trees

is essentially optimal, also when

𝑚

is close to linear in

𝑛

. Recall

that the OMv lower bound only showed this for

𝑚 = Θ(𝑛

)

. While

the above lower bound is tight, it only holds for truly subquadratic

preprocessing time. Recall that the only known lower bound for

arbitrary polynomial preprocessing time is the

𝑚

0.5−𝑜 (1)

bound

under OMv.

We rst develop an intricate reduction that shows that an ef-

cient enough partially dynamic

𝑠

𝑡

SP algorithm can be used to

solve the 4-Clique problem. Then we dene an online version of

4-Clique, similar to OMv that is plausibly hard even for arbitrary

polynomial time preprocessing. We show that if 4-Clique requires

𝑛

𝑐−𝑜 (1)

time for some

𝑐

, then any algorithm for partially dynamic

𝑠

𝑡

SP with

𝑂 (𝑚

𝑐/2−𝜖

)

preprocessing time for some

𝜖 >

0, must have

update or query time at least

𝑚

(𝑐−2)/2−𝑜 (1)

. 4-Clique is known to

be solvable in

𝑂 (𝑛

3.252

)

time [

], and if the matrix multiplication

exponent

𝜔

2, the best running time for 4-clique would still be

truly supercubic. Thus, the update time in our conditional lower

bound,

𝑚

(𝑐−2)/2−𝑜 (1)

is polynomially better than

𝑚

0.5−𝑜 (1)

, as long

𝜔 >

2. Recent results [

] show that the known techniques for

matrix multiplication cannot show that 𝜔 is less than 2.16.

While the connection between clique detection and

𝑠

𝑡

SP is

interesting in its own right, it does not resolve the limitation on

the preprocessing time of our previous lower bound. To x this,

we introduce an online version of 4-Clique, generalizing the OMv

(actually the related OuMv [44]) problem:

Denition 1.4

(OMv3 problem)

In the OMv3 problem, we are given

𝑛 ×𝑛

Boolean matrix

𝐴

that can be preprocessed and then

𝑛

queries

consisting of three length

𝑛

Boolean vectors

𝑢, 𝑣, 𝑤

have to be answered

online by outputting the Boolean value

𝑖,𝑗,𝑘

(𝑢

𝑖

∧𝑣

𝑗

∧𝑤

𝑘

∧𝐴[𝑖, 𝑗] ∧𝐴[𝑗, 𝑘] ∧𝐴[𝑘, 𝑖]).

One can think of

𝑢, 𝑣, 𝑤

as giving the neighbors of an incom-

ing vertex

𝑞

in the three partitions of a tripartite graph, and then

the Boolean value just answers whether

𝑞

would be part of a 4-

Clique if it were added to the graph. This is the natural extension of

Henzinger et al.’s OuMv problem. OMv3 is easy to solve in

𝑂 (𝑛

𝜔

)

time per query by computing whether the neighborhood dened

𝑢, 𝑣, 𝑤

contains a triangle. We hypothesize that there is no bet-

ter algorithm, even if one is to preprocess the matrix in arbitrary

polynomial time:

Hypothesis 1.5

(OMv3 Hypothesis)

Any algorithm solving OMv3

with polynomial preprocessing time needs

𝑛

𝜔+1−𝑜 (1)

total time to

solve OMv3 in the word-RAM model with 𝑂 (log 𝑛) bit words.

Using this Hypothesis, using essentially the same reduction

as from 4-Clique to

𝑠

𝑡

SP, we obtain plausible conditional lower

155

剩余13页未读，继续阅读

评论收藏

内容反馈

爱吃番茄great

粉丝: 27
资源: 296

增量式单源最短路径1

评论0

最新资源

增量式单源最短路径1

评论0

单源最短路径

30-图算法-单源最短路径-Dijkstra1

DijkstraAndAstar.rar

ACM比赛模板

清华内部ACM培训资料_各类经典算法

河海大学研究生入学考试GIS专业真题

单源最短路径问题

单源最短路径求解

单源最短路径的课设

Dijkstra求单源最短路径

单源最短路径——算法

数据结构与算法（Java版）

地理信息系统算法基础.rar

单源最短路径实验报告

单源最短路径.docx

Dijstra算法单源最短路径

SPFA算法求单源最短路径

DJK单源最短路径

数据结构与算法 （JAVA语言版）

数据结构和算法Java

数据结构java版

最新资源

数据结构与算法（JAVA语言版）