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

引入

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)$ 的，而不带权的可以归约矩乘做。
2. $2-\epsilon$ 近似不弱于 01 矩乘，有向图的任意近似都不弱于 01 矩乘。
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}$ 的话，那么时间就是 $$ \tilde\Omicron(mn^r+T_{1.2}(n,n^r,n)+T_2(n,n^{2-r})) $$ 接下来认为 $m=\Omicron(n^2)$。

倍增优化

考虑进一步分治。如果 $\pi(u,v)$ 经过度数在 $[a,b)$ 内的点，那么用第 1 部分的方法，Dijkstra 是点数 $n/a$，边数 $nb$。因此如果我们取一列区间 $$ [n^{1-r},2n^{1-r}),[2n^{1-r},4n^{1-r}),\cdots $$ 分别交给第 1 部分做，时间就降为 $$ \tilde\Omicron(n^2+T_{1.2}(n,n^r,n)) $$

近似归约

我们知道 $(\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)$，则 $$ d(u,p(u))+d(p(u),v)\le d(u,p(u))+d(p(u),u)+d(u,v)\le 3d(u,v) $$ 若 $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)$，则 $$ d(u,p(u))+d(p(u),v)\le 2d(u,p(u))+d(u,v)\le 2d(u,x)+d(u,v)\le 2d(u,v)\tag{1} $$ 剩余的情况（情况 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. 对每个 $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}$，则总时间为 $$ \tilde\Omicron(n^{3-r}+n^{\omega(r)}\epsilon^{-\Omicron(1)}\log W) $$ 可以平衡到 $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(u,p(u))+\boxed{d(p(u),v)}\le d(u,p(u))+\boxed{d(p(u),u)+d(u,v)} $$ 实际不需要准确求出 $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)$，那么可以拆成 $$ d(p_i(u),u)+d(u,u^\prime)+w(u^\prime,x)+d(x,v) $$

建立这样的图：$p_i(u)$ 向所有与 $B_{i+1}(u)$ 相邻的点（及上述 $x$ 这样的点）连边，边权 $$ \delta^\prime(p_i(u),x)=\min_{u^\prime}\set{d(p_i(u),u)+d(u,u^\prime)+w(u^\prime,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$ 所需的时间是 $$ \sum_{u^\prime}\mathrm{deg}_{u^\prime}|C_{i+1}(u)|=\tilde\Omicron(m|C_{i+1}|) $$ 我们相当于把菊花形的各束边改成了第二类边，它们的数量这么考虑：如果 $S_{i+1}$ 是以 $q$ 的概率选点的话，那么对于不在 $S_{i+1}$ 中的点，将其邻边按边权从小到大扫描，每次有 $q$ 的概率把剩余的扔掉。因此期望边数为 $\sum (1-q)^i\le 1/q$，用 Chernoff bound 一类的东西放缩下就是高概率 $\tilde\Omicron(n/q)$。从这个意义上来看，束结构也是限制度数的，基本打通了无权和有权的思想。

因此总的复杂度是 $$ \tilde\Omicron\left(\frac mq+|S_i|\frac nq+n^2\right)=\tilde\Omicron\left(\frac{mn}{|S_{i+1}|}+\frac{n^2|S_i|}{|S_{i+1}|}\right) $$ 考虑关键点集包含链 $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$，对于稠密图的平衡结果，和稠密情况那个一样。