Noobish_Monk's blog

Why do potentials work in MCMF?
By Noobish_Monk, history, 15 months ago, In English

Hello. I've been trying to understand min cost max flow algorithm for several days and now I realised I don't understand why Jonhson's potentials work. We use them so that all edges have nonnegative weights. As I remember, Jonhson's algorithm works only if there aren't any cycles with negative weight. But isn't it the criteria for optimal MCMF, that there are no negative cycles in the residual network? So, until we actually find the optimal flow, we can't use potentials as there are negative cycles. Why can we use potentials then?

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Could you please rephrase the question? I don’t understand what is it exactly that you’re asking.

The criteria for optimal flow to have no negative cycles is true only when the flow is maximum. Otherwise, the empty flow would be optimal for DAGs. Theory usually solves that by convening that there’s an extra edge between sink and source of cost $$$-\infty$$$, and talks about min cost circulations as opposed to min cost flow.

But again, this theorem is completely orthogonal to Johnson’s potentials as it implies correctness for the more generic ‘successive shortest paths’ algorithm, so maybe it will help if you rephrase the question more clearly.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't notice that the criteria is only for maximum flows, now I understand, that we just don't create these cycles. Thank you

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      To be more precise, it's not only for maximum flows, but it says, that "there is no negative cycles" is same that "is'd minimum cost flow over flows with same size". On each step, you have minimal cost flow among flows of size on this step.

      But if you have negative cycles in initial graph, you can't use potentials directly, you need to first deal with these negative cycles. Which can use similar ideas in more advanced ways, but that's another much longer story.

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        True. Also, I like to think as the problem of min cost flow in the scenario where negative cycles are allowed as undefined (kind of), because the overall final structure might not look like a flow as one would expect (i.e. might have separate negative circuits completely disconnected from the flow ‘network’) and making a ‘correct’ one is NP. To me, there is no min cost flow when there are negative cycles, only circulation.

        → Reply
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Actually, most of algoritms you know for just max flow are able to find flow with extra separate loops. Although it's possible to get rid of them in O(VE) time, I see no one who actually do this (and no problem, where you have any reason to do it).

          While being counter-intuitive, flow that allows this non-connected cycles has much more combinatorial sense in optimization problems. Of course, of your problem is to find several non-intersecting pathes from s to t, with maximum total length, you need other, but that's obviously NP-hard.

          → Reply
          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yep, that's right.

            I guess what I was trying to say is that I personally view an $$$s-t$$$ flow as being essentially several non-intersecting paths. Even the nomenclature of flow, source, sink, etc. seems to suggest such a combinatorial object.

            In this sense, min cost flow with negative cycles can't produce such outputs, and thinking one may achieve such output by applying flow-like algorithms on a network with negative cycles is a somewhat deceiving path.

            Once one eliminates the idea of source and sink (i.e. circulation), the resulting mental framework is much less deceiving.

            → Reply