本文将首先介绍独立路径问题的主要研究问题，接着介绍一些前置知识，最后讲解两篇独立路径问题的论文。

问题定义

独立路径（disjoint path）问题主要有两类基础的研究问题：

1. 给定图G，给定2个不同的顶点s和t，找到从s到t的两条独立路径。

2. 给定图G，给定4个不同的顶点s1,s2,t1,t2，找到一条从s1到t1的路径和一条从s2到t2的路径，这两条路径是相互独立的。

其中：

• 问题1可以扩展为：给定一个点对集合，为此集合中的每对点对都寻找两条独立路径。
• 问题2可以扩展为：给定2k个不同的顶点，找到k条路径，这些路径之间两两相互独立。
• 图可以是有向图或无向图，可以是有权图或无权图，其中若有权，则上述问题可以得到一些变式，如求路径边权总和最小的独立路径。
• “独立”（disjoint）有两类定义，边独立（edge disjoint）或点独立（vertex disjoint）：
• 内部点独立（inner vertex disjoint）：两条路径除了端点外没有公共顶点
• 边独立：两条路径没有公共边
• 点独立：两条路径没有公共顶点

前置知识

两类独立定义问题的相互规约（reduction）

点独立问题和边独立问题可以相互规约[1]：

• 边独立→点独立：线图（line graph）

• 原图G对应线图G‘，则G’上点独立的两条路径在G中对应的两条路径是边独立的



• 点独立→边独立：拆分顶点

• 原图G对应拆分图G‘，则G’上边独立的两条路径在G中对应的两条路径是点独立的

基础问题的最大流算法

基于0-1最大流问题的算法。

问题定义

给定2个不同的顶点s和t，找到从s到t的两条边独立路径

算法

• 给每条边赋容量1，每条边允许通过的流量为整数
• 找到从s到t的一条增广路径p1
• 反向p1，更新图
• 在更新之后的图上找到从s到t的一条增广路径p2
• 抵消p1和p2中相反方向出现的边，剩下的边组成的两条路径即为所求

k顶点割（k-vertex-cut）

k顶点割：k个顶点的集合C，移除这些顶点将导致原图不连通

块-割点图（block-cutpoint graph）

• 割点：某顶点v，移除v将导致原连通图不连通，则v是割点

• 块：二连通分量

• 连通无向图G的块-割点图 **B(G)**：以G的割点和块为顶点，以所有的(c,B)对为边，其中c是块B中的割点

• 块-割点图的顶点**b(v)**：若v是割点，则b(v)是v；若不是，则b(v)对应v所在的块

• 块-割点图的性质：无向图的块-割点图一定是树，且可以通过一次DFS来构造
  

Solving the 2-disjoint paths problem in nearly linear time [2]

问题定义

给定无向图G，给定4个不同的顶点s1,s2,t1,t2，找到一条从s1到t1的路径和一条从s2到t2的路径，这两条路径是相互顶点独立（vertex disjoint）。

算法概述

将general graph上的2-VDPP问题不断规约为2-connected graph、3-connected graph等越来越稠密的图上的2-VDPP问题

算法

general graph → connected graph

此时问题为，给定(G, s1, s2, t1, t2)， 其中G为任意的无向图。

首先，si和ti必须在同一个connected component中才有解。

然后

• 若s1,t1在一个connected component中，s2,t2在另一个connected component中 → solved（分别在各自所在的连通分量中找到一条路径即可）。

• 如果s1, s2, t1, t2都在G的同一个connected component C中，我们可以将G替换呈C → 规约到连通图

connected graph → 2-connected graph

此时问题为，给定(G, s1, s2, t1, t2)， 其中G为连通图。

首先构造G的块-割点图B(G)，令b(s1)为B(G)的根，令qi表示B(G)中从b(si)到b(ti)的路径（注意到B(G)是树，因此qi是唯一的），令v是b(s2)和b(t2)的最近公共祖先（lowest common ancestor）。

