读论文系列 #4——stretch 2 APSP 的最新进展

YeahPotato · 2025-09-15 00:11:05 · 算法·理论

更好的观感见博客。

引入

paper，APSP 近似的一些其他情形 sys 的笔记

问题

对于 APSP 问题，记 \pi(u,v) 为最短路，d(u,v) 为 \pi(u,v) 的长度。如果有一个算法能得到近似 \delta(u,v) 满足 d(u,v)\le\delta(u,v)\le m\cdot d(u,v)+a，那么就称为一个 (m,a) 近似。a=0 时称为 stretch m 近似，m=1 时称为 surplus a 近似，下文中简写作 m 近似与 +a 近似。

distance oracle 指的是以常数时间（？）回答一组 \delta(u,v) 的算法，这样避免了输出的 \Omega(n^2) 界，可以（在稀疏图中）做到平方以下。

下文中“非确定性算法”指必然正确且以高概率在对应时间内运行结束的算法；期望时间算法可以并列运行 \log 个，通过 Chernoff bound 变成非确定性。

一些上下界

1. 大家都知道准确的带权 APSP 被猜想是 \tilde\Omega(n^3) 的，而不带权的可以归约矩乘做。
3. 当 m=\Theta(n) 时，oracle 有 \tilde\Omega(m^{5/3}) 的时空下界（基于一些 fine-grained complexity 的猜想）。
4. 已知无向无权图的 (2,1) 近似可以 \tilde\Omicron(n^2)，所以现在不确定的是，无权/有权的 2 近似能不能 n^2，以及 oracle 能不能 sub-n^2。

无权

已知结果

1. [DHZ00] 存在非确定性与确定性的算法，能在线性时间内得到一张图中所有度 \ge s 点的 hitting-set，大小 \tilde\Omicron(n/s)。
2. [DHZ00] 无权无向图的 +\log n 近似 APSP 可以在时间 \tilde\Omicron(n^2) 内求解。
3. [BK10] 非负整数权无向图的 2 近似 APSP 可以在时间 \tilde\Omicron(mn^{0.5}+n^2) 内用非确定性算法求解。
4. [Zwi02] \langle n,n^r,n\rangle 的 (\min,+) 矩阵乘法的 1+\epsilon 近似能在时间 \tilde\Omicron(n^{\omega(r)}\epsilon^{-1}\log W) 内求解，其中 \omega(r) 是 \langle n,n^r,n\rangle 的普通矩阵乘法复杂度，原矩阵值域为 [W]\cup\set{\infty}。

整体处理思路

我们希望找到一些关键点，只求关键点到全体的最短路，将必经关键点的最短路作为近似结果。

1. 如果 \pi(u,v) 经过大度点，可以通过 hitting-set 的套路做到 +2 近似（优于 2 近似）。
   1. 对于 hitting-set S 内的点，做 MSSP。
   2. 求形如 \delta(u,v)=\min_{x\in S}\set{d(u,x)+d(x,v)} 的 (\min,+) 矩乘。
2. 否则是稀疏图上的 APSP。

这里 1.1 中的 MSSP 我们固定用 Dijkstra，那么剩余的就是需要指定矩乘和稀疏图 APSP 的算法。如果取度数阈值为 n^{1-r} 的话，那么时间就是

接下来认为 m=\Omicron(n^2)。

倍增优化

考虑进一步分治。如果 \pi(u,v) 经过度数在 [a,b) 内的点，那么用第 1 部分的方法，Dijkstra 是点数 n/a，边数 nb。因此如果我们取一列区间

分别交给第 1 部分做，时间就降为

近似归约

我们知道 (\min,+) 矩乘是没法做的，所以只能近似。如果有 (m,a) 近似的矩乘，那么第 1 部分整体就是 (m,a+2m) 近似。由于只需考虑 d\ge 2 的情况，(m,a+2m) 近似就必然是 (2m,a) 近似。

于是根据已知 4，第 1 部分存在一个 2+\epsilon 近似，时间关于 \epsilon^{-1} 线性。 取 \epsilon=1/\log n。如果 d(u,v)<\log n，2+\epsilon 近似相当于 2 近似；否则调用已知 2。

套用算法

