International Collegiate Programming Contest

Advanced Graph Algorithms

This session focuses on advanced graph algorithms. 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. Jupiter Orbiter
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

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?

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. The following resources have a nice sampling of some of these problems:

• University of Washington Lecture Slides
• Algorithm Design, by Jon Kleinberg and Éva Tardos.
  (This is the textbook used in CS 577 here at UW–Madison.)
• Lecture notes from a Princeton course taught from the Kleinberg-Tardos book are available here

Maximum Flow

• Ford–Fulkerson

  Ford–Fulkerson finds a maximum flow by consecutively finding augmenting paths from the source vertex to the sink. These paths are any path such that additional flow can be pushed by adding or redirecting flow along any edge. When chosen via a depth-first search and edge capacities are integers, Ford-Fulkerson runs in O(f*(V+E)) time, where f is the value of the maximum flow.

• Edmonds–Karp

  Edmonds–Karp uses the same idea as Ford–Fulkerson, but it can be shown that by using a breadth-first search instead of a depth-first search, an alternate complexity of O(|V||E|^2) can be achieved. Implementation here.

• Dinic

  Dinic is an improvement to Edmonds–Karp that achieves a complexity of O(|V|^2|E|). In practice, dinic is exceptionally quick, and should be used as the algorithm of choice if Edmonds–Karp will not be fast enough. Implementation here.

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.

Matching

• Unweighted Bipartite Matching

  The general 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. The basic max-flow algorithm solves this problem, however there are specialized versions that can solve it faster. Here is an implementation that achieves O(|V||E|) time complexity, with simpler code than the full max-flow algorithm.

• Weighted Bipartite Matching

  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 and with less code. The algorithm runs in O(|V|^3) time. Implementation here.

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 modification of the Ford–Fulkerson algorithm.

The negative cycle cancellation technique finds cycles along which positive flow can be pushed and which 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 cost. More details of this approach are given in this Top Coder tutorial.

An implementation of both algorithms is given here.