考虑q1和q2的相交情况，有如下两种情况：

case 1：q1不会经过v

此情况示意图如图所示，这种情况我们可以直接根据q1和q2构造得到解：

qi是B(G)中的路径，由多段“割点-块-割点”（除了首位可能不是）连接而成，qi对应G中多条路径，这些路径可以通过将qi的每段“割点-块-割点”替换为此块中从割点到割点的路径来得到，由此我们可以得到q1和q2对应的所有路径。

注意到由此扩展得到的p1和p2有可能相交，它们仅当如下情况下可能相交：当v是割点时可能相交于v（这是因为当v是割点时，其邻居都是块，每个块中都包含v），或v在B(G)上的父亲p是割点时可能相交于p（这是因为当v在B(G)上的父亲p是割点时，v是块，v对应的块中包含p），因此在扩展qi时，在搜索块中的割点到割点的路径时对于上述情况注意避开可能的相交点（v或p）。

case 2：q1会经过v

此情况示意图如图所示。

如果v是割点，或者（v不是割点，则b(v)是块，b(v)的孩子都是割点）b(v)的孩子之一同时被q1和q2经过 → 无解（因为从si到ti的所有路径都会经过v或b(v)的这个孩子）。

否则（即v不是割点，且b(v)的所有孩子都不会同时被q1和q2经过），

令si’为qi上在v之前的第一个割点，或者若不存在这样的割点，则令si’为si；令ti’为qi上在v之后的第一个割点，或者若不存在这样的割点，则令ti’为ti，如图所示。

由此问题就规约为在块v中找到从s1’到t1’和从s2’到t2’的两条独立路径的问题（找到了此问题的解之后，将解和qi上从si到si’、从ti到ti’的扩展路径连接起来即得到原问题的解）。

2-connected graph → 3-connected graph

此时问题为，给定(G, s1, s2, t1, t2)， 其中G为二连通图。

注意到此问题不一定有解，比如下图无解。

我们尝试将问题规约为三连通图上的问题，规约的思路为移除掉所有的二顶点割。

移除包含si或ti的2-vertex-cut（2-vertex-cuts C with C ∩ {s1, s2, t1, t2} ≠ ∅）和移除不包含的方法不一样，因此我们分成两步来移除。

step 1：移除所有包含si或ti的2-vertex-cut（2-vertex-cuts C with C ∩ {s1, s2, t1, t2} ≠ ∅）

这一步分为两步：

第一步：移除所有形如{si,v}或{ti,v}、将sj和ti分开的二顶点割，其中v ∈ V{sj , tj} 且 i不等于j

这可以通过添加边(s1, s2), (s1, t2), (t1, s2), (t1, t2)（若不存在则添加）来移除这类二顶点割。

添加这四条边并不会改变原问题的可解性：因为添加的这四条边不会参与p1或p2。

第二步：移除所有其他的包含si或ti的2-vertex-cut

以移除形如{s1,v}的二顶点割为例。

注意到(s1, v)**v is a cutpoint of G − {s1** }即所有形如{s1,v}的2-vertex-cuts，因此，我们首先构造G − {s1} 的块-割点图B(G −{s1})，接下来我们来考虑B(G −{s1})中任意一个割点v。

简单起见，令v是B(G −{s1})的根。若我们移除v，则B(G −{s1})将被分成一些子树（每棵子树都包含且仅包含v的一个孩子）。我们考虑v和t1是否相等的两种情况：

case 1：t1 = v

b(s2)和b(t2)在同一棵子树T中（这是因为在经过了第一步之后，{s1,v}不会分开s2和t2）；

存在另一棵子树T’不包含b(s2)（因为v是割点）；

存在顶点u满足b(u) ∈ T’ 且 (u, s1) ∈ E （因为G是二连通的，对于任意的顶点w满足b(w) ∈ T’，一定存在两条从w到t2顶点独立的路径，其中一条经过v，另一个经过s1），由此可以直接得到解：B(G −{s1})上t1到b(u)的路径扩展后连接(u, s1)得到s1到t1的路径，T中b(s2)到b(t2)的路径扩展得到s2到t2的路径。

