Franklyn_W's blog

How to implement flow constraint
By Franklyn_W, history, 7 years ago, In English

Hi Codeforces, 

I'm currently working on a problem related to network flows. Does anyone know how to implement constraints of the following type into a system?

Edges 1 and 2 go into the vertex, and have capacity one. Edges 3 and 4 go out and have capacity one. How can one force a constraint to the effect of (edges 3 and 2 can't have a sum of flows greater than one)? 

UPD: I should note the context involves min-cost flow, so perhaps we can leverage the costs of the edges.
  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Split the vertex in two, A and B.

Edge 1 goes into A, edges 3 goes out of A, edge 2 goes into B, edge four goes out of B, there's an edge from A to B with infinite capacity.

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

    So I can send 1 into A via edge1, 1 going out of A via edge3; 1 into B via edge2, 1 out of B via edge4.

    Now flow sum of edge2 and edge3 is 2, right?

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

Auto comment: topic has been updated by Franklyn_W (previous revision, new revision, compare).

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

I'm not sure if I understood the constraint correctly but I think it is easy to construct a system with this constraint where the (unique) optimal solution is non-integral. Therefore it is not likely that there exists a straightforward reduction to min-cost flow. (if a reduction exists it should multiply all capacities/weights with something).

→ Reply