jvmusin's blog

Checking lower constraints in networks with cycles
By jvmusin, history, 5 years ago, In English

Hello, Codeforces!

Recently I was solving max-flow problems, here is one of the problems I can't solve.

You're given a network with min and max constraints on the edges. For simplicity suppose all the edges have capacity=1. For example, you have the following network:

We want to put a lower constraint on the edge C->D so that it's min=1 and check whether there exists a flow from S to T which uses the edge C->D. Note that it's unable in the given example. To find max flow on this network, we should change it slightly to remove lower constraints from the edges (algorithm is here (on russian): https://e-maxx.ru/algo/flow_with_limits). After these changes we will get the following network (I removed edge C->D with capacity 0 from the image):

Now run any max-flow algorithm and it will find the next flow (yellow edges are used edges):

As you can see, the flow is found and it means that we can use these edges in the original network and we will get the flow from S to T with edge C->D. Restore the original network now:

But, as you can see, this is not the flow from S to T.

So, my question is: How to check lower contraints in networks with cycles?

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

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

This is a valid flow from $$$S$$$ to $$$T$$$ of size 0. It satisfies the capacity constraint and the conservation of flows.

In general, any flow can be decomposed into paths and cycles. This flow contains a single cycle.

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

    Ok, now I see that the found flow is valid. Anyway, is there a method to check if we can satisfy the lower constraints with the flow which starts in S, ends in T and uses at least min capacity of every edge? I mean, the value of outcoming flow from S is equal to sum of min capacities, and same for incoming flow in T.

    EDIT: Of course, not the sum of min capacities. I meant that what if we don't want to include any cycles (circulations) which are independent of flow from S.

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

      This one looks NP-hard. There's a reduction from Hamiltonian Path problem:

      Take any undirected graph $$$G$$$ with $$$n$$$ vertices. Create a directed graph $$$H$$$ in the following way: for each $$$i$$$ from $$$1$$$ to $$$n$$$, create two vertices $$$a_i$$$, $$$b_i$$$ and create a directed edge $$$a_i \to b_i$$$ with mincap=maxcap=1. For each edge $$$uv$$$ in the original graph $$$G$$$, add two directed edges to $$$H$$$: $$$b_v \to a_u$$$ and $$$b_u \to a_v$$$. Finally, set $$$S=a_1$$$ and $$$T=b_n$$$.

      Now, we can see that there exists a flow with your property if and only if there is a Hamiltonian Path between $$$1$$$ and $$$n$$$ in $$$G$$$.

      (I hope this is correct. XD)

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

        I created this graph in almost the same way you explained) The only difference is that not all the edges $$$a_{i} \to b_{i}$$$ have mincap=1.

        And yes, surely now it looks like NP-hard.

        Thanks for your reply.

        → Reply