case 2：t1 ≠ v

包含b(t1)的子树T至少包含b(t2)和b(s2)中的一个，且如果T仅恰好包含b(t2)和b(s2)中的一个，另一个一定是v（因为边(s2, t1)和(t2, t1)的存在）；

和case1一样，也存在顶点u满足b(u) ∈ T’ 且 (u, s1) ∈ E，由此问题规约为在T对应的图中找从v到t1和从s2到t2的两条独立路径。

令G‘为T对应的图添加边(s1,v)，继续考虑B(G’-{s1})，重复这个过程，直到B中不存在割点。

step 2：移除所有不包含si或ti的2-vertex-cut（2-vertex-cuts C with C ∩ {s1, s2, t1, t2} = ∅）

移除操作

移除掉C之后会将图G分成几个连通分量，{s1, s2, t1, t2} 在同一个连通分量中（因为边(s1, s2), (s1, t2), (t1, s2), (t1, t2)），我们通过移除其他的连通分量来达到移除C的目的。考虑任意一个要移除的连通分量D，移除操作为移除D并为C中两点之间添加边。移除掉所有C之后得到的图为G’。

此操作不会改变问题的可解性：若p1和p2会用到D中的点边，则必然只有其中一条会经过D，且这条路径一定会经过u和v。

由此问题便规约为在G‘上找从s1到t1和从s2到t2的独立路径的问题。

那么接下来我们的问题是，如何找到C和D（2-vertex-cuts C with C ∩ {s1, s2, t1, t2}＝ ∅, and the connected component D separated from {s1,s2,t1,t2} after removing C）。

找到C和D

找D

首先找到这类顶点：存在2-vertex-cuts将其和{s1,s2,t1,t2}分开。

为了方便判断，我们给G添加一个顶点x和边(x, s1), (x, s2), (x, t1), (x, t2) ，得到图Gx，从而有：在Gx中某顶点不满足3-connected to x <-> 在G中存在2-vertex-cuts将其和{s1,s2,t1,t2}分开。因此我们只需寻找在Gx中和x不是三连通的顶点即可。

判断两个顶点之间是否是三连通，可以通过Di Battista和Tamassia提出的一种数据结构[3]来进行：预处理时间复杂度O(m+n)，判断时间复杂度O(1)。

找C

所有不满足3-connected to x的顶点组成一些连通分量，对于每一个这样的连通分量D，如何定位D对应的C？

Lemma: 有且仅有2个” 3-connected to x”的顶点和D有边相连（这两个顶点即把D和{s1,s2,t1,t2}分开的C）

Proof：

• 至少2个（G is 2-connected）

• 至多2个（假设有三个，D中可以找到vertex that 3-connected to x）

因此，step 2即：标记所有not 3-connected to x的顶点，从标记的顶点出发搜索，只访问标记的顶点，此过程中走到的所有顶点构成当前D，且过程中遇到的两个未标记顶点即对应的C，将D移除，未C中两点之间加边

On 3-connected graph

此时问题为，给定(G, s1, s2, t1, t2)， 其中G为三连通图。

注意到此问题不一定有解，比如下图无解。

但是若图是平面图（planar graph），则一定有解[1]，这篇论文的主要思路为最大流方法搜索s1到t1的3条disjoint paths、s2到t2的3条disjoint paths，然后组合它们。

对于非平面图，已有工作已提出对于具有下述性质1的图的线性求解算法[4][5]：

性质1: 3-connected，且不存在3-vertex-cut将{s1,s2,t1,t2}和某些顶点分开（即任意给定一个sz<=4的顶点集合S，一定存在四条disjoint path分别从{s1,s2,t1,t2}出发到达S）。

