2
$\begingroup$

I've got a variant of bipartite graph matching and I can't find any literature about it.

We have bipartite graph with real capacity edges from source to left vertices (the sum of which is 1), real capacity edges from right vertices to sink (also summing to 1), and unlimited capacity edges between left and right. What is the fastest algorithm for max flow here?

To phrase it more colorfully, you have N types of dog food, totaling 1 kilogram; and N dogs, with each dog being able to eat a maximum quantity of food, but in total they can eat 1 kilogram. Not all dogs will eat all types of dog food, but they will eat up to their "capacity" of any combination of the types that they do like. How do you get the largest quantity of dog food fed to your dogs?

So far it looks like Edmonds-Karp is actually faster than push-relabel. I've been using the networkx python package implementation of both of these algorithms, but now I need to optimize for speed. I will be implementing a solution in C or Cython, but I'm concerned about the algorithm itself. It feels like there should be a specialized solution for this that works faster. Does anyone have any ideas?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Did you try linear programming algorithm? If there is a library implementing LP algorithms you could compare LP performance with Edmonds-Karp or push-relabel algorithms. Just an idea. $\endgroup$
    – fade2black
    Jul 5, 2017 at 23:12
  • 1
    $\begingroup$ I suppose you could try the algorithms listed here: en.wikipedia.org/wiki/Maximum_flow_problem#Solutions, and see which seems fastest. Or you could try to analyze their running time on graphs of the form you listed. Some of them might be primarily of theoretical interest and too complicated to be worth implementing. $\endgroup$
    – D.W. ♦
    Jul 6, 2017 at 0:06

1 Answer 1

Reset to default
0
$\begingroup$

Looks like the answer I was looking for was something like Dinitz's algorithm with dynamic trees. There are some implementation optimizations that can be added since we know it's a bipartite graph.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Did you measure performance against other implementations? I'm just curious. $\endgroup$
    – fade2black
    Jul 7, 2017 at 19:08
  • $\begingroup$ Not yet. The python implementation of Edmonds Karp and preflow push look like ridiculously slow due to python overhead. At least for my small graphs. I'd need to rewrite all of them in C/Cython to get a good comparison, but I don't think I'll reimplement more than one. $\endgroup$
    – Lucian
    Jul 8, 2017 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.