1. 全部用朴素做法，取 r=0.5 得 \tilde\Omicron(n^{2.5})。
2. 第 2 部分用已知 3，就是 n^2+n^{2+r}+n^{2.5-r}，取 r=0.25 得 \tilde\Omicron(n^{2.25})。
3. 上一条基础上，第 1 部分用已知 4，就是 n^2+n^{\omega(r)}+n^{2.5-r}，可以平衡到 \tilde\Omicron(n^{2.032})。
4. 还已知一个 parameterized 的算法是做 +k 近似的，与矩乘结合得到一个 (1+\epsilon,k) 近似算法。

有权

已知结果

1. [TZ01], [TZ05] 对于“密度” p，存在非确定性算法能在 \tilde\Omicron(m/p) 的时间内得到一组大小为 \tilde\Omicron(np) 的关键点集并计算出每个束内的基本信息，满足束和簇的大小均不超过 \tilde\Omicron(1/p)。
2. [EN22] 非负整数权无向图的 1+\epsilon 近似 MSSP 能在时间 \tilde\Omicron(m^{1+\omicron(1)}+n^{\omega(r)}\epsilon^{-\Omicron(1)}\log W) 内求解，其中起点集合大小 n^r，边权值域 [W]。

整体处理思路

同样取一些关键点，但是现在我们考虑这样的结构：对于点 u，找到与它距离最近的关键点 p(u)，将距离比 d(u,p(u)) 小的点，和 p(u) 一起组成 u 的束（branch）B(u)。束的逆称为簇 C(v)=\set{u\mid v\in B(u)}。

（蓝色点表示最近关键点，称为“枢轴”）

通过束的定义以及三角不等式，可以放缩得到一些近似。首先有个 3 近似：若 v\notin B(u)，则

若 v\in B(u)，已知 1 的做法里能算出 u 到 B(u) 各点的最短路，所以就不用管了。

我们现在称 \pi(u,v)\setminus(B(u)\cup B(v)) 中的点为“束间点”。

（情况 1）如果 \pi(u,v) 有束间点 x，那么 d(u,x),d(x,v) 中至少有一个 \le d(u,v)/2，不妨设为 d(u,x)，则

剩余的情况（情况 2）是关注的重点。

暴力做法

若 \pi(u,v) 无束间点，那么 \pi(u,v) 一定形如 u\rightsquigarrow u^\prime\to v^\prime\rightsquigarrow v，其中 u^\prime\in B(u)，v^\prime\in B(v)。这样的 (u,u^\prime,v^\prime,v) 的数量是 m|C|^2=\tilde\Omicron(m/p^2)。总的时间：

1. 情况 1 从关键点出发跑 Dijkstra，\tilde\Omicron(nmp)。
2. 情况 2 暴力更新，\tilde\Omicron(m/p^2)。
3. 两类情况取 \min，\Omicron(n^2)。

我们可以做一个 oracle，省去 3，取 p=n^{-1/3} 得 \tilde\Omicron(mn^{2/3})。

注意到如果暴力做无束间边（\tilde\Omicron(n/p^2)），而恰有一条束间边的情况归到情况 1，可以得到一个 \tilde\Omicron(nm^{2/3}) 的 (2,\max w) 近似。

稠密情况

对于情况 1 用已知 2 的 1+\epsilon/2 近似，得到 2+\epsilon 近似。

对于情况 2，分两步做（各束边指的是，每个 u 向 B(u) 内点连边权为距离的边）：

（② 对应第 1 次 Dijkstra，③ 对应第 2 次）

1. 对每个 v^\prime，保留其邻边与各束边，跑 Dijkstra，得到 d^\prime(v^\prime,u)。
2. 对每个 u，保留各束边，建边 (u,v^\prime) 权 d^\prime(v^\prime,u)，跑 Dijkstra。

时间均为 \tilde\Omicron(n^2/p)，这样算出来的是准确 SP。若 p=n^{r-1}，则总时间为

可以平衡到 n^{2.213}。

注意到建束内边对非稠密图过于激进了，接下来的做法进行了进一步的平衡。

倍增优化

相比情况 2，情况 1 更容易优化。注意到有权图的“束”结构与无权图的简单的 hitting-set 结构有以下共同点：

