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).