K mutually exclusive routes in a graph

Question

Input: Graph G (assume all edges have unit weights), source-destination vertex pairs (X1, Y1) , (X2 Y2) , ..., (Xk, Yk) (all of them are distinct).

Output: Routes R1 (from X1 to Y1), R2(from X2 to Y2), ... , Rk (from Xk to Yk) such that R1, R2, ..., Rk do not share any vertices between them. No need to optimize the route length.

What algorithm to use? What would be the complexity of this problem? I need a theoretically strong solution, not a heuristics works-most-of-the-time solution.

The most obvious solution is to assign each free vertex(not in X1, X2, .. Xk, or Y1, Y2, ..., Yk) to one of the k paths and see if they actually form paths in the required way. There are possible n^k assignments ( (n-2k)^k to be more precise). Can we do better? What if we assume the graph to be a 2d grid structure? (Equivalent to solving https://play.google.com/store/apps/details?id=com.bigduckgames.flow game, but without fill every square requirement).

Answer 1

You can find one of the possible solutions in this paper: "The disjoint paths problem in quadratic time" by Ken-ichi Kawarabayashi, Yusuke Kobayashi, Bruce Reed (pdf).

This solution is not trivial but efficient - only O(N²) time complexity, where N is the number of vertices. It is efficient only if K is a small constant.

---

It is also possible to solve this as Multi-commodity flow problem. But I doubt any multi-commodity-specific algorithm is efficient enough. Because general multi-commodity flow problem (when flow for at least one commodity is greater than one) is NP-hard.

It is unlikely that this is solvable as a single-commodity flow problem. For example, here is a counter-example to the following proposal:

...limiting the S to X2 and T to Y2 edges to capacity 0.5? If there is a pair of disjoint routes with the required match-up, then it is possible to have a total flow of 1.5 from S to T... I am sure this method will give an accurate report of whether there is a set of disjoint paths.

                                           

It is easy to find a flow of capacity 1.5 (this flow is shown on diagram). But there is no way to connect both (green and red) pairs of vertices with disjoint paths.

Answer 2

You can use MaxFlow to solve this problem. If you don't familiar with Flow, you can read some material about it.

Algorithm

1. Make one super sink vertice S and one super target vertice T. link some new edges S -> X1, S -> X2, Y1 -> T, Y2 -> T....., S -> Xk, Yk -> T, and set the capacity of each pair of edges 1, 0.75, 0.5 .....
2. Seperate each vertice p into two new vertices p' and p", linked the p' and p" with a new edge whose capacity is also 1.
3. Run MaxFlow from S to T, and save the information of the flow-path. It' obviously that the maxflow of this new graph is 2. And the two flow-path is indicating the required route. Because the algorithm always find the max flow, so the final flow path must be X1 -> Y1, X2 -> Y2 ... Xk -> Yk.

Proof

Because we seperate each vertice and replaced by one edge whose capacity is 1, so each vertice in the original graph can be traversal by one flow. In other word, it also means each vertice can belong to one path.

Extend

If you want to minimize the total length of two paths, you can just extend the algorithm. Add each edge in the new graph one property: cost. The cost for the edges from origin graph will be 0; and the cost for that new edges indicating the seperate vertices will be 1. You can run Min-Cost-Max-Flow algorithm, and get the required information.

Complexity

The complexity of the MaxFlow is O(N * N * M) by using Dinic algorithm. And the complexity of Min-Cost-Max-Flow is also approximately O(N * N * N).

Answer 3

I don't have a full solution, but I do have a reduction that can be used as a first step. First, decompose the graph into its biconnected components. This decomposition identifies all the cut vertices, a vertices that, if removed, disconnects the graph into two components. For each cut vertex, the source and destination vertex pairs are either on the same side of the cut, as a non-split pair, or on opposite sides of the cut, as a split pairs. (If the cut vertex is also either source or target, count it as a split pair.)

• If there are two or more split pairs for any cut vertex, the problem has no solution, because both paths would have to pass through the cut vertex. (This is a generalization of the quincunx graph example in my comment above.)

• If there are no split pairs, then the problem resolves into two smaller problems, one on each of the components. The solution is the combination of a solution on each of the smaller ones.

• If there is exactly one split pair, then you reduce the problem to pair of smaller problems, one on a related version of each of the components, where the cut vertex is duplicated between the graphs. Suppose the cut vertex is X_1 in some component; in that component label the duplicated cut vertex Y_1. Vice-versa for the other component. As before, the solution is a combination of that of the two smaller ones.

The essence of this solution is the pigeonhole principle, since two paths can't go through one point. Moving up one step, three points can't go through two points. This leads immediately to examining triconnected components and using SPQR trees. From this structure, you can enumerate all two-point cuts. As before divide, the vertices into two sets and proceed analogously, except that you have to consider all permutations of the split pairs. The subproblems are now all on triconnected components.

You can see where this leads. I don't know if SPQR trees have been generalized to higher degrees of connectivity. Even if they have been, you can expect combinatorial explosion in general. And all this leads to a hard problem.

---

At first, I suspected the problem was tractable on planar graphs. It's not; see the paper referenced above. It remains NP-complete.

Given the above algorithm, you can assume a problem on a biconnected graph. The difference here is that planar graphs only have "local" edges (seen by embedding the graph on a sphere); "remote" edges would have to cross others. That means that behavior of minimal cut sets is much more well behaved. But not enough more well behaved to make the problem work.