2
$\begingroup$

Here are the details:

(1) We are given a number $f$ of units of flow that we wish to transmit from the source node to the sink node. For example, $f=5$ units of flow (data or goods) should be transmitted from the source node to the sink node.

(2) We are not given any plan or policy to transmit the flow. However, we know that $f$ is less than the maximum flow of the network. So, it is possible to transmit such an amount of flow through the network.

(3) We are given the arcs' capacities.

$\bullet$ Now, it is required to determine the residual network after sending these $f$ units of flow.

Very simple:

Input: A network with the given arcs' capacities and an amount of flow $f$. Also, two nodes are specified as source and sink nodes.

Output: A plan to transmit $f$ units of flow from the source node to the sink node, and the corresponding residual network.

It is clear that there may be more than one plan to send $f$ units of flow through the network, and so the residual network may change. It is not important to reach a special residual network. My main concern is only to find the time complexity of such a job (finding a way to transmit $f$ units of flow through the network, and then determining the residual network).

It is easy to see that if I have the plan to send $f$ units of flow, the residual network can be determined with time complexity of $O(m)$, where $m$ is the number of edges in the network.

$\bullet$ I highly appreciate any help in advance.

$\endgroup$
  • 1
    $\begingroup$ What did you try? Where did you get stuck? Did you try to prove your guess? What went wrong? $\endgroup$ – David Richerby Oct 3 '17 at 11:08
  • $\begingroup$ Actually, as in the Ford-Fulkerson algorithm, we used the augmentation path technique to find the max-flow, I think that to find the residual network after transmitting $f$ units of data (flow), we just need to transmit these $f$ units one by one through some available paths and after sending one unit, we update the arcs' capacities. This way, after sending $f$ units, one by one, we have the residual network. Now, since to find an available path from source to sink, the time complexity is $O(m)$, and we are doing it $f$ times, the time complexity of my method is $O(mf)$. $\endgroup$ – Ofogh Oct 3 '17 at 20:18
  • $\begingroup$ It was not possible to continue in that comment, so I will continue here. I am almost sure that the time complexity of my method to find the residual network is computed correctly. However, I am not sure that my method is the best technique to find the residual network! This is why I ask this question here. I will edit the question to explain more. $\endgroup$ – Ofogh Oct 3 '17 at 20:20
  • $\begingroup$ @DavidRicherby I explained a bit in comments and also edited the question. $\endgroup$ – Ofogh Oct 3 '17 at 20:30
  • $\begingroup$ Does $f$ denote the size of the desired flow, or the flow itself? A flow describes where to send the flow (i.e., it tells us how much to send along each edge). The size of the flow is a number. I am assuming $f$ denotes the size of the flow. I have edited the question accordingly -- check whether it reflects your intent. $\endgroup$ – D.W. Oct 5 '17 at 6:28
0
$\begingroup$

The time complexity of this problem is (at most) the time complexity of the network flow problem. You are given a graph and you want to find a flow of size $f$. You can use any network flow algorithm for this. Different algorithms have different running time. Wikipedia has a list of algorithms, with their running times. There is not a single optimal algorithm; different algorithms work better in different situations.

You mentioned you want to find a flow of size at least $f$, rather than a max flow. Many of the algorithms for max flow can be adjusted to stop early when you've found a flow that is large enough. Or, you can adjust the graph to ensure that a flow of size $f$ is a max flow -- if the original source vertex is $s$, add a new vertex $s_0$ and an edge $s_0 \to s$ of capacity $f$, then treat $s_0$ as the new source vertex and solve the max flow problem.

Once you find the flow itself, you can compute the residual network in $O(m)$ time. For each edge, you compute how much remaining capacity it has (the capacity of that edge minus the amount sent by the flow); and you add a reverse edge if necessary (the amount of the flow). This is $O(1)$ work per edge. All known network flow algorithms take $\Omega(m)$ time. Therefore, the time to compute the residual network once you find the flow is negligible; the bottleneck is finding the flow itself.

$\endgroup$
  • $\begingroup$ See edited answer, which now I think answers your question. $\endgroup$ – D.W. Oct 5 '17 at 6:31
  • $\begingroup$ By "network flow algorithm" in the first paragraph, you meant the "max-flow algorithm"? It is not required to find the max-flow, but to find some paths to send the given amount of flow. $\endgroup$ – Ofogh Oct 5 '17 at 9:58
  • $\begingroup$ @Ofogh, yes, that's right. Finding a max flow suffices. Many of the algorithms for max flow can be adjusted to stop early when you've found a flow that is large enough. Or, you can trivially adjust the graph to ensure that a flow of size $f$ is a max flow -- if the original source vertex is $s$, add a new vertex $s_0$ and an edge $s_0 \to s$ of capacity $f$, then treat $s_0$ as the new source vertex and solve the max flow problem. $\endgroup$ – D.W. Oct 5 '17 at 17:54
  • $\begingroup$ Thanks for your explanations! I cannot vote your answer up as my reputation is less than 15! I will do once I can. $\endgroup$ – Ofogh Oct 5 '17 at 22:44
  • $\begingroup$ @Ofogh, cool, glad it helped! If this answer resolved your problem, you can tick the checkmark to the left of the answer to mark it as the accepted answer, if you wish. $\endgroup$ – D.W. Oct 5 '17 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.