Training Material

## Network flows

Note: Network flows are not part of the syllabus for IOI/IOITC.

Given a network of pipes with a given capacity and two nodes, source and sink, what is the maximum flow that can be passed from source to sink?

```                 7
-->u ------------->v
/    \            /   \
/ 7    \       10 /     \5
/        \        /       \
source         \----  /         -->sink
\        10     X         /
\ 5           / \       /7
\    <------/   \-->  /
-->w-------------->z
7
```
1. For each edge e, flow(e) ≤ capacity(e)
2. At each node, flow into the node is equal to the flow out of the node (conservation of flow).

In this case, the maximum flow is 12:

• send 5 along source→u→v→sink
• send 5 along source→w→z→sink.
• send 2 along source→u→v→w→z→sink

Observe that the edges (u,v) and (z,sink) together disconnect the source from the sink. This is called a "cut set". Clearly, any flow that goes from source to sink must go through this cut set and cannot exceed the capacity of the cut, namely 14. There may be many cut sets --- for instance, (source,u), (source,w) is also a cut set, with capacity 12.

It is clear that the maximum flow in the graph cannot exceed the capacity of the minimum size cut in the graph.

Claim: The maximum flow from source to sink is equal to the capacity of the minimum size cut in the graph.

How do we compute the maximum flow?

```          5     5     5           <--flow
source---->o---->o---->sink
5    10     5           <--capacity
```

Now, we select another path (ignoring directions) to augment the flow.

An augmenting path is a path from source to sink where

• forward edges, flow < capacity
• backward edges, flow > 0

e.g. we may have a path that looks like

```          4     6      3       2         <--flow
source---->o----->o<-----o<------sink
5     5      4       3         <--capacity
```

For each edge on this path, we compute leeway(e), defined as:

• if e is a forward edge : capacity(e) - flow(e)
• if e is a backward edge : flow(e)
```          4     6      3       2         <--flow
source---->o----->o<-----o<------sink
5     7      4       3         <--capacity
1     1      3       1         <--leeway
```

Augment flow upto min leeway along the path. Here min leeway is 1, so you can augment flow. On reverse edges, cancel out the existing flow, so reduce by the augmented amount.

After augmentation.

```
5     7      2       3         <--new flow
source---->o----->o<-----o<------sink
5     7      4       3         <--capacity
```

Repeat the augmentation step till you cannot find an augmenting path. (This algorithm is called the Ford-Fulkerson algorithm.)

Example:

```                    7
-->u ------------->v
/    \            /   \
/ 7    \       10 /     \5
/        \        /       \
source         \----  /         -->sink
\        10     X         /
\ 5           / \       /7
\    <------/   \-->  /
-->w-------------->z
7
```

```
5     5     5         <--flow
source ---->u---->z---->sink
7    10     7         <--capacity
```

Find an augmenting path, for example:

```            5     0     0         <--flow
source ---->u---->v---->sink
7     7     5         <--capacity
2     7     5         <--leeway

```

```            7     2     2         <--augmented flow
source ---->u---->v---->sink
7     7     5         <--capacity
```

Now, another augmenting path (with backward edges):

```            0     0     5     2     2       <--flow
source ---->w---->z<----u---->v---->sink
5     7     10    7     5       <--capacity
5     7     5     5     3       <--leeway
```

Augmented flow

```            3     3     2     5     5       <--flow
source ---->w---->z<----u---->v---->sink
5     7     10    7     5       <--capacity
```

Finally, we have an augmenting path

```            3     3     5         <--flow
source ---->w---->z---->sink
5     7     7         <--capacity
2     4     2         <--leeway
```

Augmented flow

```            5     5     7         <--augmented flow
source ---->w---->z---->sink
5     7     7         <--capacity
```

How do we find augmenting paths?

• Use BFS. At each node:
• take a forward edge if flow < capacity
• take a backward edge if flow > 0
• If you reach the sink, you have found an augmenting path.

In the worst case, you have to do one iteration for each unit of flow. Let F be the optimum flow. Then, we have F iterations, each of which requires finding an s-t path (BFS/DFS), so it takes mF time. (This assumes that flows are all integers).

Here is a worst case scenario:

```                                 10000      10000
--->A---------->t
/     \       -->
/       \1    /
s         --> / 9000
----------->B
9000
```

Here, if we always choose a path that includes the edge AB (or BA), each step increases the max flow by exactly 1 unit, so it takes 19000 iterations to terminate. (Of course, we could have been lucky and chosen directly the upper and lower paths to augment.)

Claim: If we always augment the flow by finding the shortest s-t path in terms of number of edges, the algorithm terminates in time O(mn). (We will not prove this). Notice that if we search for augmenting paths via BFS, we are guaranteed to find the shortest augmenting path at each stage.

Observe: If the capacities are integers, each time we augment the flow, we augment it by an integer. So, the max flow will always be integral.

### Video material

Video lecture on Network flows, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)