1. 通过一个中介点 x，三角不等式放缩多出两倍的 d(x,?)（在无权图中就是 +2），得到 2（或 2+\epsilon） 近似。
2. 关键点出发全图跑 MSSP，这使我们无法不受限制地增加关键点数，否则这部分会成为瓶颈。

（对数尺度；每个格子的右边界为该格算法的关键点密度）

在无权图中，通过考虑子问题：经过度数在 [a,b) 间点的最短路，对其分治，得到倍增做法，减少了边数，使得 Dijkstra 总时间由 mn^r 降至 n^2。在有权图中，模仿这一思路：考虑关键点集 S_{i+1}\subset S_i，现在需要对于所有 (u,v) 满足 \pi(u,v) 在 S_{i+1} 下无束间点，而在 S_i 下有束间点的情况，去求 d(u,v) 的近似。同样，我们的目标是减少关键点出发 MSSP 的边数，同时保证近似的论证不失效。

仍然假定 d(p_i(u),u)\le d(u,v)/2。回顾不等式 (1)：

实际不需要准确求出 d(p_i(u),v)，而只求一个近似的 \delta(p_i(u),v)\in[d(p_i(u),v),d(p_i(u),u)+d(u,v)] 即可。进一步，如果 \pi(u,v) 形如 u\rightsquigarrow u^\prime\to x\rightsquigarrow v，其中 u^\prime\in B_{i+1}(u)，x\notin B_{i+1}(u)，那么可以拆成

建立这样的图：p_i(u) 向所有与 B_{i+1}(u) 相邻的点（及上述 x 这样的点）连边，边权

另外对于所有的点 v，将与 v 相邻的权 \le d(v,p_{i+1}(v)) 的边加入。跑 Dijkstra。设 \pi(x,v)=x\to\cdots\to v_1\to v。由于 x\in B_{i+1}(v)，故 (v_1,v) 是保留的；由于 d(v_1,p_{i+1}(v_1))+w(v_1,v)\ge d(v,p_i(v))，故 x\in B_{i+1}(v_1)，所以 (v_2,v_1) 也保留，以此类推。

求 \delta^\prime 所需的时间是

我们相当于把菊花形的各束边改成了第二类边，它们的数量这么考虑：如果 S_{i+1} 是以 q 的概率选点的话，那么对于不在 S_{i+1} 中的点，将其邻边按边权从小到大扫描，每次有 q 的概率把剩余的扔掉。因此期望边数为 \sum (1-q)^i\le 1/q，用 Chernoff bound 一类的东西放缩下就是高概率 \tilde\Omicron(n/q)。从这个意义上来看，束结构也是限制度数的，基本打通了无权和有权的思想。

因此总的复杂度是

考虑关键点集包含链 V=S_0\supset S_1\supset\cdots\supset S_k。其中 S_i 中的每个点以 1/2 概率出现在 S_{i+1} 中。如果 \pi(u,v) 在 S_k 的下仍有束间点，那么就只能用原来情况 1 的做法，从 S_k 出发跑 MSSP；否则一定存在某个 S_{i}-S_{i+1} 交界，就用上面的方法。设 k=(1-r)\log_2n，则 |S_k|=\tilde\Theta(n^r)，时间为 \tilde\Omicron(mn^{1-r}+n^2+T_1(n,m,n^r))，T_1 是 MSSP 的复杂度。

实际实现时，第一类边权的 \min 只需要拿 B_k(u) 内所有点的邻边去松弛就行，那么为了保证 |C_k(u)| 的大小，需要强制往 S_k 里加已知 1 里的构造，不过这个不影响复杂度。总的做法：

1. 求出 \set{S_i}，建出束结构。
2. 对于每个 u，每个 i，每个 B_k(u) 内点的邻边，更新 \delta^\prime(p_i(u),x)。
3. 对于每个 p_i(u) 建图跑 Dijkstra。
4. 对于 S_k 在原图上跑 MSSP。
5. 对每个 (u,v) 求答案。

套用算法

1. MSSP 直接用 Dijkstra，时间 mn^r，取 r=0.5 得 \tilde\Omicron(mn^{0.5}+n^2)，这就是 [BK10]。
2. MSSP 用已知 2，这样是 2+\epsilon 近似，是 mn^{1-r}+n^2+n^{\omega(r)}\epsilon^{-\Omicron(1)}\log W，对于稠密图的平衡结果，和稠密情况那个一样。