非平面图必然存在同胚于K5或K3,3的子图K，[4][5]提出的算法分别解决具有性质1且同胚于K5和K3,3的图上的(G,s1,s2,t1,t2)问题，主要思路是搜索{s1,s2,t1,t2}到K的四条disjoint paths，然后借助K连接它们（穷举情况，有些情况下需要修改K或那4条路径）。

因此我们尝试将三连通图上的问题规约为具有性质1的图上的问题，规约的思路为移除掉所有将{s1,s2,t1,t2}和某些顶点分开的三顶点割。

和移除二顶点割类似，我们也是移除掉从{s1,s2,t1,t2}分开的连通分量D，并为C中的三个顶点两两之间添加边。完成此处理后的图为G’，由此问题规约为在G‘上的问题。

接下来的问题是如何找到C和D。这可以通过[6]来完成。同样是添加点边得到Gx，在Gx上某顶点不满足4-connected to x <-> 在G上存在3-vertex-cuts将其和{s1,s2,t1,t2}分开。

A Quick Method for Finding Shortest Pairs of Disjoint Paths [7]

问题定义

给定有向图G，每条边都有非负边权，且每对点之间最多只有一条边；给定一个顶点s；找到s到全图所有其他的顶点v、满足图下条件的两条路径：边独立（edge-disjoint），且两条路径边权总和是所有边独立路径对中最小的。

算法

s到一个v:  来自0-1 minimum-cost maximum-flow算法

• 0-1 minimum-cost maximum-flow问题：给定有向图G，每条边都有非负边权和单位容量，每条边允许通过的流量是整形的（即0或1），其中非负边权表示单位流量流经这条边需要的开销；给定一个源顶点s和一个汇顶点t；从s到t有一至多种最大流，在所有的最大流中找到开销最低的最大流。
• 0-1 minimum-cost maximum-flow的解法：直到不再存在s到t的增广路径，否则持续如下过程：找到从s到t的最短路径（由边权定义的最短），然后反向这条增广路径，流量增加1。
• 前两条增广路径经过抵消之后即s到t的边独立且边权和最小的两条路径

由s到一个点的算法，我们可以得到s到所有v的简单算法：对每对(s,v)运行单点对算法:

1.在G上找s->v的最短路径p1

2.反向p1得到图Gv

3.在Gv上找s->v的最短路径p2

4.抵消p1p2中相反出现的边,得到解

对于上述单点对算法，考虑所有(s,v)对，其中第1步“在G上找s->v的最短路径p1”可以通过Dijkstra算法来完成，而2、3、4步实际上并不需要每对点对单独进行。

设Gv表示反向从s到v的最短路径后得到的图，注意到对于不同的v，Gv是有关联的，基于此本文提出了一种修改版Dijkstra算法，能效果上同时在所有Gv上运行Dijkstra算法，在一次类Dijkstra计算过程后得到所有顶点的**dv(s,v)**（dv(s,v)：Gv上从s到v的最短路径长度）

回顾Dijkstra算法

• 初始:

• d(s)=0, d(v)=∞ if v≠s;

• p(v)=undef;

• 所有顶点未标记

• 重复直到所有顶点被标记,或未标记的顶点d(.)=∞:

• 选d(.)最小的未标记顶点u, 标记u

• 对u的每条邻边(u, w) , If d(u) + c(u, w) < d(w)：d(w) = d(u) + c(u, w) , p(w) = u

修改版Dijkstra: 输出dv(s,v)和对应路径

Gv：反向G中从s到v的最短路径后得到的图

**dv(s,v)**：Gv上从s到v的最短路径长度

初始步骤

1. 搜索以s为根的最短路树T，我们称T中的边为树边，G中其他的边为非树边

2. 修改每条边(u,w)的边权：c’(u, w) = d(s, u) + c(u, w) - d(s, w)

初始步骤2“修改每条边(u,w)的边权”后的图具有如下性质：

