scopeInfinity's blog

By scopeInfinity, history, 8 years ago, In English

For a general Min Cost Max Flow problem cost C associated to an edge having flow F results in C*F .

Thus Objective is to minimize Sigma Ci * Fi, where Fi <= Capacity of ith Edge and giving maximum flow.

0-1 Version

If we have a variation that with a flow F <= Capacity is flowing through an edge only Ci cost should be considered NOT Ci*Fi.

i.e. If edge allows flows its going to cost C or else its going to cost 0.

I am not sure, How can I proceed for it. The optimal cost flow is not required.

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

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I think it's NP-complete, so there is no polynomial time algorithm (assuming P ≠ NP). You could prove that by showing that some other NP-complete problem, in example vertex cover (in a general graph) can be solved using your 0-1 min-cost flow.

The vertex cover problem is: given a graph, choose the smallest subset of vertices, such that every vertex v is either chosen, or one of it's neighbors is chosen. Then, if your graph has n vertices, construct the following flow network: you have a source, n vertices x1, ..., xn, n other vertices y1, ..., yn and a sink. You connect the source to all xi (capacity 1, cost 0), all yi to the sink (infinite capacity, cost 1), and each xi to yi (infinite capacity, cost 0). Also, for every edge (u, v) in your graph you add edges from xu to yv and from xv to yu (infinite capacity, cost 0). Now, note that the maximum flow here is n, and only edges from yi to the sink have non-zero cost, so your flow will try to use the least amount of them, and the ones used will be exactly the minimum vertex cover.