I am aware that the problem has been discussed here more than once. However, I need to find the maximum number K of vertex-disjoint paths in a directed graph with a running time of |V| x |E|.

I know the algorithm of transforming each vertex into v_in, v_out and adding an edge with capacity 1 from v_in to v_out and for each pair of vertices (u,v) add an edge with capacity 1 from u_out to v_in and then compute the max flow in this network. However, after my calculations this algorithm takes O(E) preprocessing + O(VE^2) or O(V^2E) for max flow. Am I doing something wrong?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.