BALDA_AMAR's blog

Minimum Cost Maximum Flow with negative cycles
By BALDA_AMAR, history, 7 years ago, In English

Is there any good implementation of minimum cost maximum flow with negative cycles? Can someone please share their implementation. Also, could you please give the complexity as well.

Thanks in Advance

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

»
7 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

I think it is NP hard since it can be used to solve the Hamiltonian Path problem. I'll let someone who is more well versed with the theory correct me on this.

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

    What if we have unit capacity edges?

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    For sure it isn't NP-Hard (unless P = NP), since there exists linear programming formulation for the problem, and there exists poly-time algorithm to solve linear programs.

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

    The reason it can't solve the Hamiltonian path is that under the definition of the max-flow problem it is legal to send flow along a cycle that is not reachable from the source or from which the sink is not reachable. This way, on a graph with a hamiltonian path if you assign -1 weight to each edge and run the min-cost maxflow algorithms, it will find a single path and multiple cycles in such a way that each vertex belongs to either the path or exactly one cycle. If you are lucky the number of cycles will be zero (and thus you'll find the hamiltonian path), but it doesn't have to be the case.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The way you do it is:

  1. Connect the sink to the source with an edge with infinite capacity and negative infinity cost

  2. For as long as there's a negative cycle in the graph, increase the flow along that cycle by a constant (similar to Ford-Fulkerson you'd introduce reverse edges for all the edges for which the flow was increased).

I don't have an implementation handy, but I remember that the only implementation for mincost maxflow in this book:

https://www.amazon.com/Algorithms-Part-Graph-3rd-Pt-5/dp/0201361183

was exactly that in case you can find it online or among your friends.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Beware that this gives a min cost circulation, and not a min cost max flow (i.e., there might be flow that just “is there”, going in a circle, with no way of it getting there in the first place. That might be a problem depending on what you want. In case you don’t want that, you can get the flow value by summing the flow going through S, but the flow function itself has to be recomputed. Also, the cost is not correct.

    What you could do in this case is just find a correct flow (which is a subflow of what your algo outputs), and get its cost.

    I’m not sure what I’m proposing is coreect, but I’m pretty confident that it should be.

    EDIT: In fact, it must be wrong, because that would solve Hamiltonian cycle. Still, the subtlety here is important to understand.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is possible and can be solved.The idea involves
1.first removing negative cycles by finding negative cycles using bellman ford as long as there is a negative cycle. this should terminate in finite steps because the min cost is bounded.
2.after all negative cycles are removed then we can run standard mincost max flow which allows negative edges.
Here the complexity seems to contain some sort of absolute value of mincost possible or something like that (though not a tighter bound.the above bound is highly intuitional)

MY DOUBT: Can we do any sort of scaling technique here as in max flow porblems to remove linear dependency on min cost possible.

→ Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

There is an algorithm based on push-relabel and successive approximation that solves the min-cost circulation problem in where C is the maximal edge cost. (Edge costs are assumed to be integers.) I think the original paper is "FINDING MINIMUM-COST CIRCULATIONS BY SUCCESSIVE APPROXIMATION" by Andrew V. Goldberg and Robert E. Tarjan.

The algorithm alternates two steps: Pushing along each edge that is steeper that ε to get a -optimal pseudoflow and running push relabel to then get a -optimal circulation. This is repeated until .

To solve a min-cost-max-flow problem, first get any max-flow, then solve the min-cost circulation problem on the residual graph. (You could alternatively add a t → s edge of cost  - ∞ and capacity ∞ and just run the min-cost-circulation).

My implementation is on github. It's quite fast in practice, I've used it for V = E = 104 or dense bipartite matching problems with V = 103, E = 106.

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

    Can you give any link to problems requiring mincost maxflow on graphs with negative cycles on any online judge?

    → Reply