International Collegiate Programming Contest

Network Flow

This session focuses on network flow, and in particular the maximum flow problem and variations. If you are not familiar with the relevant concepts and algorithms, or you need a refresher, you can use the resources below.

Problem Set

1. Power Transmission*
2. Sabotage*
3. Collector's Problem
4. Factors and Multiples
5. Buy One, Get the Rest Free

A PDF containing all the problems is available here.

Note: All problems expect I/O to be done using standard input and standard output. The solution to problems must be written in a single file. If you are programming in Java the application class should be called "Main".

Resources

Network Flow

A digraph with weighted edges can be interpreted as a network, with the edges representing directed connections between the nodes, and the weights representing the capacities of those connections. The capacities of an edge and its reverse may be different; a non-existent reverse is considered as existing with zero capacity. The classic example is of a network of water pipes: each vertex is a joint which connects some pipes, and each pipe has a maximum rate of flow that can pass through it. (Ordinary pipes, of course, are undirected and have the same capacity in each direction.) One has a special vertex, the source, which generates flow (say, a water pump) and another special vertex, the sink, which consumes it. Other vertices neither produce nor consume flow, so the net incoming minus outgoing flow at any other vertex should be zero. One can ask various questions about the flows possible on such a network, but the most common is the maximum flow problem: What is the largest amount of flow that can be passed through the network from the source to the sink, and how can it be realized?

The Basic Scheme for Maximum Flow: Ford-Fulkerson

The basic scheme for finding a maximum flow in a network is Ford-Fulkerson, and works as follows: Start from the trivial zero flow. As long as it is possible, find an augmenting path, a path from the source to the sink so that each directed edge along that path has positive capacity. When you have found such an augmenting path, push flow from the source to the sink along that path equal to the minimum edge capacity on that path. To do this, increase the running total of current flow by that amount, and for each edge in the path, decrease the capacity by that amount in the direction of the flow, and increase the capacity of the reverse edge by the same amount. (These new capacities are called residual capacities.) Repeat this until no augmenting path can be found; at that point the current flow is the maximum possible.

Notice that the scheme does not specify how to find an augmenting path. There are various choices, and they affect how many augmentations will be needed to reach the maximum flow. If all capacities are integer, each augmenting path adds at least 1 to the total flow, so no more than f augmentations are needed, where f denotes the maximum flow value. However, that may be a large number. Moreover, the number of augmentations may be even larger when the capacities are not integers. In fact, the scheme may even fail to terminate at all when the capacities are irrational. Usually, a good choice is an augmenting path with the fewest number of edges (which can be found using BFS). In that case, the scheme is guaranteed to terminate after no more than VE augmentations. This instantiation of the Ford-Fulkerson scheme is known as Edmonds-Karp.

For more information about network flow and the Ford-Fulkerson scheme, including a small example worked out in detail, see these PDF slides and these PPT slides. Another explanation is available at the Wikipedia page. There is a more advanced page at Topcoder about various choices for augmenting path selection as well. Most of the time, though, just using BFS should suffice, and you should focus on understanding the core algorithm well rather than finding the most efficient version.

Variants and Common Applications

There are very many problems that can be reinterpreted as network flow, and it is good to familiarize yourself with some of the most common ones, as well as developing the habit of looking for flow in otherwise complicated optimization problems with constraints. (This doesn't mean that flow is always the right choice where it applies because max flow isn't the fastest algorithm around. But it often works in surprising places.) Try creating a graph so that optimizing the quantity you are interested in corresponds to finding a maximum flow or minimum cut, and then you can make Ford-Fulkerson do the rest of the work for you!

Multiple Sources and Sinks

One common variant of maximum flow involves having multiple sources and/or sinks in the graph, rather than just one. This can be converted into the basic problem by adding in two special vertices: a super source and a super sink. The super source is connected to all the original source vertices with infinite-capacity edges, and the all the original sink vertices are connected to the super sink with infinite-capactiy edges. Then the basic algorithm can be run with the super source and super sink.

Vertex Capacities

Sometimes the vertices, as well as the edges, may have capacities limiting the amount of flow that can pass through them. To model this, one can split each vertex into an "in" vertex and an "out" vertex. All incoming edges are connected to the "in" vertex, and all outgoing edges to the "out" vertex, and an edge with capacity equal to the vertex capacity is placed from the "in" vertex to the "out" vertex. This configuration reduces the vertex-capacity problem to the original one.

Bipartite Matching

Recall that a matching in a bipartite graph is a set of edges, no pair of which shares a common vertex. Finding the maximum size of such a bipartite matching can be done using maximum flow, as can many variants of this basic problem. The slides here have some information on bipartite matching as well as several other variants on maximum flow.

Minimum Cut

The dual problem to maximum flow is minimum cut. For two vertices s and t, an s-t cut is a set of edges such that if those edges are removed, there is no path from s to t. The min cut - max flow theorem states that the minimum total edge weight over all s-t cuts is equal to the maximum flow on the same graph with source s and sink t. One can even extract a minimum cut from a maximum flow. To do this, first find out which vertices are reachable from s via edges which have positive residual capacity in the given maximum flow. The edges that go from this set of vertices to its complement form a minimum cut.

Min-Cost Flow

Another related setup is when the edges of the graph, in addition to having capacities governing the amount of flow that can pass through them, also have costs per unit of flow associated with them. The problem in this case is to find the minimum cost for passing f units of flow from the source to the sink, and to find a flow of that value and cost. (Alternatively, one might ask for the minimum cost for passing the maximum amount of flow, whatever it happens to be; this is Min-Cost Max-Flow.)

One approach for solving this problem uses successive shortest paths. The basic idea is to run Ford-Fulkerson where the augmenting paths are chosen so that each new augmenting path is a shortest path from s to t w.r.t. the edge costs. The cost of an original edge e is the cost b per unit of flow; the cost of the reverse of e is -b (corresponding to the savings of b when one less unit of flow is sent through e). Augmenting along such a path guarantees that, at any point in time, the current flow is a min-cost flow for the current value of the flow. We keep augmenting this way until we realize the required flow value.

It is important to note that since some of the edge weights can be negative, we cannot simply use Dijkstra's algorithm to find the shortest paths. Instead, we can use the slower Bellman-Ford algorithm (the easiest approach) or, if this is not fast enough, use more sophisticated ideas to create and maintain equivalent networks with nonnegative edge weights, and run Dijkstra's algorithm on them rather than on the actual residual networks to find shortest paths.

Successive shortest paths is only one of several approaches to the min-cost flow problem. It can be considered a generalization of Ford-Fulkerson. In the case of integer capacities, the worst-case running time for the algorithm using Bellman-Ford O(VEf). Another approach, called cycle cancelling, works by first obtaining any flow of the desired value, and then repeatedly removing negative cycles in the residual network in order to reduce the cost, until there are no negative cycles left. This two-page Topcoder tutorial covers both successive shortest paths and cycle cancelling in some depth, and these slides cover successive shortest paths in the context of the weighted bipartite matching problem.