Find edge-disjoint paths (not the number, the paths)

Question

given a directed graph we can use edmonds-karp or ford-fulkerson algorithms to find the maximum number of edge disjoint paths in a directed graph.

Say there are k edge-disjoint paths in G, how can one find the actual paths in polynomial time? My best choice is BFS and once a path is found mark those edges as used.

Thanks a lot!

Answer 1

You can use flow decomposition. It goes like this:

1. Let's run a depth-first search from the start node and ignore the edges that have a zero or a negative flow.

2. Once you reach the terminal node, subtract one from the flow through all edges on the path from the start node to the terminal one and print them (they form a path).

3. Keep doing this as long as the terminal node is reachable.

Each run uses a polynomial amount of time and finds and removes one path from the graph. The number of disjoint paths is clearly polynomial, so this algorithm has a polynomial time complexity.

You can also use breadth-first search, too (you still need to ignore edges with a non-positive flow).