3
$\begingroup$

One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS.

Could we create the level graph from sink to source instead of source to sink? Of course when subsequently doing the DFS on the level graph we would have to go down the levels rather than up.

I would expect this slight variation to lead to less dead ends during the DFS, resulting in a somewhat faster algorithm. I implemented the change and it supports my expectations. The performance improvement is minor but consistent in my test cases (e.g.: random graphs).

I could not find any literature about this online, and I study CS by myself so I cannot ask a teacher.

  • Is the change valid, or does it break the algorithm in a way I did not anticipate?
  • I can think of graphs in which the change would have a worse performance (i.e.: simple paths from source to sink, complicated paths from sink to dead ends). Is there a class of problems where these graphs are commonplace?
  • Anything else I should know or worry about?
$\endgroup$
  • 2
    $\begingroup$ It's quite common for this kind of thing to work well in practice but not be discussed much, if at all, in the literature if, for example, it doesn't change the asymptotic running time. But I'm not familiar with Dinitz's algorithm so I can't say anything specific to that. $\endgroup$ – David Richerby Jun 10 '16 at 7:42
  • $\begingroup$ Have you tried adapting the correctness proof to match your modified version? $\endgroup$ – Raphael Jun 10 '16 at 10:15
  • $\begingroup$ @Raphael, since you suggested I had a look but my theoretical background is not strong enough to understand the proof. I only really grok enough to code the algo from the description. I now ran enough tests to be very confident the variation works correctly. The improvement is mostly by a constant factor (slightly dependent on the graph density, but complicated to describe and not too significant). Since it is on average 2-2.5x faster I was expecting someone might have encountered it before. $\endgroup$ – marcv81 Jun 10 '16 at 14:22
  • $\begingroup$ So you are asking for somebody to provide a correctness proof? I'm not sure that is a reasonable scoped question for this site. (Community votes?) In any case, you should provide slightly more detailed pseudocode of the modified part so that any who want to attempt such a proof know exactly what you are doing. $\endgroup$ – Raphael Jun 10 '16 at 14:44
  • $\begingroup$ At the time I asked I was not sure whether it was correct or not. In any case I am not asking for a proof of correctness ;) I was expecting the trick to be common enough that someone would have come across it before and could confirm it's okay to go ahead with it, and possibly list some pitfalls if any. $\endgroup$ – marcv81 Jun 10 '16 at 15:05

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.