optimization - 所有对最大不相交路径算法

Question

假设在一个无向图中有多个源目的地对。我想为多对生成不相交的路径。这样的问题的复杂性是什么？是否有任何多项式启发式方法可以找到这些对的边缘不相交路径？（即 s1 和 d1 之间的路径不应与 s2 和 d2 之间的路径有任何公共边）

Answer 1

这看起来像是多商品流问题的变体： http ://en.wikipedia.org/wiki/Multi-commodity_flow_problem

将每个源/汇对视为一种新商品，并赋予边缘单位权重以强制执行不相交的路径。现在在文献中搜索具有单位容量的此类 MCFP 的近似值。

Answer 2

您的问题是 NP-hard，即使对于两个源和两个接收器的情况也是如此。如果您不再关心哪个源与哪个接收器匹配，它就会成为多项式可解的。