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. Flowery Trails
5. Cordon Bleu

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?

There are a wide variety of generic problems that network flow can solve. 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

Solutions

• 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.

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 sum of the weights of edges used is minimal. Many 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.