I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost).
For the sake of my question, denote $n=|E|$.
Are there algorithms that will run in $O(n^2)$, or even $O(n\log(n))$, or for that matter anything less than $O(n^3)$? In my case, $n$ is ~100,000, so $O(n^3)$ is impractical for me.
'Extra' questions (should these go under a separate question?):
- Do any of these supper multi-graphs (I have 2 edges from my super-source node to each of the "blue" nodes in my bipartite graph, and 2 edges from each of the "red" nodes to my super-sink node)?
- Are there efficient implementations of such algorithms (that run in less than $O(n^3)$, and support multi-graphs) in C++, C, or Python?
- If the answer is 'no', what are popular approximation algorithms and their associated run times?