All pairs edge disjoint paths Split each edge into two edges with different directions Set the capacity of each edge to be 1 Find the maximum of max flow between every pair of nodes 0/1 0/1 0/1 0/1 1/1 1/1 1/1 0/1 0/1 0/1 0/1 1/1 1/1 0/1 1/1 1/1 M 0/1 0/1 1/1 0/1All pairs edge disjoint paths • Split each edge into two edges with different directions • Set the capacity of each edge to be 1 • Find the maximum of max flow between every pair of nodes 1/1 1/1 1/1 1/1 0/1 0/1 1/1 1/1 1/1 0/1 0/1 0/1 1/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1