International Collegiate Programming Contest

Network Flow

This session focuses on problems related to network flow. 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. Dots and Boxes
2. Kaguya Wa Saketakunai
3. Landscaping
4. Planes, Trains, but not Automobiles
5. Cordon Bleu
6. Code Names

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" and should be in the default package.

Resources

Networks, flows, and cuts

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. 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? Technically, the term "flow" refers to the latter, and the amount is called the "value" of the flow.

A closely related problem is that of finding a cut of minimum capacity in the network. A cut is a partition of the vertices that separates the source from the sink, and the capacity of the cut is the sum of the capacities of all the edges that go from the source side of the cut to the sink side.

There are a wide variety of generic problems that can be cast as maximum flow or minimum cut. Mastering these can help expand your ability to recognize a problem as requiring network flow. See here for a nice sampling of such problems.

Maximum Flow

Many of the algorithms for computing a flow of maximum value are instantiations of the Ford–Fulkerson schema, which superimposes successive maximum path flows without ever violating the capacity constraints. The paths go from the source to the sink, consist of edges and reverse edges, and are referred to as augmenting paths. When the augmenting paths are chosen via a depth-first search and edge capacities are integers, the process runs in O(f.(|V+|E|)) time, where f is the value of the maximum flow. When the paths are chosen via breadth-first search, the process runs in time O(|V|.|E|²) for arbitrary capacities and is known as Edmonds–Karp. Staging such augmentatations into blocking flows as in Dinic's algorithm improves the running time to O(|V|².|E|) in general networks, and O(|E|.min(|E|^1/2,|V|)) for networks where all capacities are 1. When Edmonds-Karp is not fast enough, Dinic often is.

Ford-Fulkerson maintains feasiblity and gradually reaches optimality. A dual approach known as Push-Relabel maintains optimality and gradually reaches feasiblity. Although courses typically focus on augmenting path approaches, in competitive programming, Push-Relabel is often the algorithm of choice. See here for more about the underlying theory and algorithms.

Minimum Cut

A cut of minimum capacity can be obtained from a flow f of maximum value by taking the source side to be all vertices that are reachable from the source in the residual network for f. The additional work beyond finding a flow of maximum value is just O(|V|+|E|). The maximum value of a flow equals the minimum capacity of a cut.

Bipartite Matching

Finding matchings in bipartite graphs is one of the classical applications of max flow.

The unweighted bipartite matching problem takes as input a bipartite graph representing two sets of objects to be matched, with an edge between objects that can potentially be paired. The maximum bipartite matching question asks how many pairs can be made such that each object from either set is involved in at most one pair. Ford-Fulkerson with depth-first of breadth-first search solves the problem in time O(|V|.|E|). Dinic does it in time O(|V|^1/2.|E|).

Weighted bipartite matching asks the same matching problem except in a weighted graph. The general solution can be reduced to min-cost max-flow, but the Hungarian algorithm solves the problem more efficiently (in time O(|L|².|R|) for a bipartite graph with left vertex set L and right vertex set R) and with less code.

Min-Cost Max-Flow

Min-Cost Max-Flow takes a graph as input where each edge has both a capacity and a weight. The goal is then to find a maximum flow from s to t such that the following quantity is minimized: the sum over all edges of the product of the weight of the edge and the flow through the edge. Several interesting problems can be modeled in the min-cost max-flow problem framework. There are two common ways to solve the min-cost max-flow problem: negative cycle cancellation, and a variant of Ford–Fulkerson.

The negative cycle cancellation technique finds cycles along which positive flow can be pushed and that have negative total cost. To model the source–sink behavior, an infinite-capacity edge is added from the sink to the source. When all of the negative cycles have been cancelled, the resulting flow is a maximum flow with minimum cost. This simple technique is fairly easy to implement, and works well when the network can be guaranteed to have few negative cycles.

The more common solution to min-cost max-flow is to use the Ford–Fulkerson algorithm, and select augmenting paths by choosing paths with positive capacity and minimum total net cost per additional unit of flow. More details of this approach are given in this tutorial.