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 (#7)

1. Internet Bandwidth
2. Angry Programmer
3. The Dog Task
4. Critical Links
5. Manhattan
6. Warehouse
7. Dijkstra, Dijkstra
8. SAM I AM

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.

Konig's Theorem

König's Theorem states that the minimum vertex cover on a bipartite graph equals the value of the maximum matching.

Finding Articulation Points and Bridges

A vertex such that its removal (along with its adjacent edges) disconnects the graph is called an articulation point. Similarly, an edge such that its removal disconnects the graph is called a bridge. Naively, we may find all articulation points or bridges in a graph by removing each vertex/ edge individually and checking connectivity. However, this requires O(V) or O(E) depth-first searches. Instead, we may find all articulation points or bridges with a single depth-first search while maintaining some auxilliary information. The following tutorial describes the algorithm to find articulation points, and its follow-up tutorial describes the algorithm to find bridges. We have an implementation that does both here.

Finding Strongly Connected Components

A directed graph is considered strongly connected if every vertex is reachable from every other vertex. If a directed graph G is not strongly connected, it may be partitioned into strongly connected components - sets of vertices that are strongly connected in G. We have an implementation of Kosaraju's Algorithm to compute the strongly connected components of a directed graph in linear time here.

2-SAT

2-SAT is a special case of the boolean satisfiability problem (SAT). For 2-SAT, the idea is that we have n boolean variables x_i and a formula of the form (x_1 v !x_3) ^ (!x_2 v x_5) ^ ... where the variables and negations can be anything, but the formula is the AND of clauses that are the OR of two variables. Determining whether a 2-SAT formula is satisfiable (that is, there are assignments to the variables x_i such that the formula evaluates to true) can be done in polynomial time, whereas general SAT is NP-Complete. To see how, consult the following blog entry on Codeforces.