How to find all equals paths in degenerate tree from specific start vertex?

What algorithms efficiently find a largest possible set of paths from u to v such that each pair of paths in the set is intermediate-vertex-disjoint?

• Let G be an undirected graph, and let u and v be two distinct, nonadjacent vertices in G. Two paths from u to v are intermediate-vertex-disjoint if the only vertices that these paths share are u and v. Give an algorithm that efficiently finds a largest possible set of paths from u to v such that each pair of paths in the set is intermediate-vertex-disjoint.  What is the time complexity in terms of n, m and r(u, v), where r is the maximum number of such paths in a set. (Hint: Think about the maximum flow problem.) This is a question, I found somewhere but dint know how to approach it using max-flow.

• Answer:

  You can solve this using max flow. First you split each node x in two nodes x1 and x2. All edges going to x now go to x1 and all edges leaving from x now leave from x2. Each of these edges will have capacity 1. You also add for each x an edge from x1 to x2 of capacity 1. Now you can run max flow from u2 to v1. The resulting max flow gives you the number of vertex disjoint paths. The solution can't have more than n paths so using Ford-Fulkerson you will get a solution that takes O(nm) time (with n the number of nodes and m the number of edges).