输入:图形G(假设所有边都具有单位权重)，源-目标顶点对(X1，Y1)，(X2 Y2)，...，(Xk，Yk)(它们都是不同的)。
输出:路由R1(从X1到Y1)，R2(从X2到Y2)，...，Rk(从Xk到Yk)，以使R1，R2，...，Rk之间不共享任何顶点。无需优化路由长度。
使用什么算法？这个问题的复杂性是什么？我需要一个理论上很强的解决方案，而不是启发式的最常用的解决方案。
最明显的解决方案是将每个自由顶点(不在X1，X2，.. Xk或Y1，Y2，...，Yk中)分配给k条路径之一，并查看它们是否实际上以所需的方式形成了路径。可能有n个k分配(更精确地说是(n-2k)^ k个)。我们可以做得更好吗？如果我们假设图形为2d网格结构怎么办？ (等效于解决https://play.google.com/store/apps/details?id=com.bigduckgames.flow游戏，但没有满足每个平方的要求)。
最佳答案
您可以在本文中找到一种可能的解决方案:"The disjoint paths problem in quadratic time" by Ken-ichi Kawarabayashi, Yusuke Kobayashi, Bruce Reed(pdf)。
该解决方案不是简单的，而是有效的-仅O(N2)时间复杂度，其中N是顶点数。仅当K为一个小常数时，它才有效。
也可以将其解决为Multi-commodity flow problem。但是我怀疑任何特定于多商品的算法是否足够有效。因为一般的多商品流问题(当至少一种商品的流大于一个时)是NP难的。
作为单一商品流动问题，这不太可能解决。例如，这是以下提议的反例:
容量为1.5的流量很容易找到(该流量如图所示)。但是，无法通过不相交的路径来连接(绿色和红色)两个顶点对。