• 对于每条边(u,w)，有c’(u, w)>=0；c’(u,w)=0当且仅当(u,w)是树边
• 推论：对于所有顶点v，d(s,v)=0
• 边权修改后的图上的最短路径，是原图中的最短路径
• 这是因为：设p是从u到w的任意一条路径，则c’(p) = c(p) - d(s, w) + d(s, u)，因此任意两条端点相同的路径，它们的路径长度变化了相同的值，因此相同端点之间的所有路径的长度排序是不变的。

搜索步骤

步骤

初始步骤完成后，接下来是和Dijkstra类似的不断从未标记顶点选择顶点扩展和标记的过程。

和Dijkstra会涉及到的过程不一样的一个过程：初始时最短路树T上所有顶点都未标记，不断标记顶点，从T中移除标记顶点，会将T分成多棵由未标记顶点构成的子树（Removing the labeled vertices from the shortest-path tree T divides T into subtrees that span the set of unlabeled vertices. Initially there is only one unlabeled subtree, equal to T.）。此算法将维护这些未标记子树。

• 初始:

• d(s)=0, d(v)=∞ if v≠s;

• p(v)=undef;

• q(v)=undef;

• 所有顶点未标记

• 重复直到所有顶点被标记,或未标记的顶点d(.)=∞:

• u=v或
• u和w在不同的未标记子树中

• 选d(.)最小的未标记顶点v

• 令S表示包含v的未标记子树。标记v，这将把S分成新的未标记子树：一棵包含v的父亲（如果父亲存在且未标记），以及v的每个未标记孩子都有一棵子树

• 对于所有满足u和w都在S中、且满足如下条件的非树边(u,w)：

• 如果d(v) + c(u, w) < d(w)：d(w) = d(v) + c(u, w), p(w) = u, q(w) = v

下面对上述算法步骤进行解释：

(u,w)的选择

• 非树边: 树边cost是0,可以随便走不影响当前路径长度,因此只需要考虑非树边

• 非树边**(v, w)** : 普通Dijkstra扩展v是检查v的所有邻边, 不同Gx上v的邻边集合不一样,但G中v的非树边邻边是所有Gx上v的邻边的公共部分(因为反向的边都是树边)

• u和w在不同的未标记子树中：

• u在parent子树中: 从v沿反向s到v的T上路径走到u

• u在child子树中: 从v沿T走到u

• 设T’是反向s到v的T上路径得到的, 则v沿着T可以走到u：

q的含义

q(w)的含义：从q(w)走到p(w)，只需要沿着T走即可

搜索步骤举例

得到d,p,q之后，构造路径

• 输入：顶点v；数组d,p,q

• 输出：s到v的两条edge-disjoint paths with minimum cost

Step1: 标记 “q vertices”

• x=v

• while(x!=s) mark x; x=q(x)

Step2: track path

• x=v

• while(x!=s) add x to path

• unmark: x有两个前驱，p(x)和x’s parent in T

• if x is marked: unmark x; x=p(x)

• else: x=x’s parent in T

举例：

v: f

mark f, d

f->c->a->s

f->d->s

参考文献

[1] Y. Perl and Y. Shiloach, Finding two disjoint paths between two pairs of vertices in a graph, J. ACM 25 (1978), 1–9.

[2] Torsten Tholey: Solving the 2-Disjoint Paths Problem in Nearly Linear Time. STACS 2004: 350-361.

[3] G. Di Battista and R. Tamassia, On-line maintenance of triconnected components with SPQR-trees, Algorithmica 15 (1996), 302–318.

[4] M. E. Watkins, On the existence of certain disjoint arcs in graphs, Duke Math. J. 35 (1968), 231–246.

[5] Y. Shiloach, A polynomial solution to the undirected two paths problem, J. ACM 27 (1980), 445–456.

[6] A. Kanevsky, R. Tamassia, G. Di Battista, and J. Chen, On-line maintenance of the four-connected components of a graph, Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 1991), pp. 793–801.

[7] J. W. Suurballe, Robert Endre Tarjan: A quick method for finding shortest pairs of disjoint paths. Networks 14(2): 325-336 (1984)