For a long time it puzzled me how something so expensive, so leading edge, could be souseless, and then it occurred to me that a computer is a stupid machine with the ability
to do incredibly smart things, while computer programmers are smart people with theability to do incredibly stupid things. They are, in short, a perfect match.
— Bill Bryson, Notes from a Big Country (����)Shortly after the “iron curtain” fell in ����, an American and a Russian, who had both
worked on the development of weapons, met. The American asked: “When you
developed the Bomb, how were you able to perform such an enormous amount ofcomputing with your weak computers?” The Russian responded: “We used better
algorithms.”— Ye�m Dinitz, in “Dinitz’ Algorithm: The Original Version
and Even’s Version” (���6)
So I’m the bad guy now I hear, because I don’t go with the �ow.
Don’t ever go with the �ow, be the �ow.
— Jay-Z, "Stream of Consciousness", May �6, ������Applications of Flows and Cuts
��.�Edge-Disjoint Paths

One of the easiest applications of maximum flows is computing the maximum
number of edge-disjoint paths between two specified vertices s and t in a
directed graph G using maximum flows. A set of paths in G is edge-disjoint if
each edge in G appears in at most one of the paths; several edge-disjoint paths
may pass through the same vertex, however.
If we give each edge capacity 1, then the maximum flow from s to t pushes
either 0 or 1 units of flow along each edge. The flow-decomposition theorem
implies that the subgraph S of saturated edges is the union of several edgedisjoint paths and cycles. Moreover, the number of paths in this decompositionis exactly equal to the value of the flow. Extracting the actual paths from S is
straightforward—follow any directed path in S from s to t, remove that pathfrom S, and recurse.
Conversely, we can transform any collection of k edge-disjoint paths into a�����. A����������� �� F���� ��� C���flow by pushing one unit of flow along each path from s to t; the value of theresulting flow is exactly k. It follows that any maximum flow algorithm actually
computes the largest possible set of edge-disjoint paths.
If we use Orlin’s algorithm to compute maximum flows, we can computeedge-disjoint paths in O(V E) time, but Orlin’s algorithm is overkill for thissimple application. The cut ({s}, V \ {s}) has capacity at most V 1, so the
maximum flow has value at most V 1. Thus, Ford and Fulkerson’s originalaugmenting path algorithm already runs in O(| f ⇤ | E) = O(V E) time.
The same algorithm can also be used to find edge-disjoint paths in undirected
graphs. First, replace every undirected edge uv in G with a pair of directededges u v and v u, each with unit capacity, and call the resulting directed
graph G 0 . Next, compute a maximum (s, t)-flow f ⇤ in G 0 using Ford-Fulkerson.
For any edge uv in G, if f ⇤ saturates both directed edges u v and v u in G 0 ,we can remove both edges from the flow without changing its value. (Moregenerally, we can find an acyclic maximum flow in G 0 by canceling all cycles
in f ⇤ , not only cycles of length 2.) Thus, without loss of generality, f ⇤ assigns a
unique direction to each saturated edge. Finally, we can extract the edge-disjoint
paths by searching the subgraph of directed edges saturated by f ⇤ .

��.�

Vertex Capacities and Vertex-Disjoint Paths

Now suppose the vertices of the input graph G have capacities, not just theedges. In addition to our other constraints, for each vertex v other than s and t,
we require the total flow into v (and therefore the total flow out of v) to be at
most some non-negative value c(v):Xf (u v)  c(v).
u v

Can we still compute maximum flows with these new vertex constraints?
In, Ford and Fulkerson proposed the following reduction to a flow
network Ḡ with only edge capacities. Replace every vertex v with two vertices
vin and vout , connected by an edge vin vout with capacity c(v), and then replace
every directed edge u v with the edge uout vin (keeping the same capacity).
Routine definition-chasing implies that every feasible (sout , t in )-flow in Ḡ isequivalent to a feasible (s, t)-flow with the same value in the original graph G,
and vice versa. In particular, every maximum flow in Ḡ is equivalent to a
maximum flow in G. The reduction from G to Ḡ takes O(E) time, after which
we can compute the maximum flow in Ḡ using Orlin’s algorithm. Altogether,computing the maximum flow in G requires O(V E) time.
It is now easy to compute the maximum number of vertex-disjoint paths
from s to t in O(V E) time: Assign capacity 1 to every vertex and compute a
maximum flow!
�����.�. Bipartite Matching

sin

s

t

tin
sout

tout

Figure ��.�. Reducing vertex-disjoint paths in G to edge-disjoint paths in Ḡ .

��.�Bipartite Matching

Another natural application of maximum flows is finding maximum matchingsin bipartite graphs. A matching is a subgraph in which every vertex has degree
at most one, or equivalently, a collection of edges such that no two share avertex. The problem is to find a matching with the maximum number of edges.
For example, suppose we have a set of doctors who are looking for jobs, anda set of hospitals who are looking for doctors. Each doctor lists all hospitals
where they are willing to work, and each hospital lists all doctors they arewilling to hire. Our task is to find the largest subset of doctor-hospital hires thateveryone is willing to accept. This problem is equivalent to finding a maximum
matching in a bipartite graph whose vertices are the doctors and hospitals, andthere is an edge between a doctor and a hospital if and only if each find theother acceptable.
We can solve this problem by reducing it to a maximum flow problem, as
follows. Let G be the given bipartite graph with vertex set L [ R, such that everyedge joins a vertex in L to a vertex in R. We create a new directed graph G 0
by ( ) orienting each edge from L to R, ( ) adding a new source vertex s withedges to every vertex in L, and ( ) adding a new target vertex t with edges
from every vertex in R. Finally, we assign every edge in G 0 a capacity of 1.
Any matching M in G can be transformed into a flow f M in G 0 as follows:
For each edge uw in M , push one unit of flow along the path s u w t. Thesepaths are disjoint except at s and t, so the resulting flow satisfies the capacity
constraints. Moreover, the value of the resulting flow is equal to the number ofedges in M .
Conversely, consider any (s, t)-flow f in G 0 , computed using the FordFulkerson augmenting path algorithm. Because the edge capacities are integers,
the Ford-Fulkerson algorithm assigns an integer flow to every edge. (This is easy
to verify by induction, hint, hint.) Moreover, since each edge has unit capacity,
the computed flow either saturates ( f (e) = 1) or avoids ( f (e) = 0) every edge
This problem is very different from the stable matching problem we saw in Chapter ,because we aren’t trying to make each doctor and hospital as happy as possible.

�����. A����������� �� F���� ��� C���in G 0 . Finally, since at most one unit of flow can enter any vertex in U or leaveany vertex in W , the saturated edges from U to W form a matching in G. The
size of this matching is exactly | f |.
Thus, the size of the maximum matching in G is equal to the value of the
maximum flow in G 0 , and provided we compute the maxflow using augmenting
paths, we can convert the actual maxflow into a maximum matching in O(E)time. We can compute the maximum flow in O(V E) time using either Orlin’s
algorithm or off-the-shelf Ford-Fulkerson.

stFigure ��.�. A maximum matching in a bipartite graph G , and the corresponding maximum �ow in G 0 .

It is enlightening to interpret the behavior of Ford-Fulkerson in G 0 in termsof the original bipartite graph G. The algorithm maintains a matching M in G,
which is initially empty; the edges of M correspond to edges in G 0 that carry flow.
Call a vertex of G matched if is an endpoint of some edge in M , and unmatchedotherwise. In each iteration of the algorithm, we look for an alternating pathin G—a path from an unmatched vertex of L to an unmatched vertex in R thatalternates between edges in M and edges not in M . (Alternating paths in G
correspond exactly to augmenting paths for the current flow in G 0 .) If we findan augmenting path P, we update M to the symmetric difference M P, which
increases the number of edges in M by 1, and continue to the next iteration.
If there is no alternating path, the maxflow-mincut theorem implies that M
is a maximum matching, so the algorithm ends. Finding a single alternating
path requires O(E) time, and the algorithm halts after at most V iterations, so
the overall algorithm runs in O(V E) time. Figure . shows this algorithm inaction.
This characterization of maximum bipartite matchings in terms of alternating
paths was proved by Claude Berge in(independently of the maxflow-mincuttheorem), although it was already implicit in algorithms described by Harald
Kuhn in, by Dénes K nig in, and by Carl Jacobi around.
A more sophisticated algorithm, proposed by John Hopcroft and RichardpKarp in, computes maximum matchings in bipartite graphs in only O( V E)
time, by finding several disjoint alternating paths in each iteration.

��6��.�. Tuple Selection

Figure ��.�. An increasing sequence of matchings connected by alternating paths.

��.�

Tuple Selection

The bipartite maximum matching problem is the simplest example of a broader
class of problems that I call tuple selection. The input to a tuple selection
problem consists of several finite sets X 1 , X 2 , . . . , X d , each representing a different
discrete resource. Our task is to select the largest possible set of d-tuples, eachcontaining exactly one element from each set X i , subject to several capacity
constraints of the following form:• For each index i, Each element x 2 X i can appear in at most c(x) selected
tuples.
• For each index i, any two elements x 2 X i and y 2 X i+1 can appear in at
most c(x, y) selected tuples.
Each of the upper bounds c(x) and c(x, y) is either a (typically small) nonnegative integer or 1.
In the maximum-matching problem, we have d = 2 resources, each element x has capacity c(x) = 1, and each pair (x, y) has capacity c(x, y) = 1
or c(x, y) = 0, depending on whether or not x y is an edge in the underlying
bipartite graph.
I couldn’t find a standard name for these problems, so I made up my own. These aresometimes called “assignment problems”, but it’s more common for the phrase “the assignment
problem” to refer to the problem of finding a maximum-weight bipartite matching in an edgeweighted bipartite graph.

�����. A����������� �� F���� ��� C���

Because the resources are linearly ordered, and only pairs of objects inadjacent subsets X i and X i+1 are constrained, the tuple selection problem canbe reduced to a maximum-flow problem in a directed graph G defined as follows:• G contains a vertex for each element of each set X i , as well as a source
vertex s and a target vertex t. Each vertex x (except s and t) has capacityc(x).
• G contains an edge s w for each element w 2 X 1 , an edge z t for eachelement z 2 X d , and an edge x y with capacity c(x, y) for each pair ofelements x 2 X i and y 2 X i+1 , for all i. (Optionally, we can omit edges x ywith c(x, y) = 0.)
Every path from s to t in G corresponds to (or “is”) a d-tuple that we could
select; conversely, every selectable d-tuple that satisfies the stated constraints
corresponds to (or “is”) a path from s to t in G.

s

t

X1

X2

Xd

Figure ��.�. The �ow network for a tuple selection problem.

More generally, let f be an arbitrary feasible integer (s, t)-flow in G. Because
all capacities are integers or 1, the Flow Decomposition Theorem implies
that f is the sum of | f | paths from s to t, each carrying exactly one unit offlow. Straightforward definition-chasing implies that the resulting set of tuples
satisfies all the capacity constraints. Conversely, for any set of k tuples thatsatisfies the capacity constraints, the sum of the k corresponding paths is afeasible integer (s, t)-flow with value k.
Thus, we can select the maximum number of tuples that satisfy the given
capacity constraints by computing a maximum (s, t)-flow f ⇤ in G and thencomputing a flow decomposition of f ⇤ . Because all finite capacities in G are
integers, we can assume without loss of generality that f ⇤ is an integer flow, andtherefore (by the previous paragraph) corresponds to a valid set of | f ⇤ | tuples.

Exam Scheduling
The following “real world” scheduling problem might help clarify our general
reduction.
If pairs of objects from even one non-adjacent pair of subsets (X i and X j where j > i + 1)
are also constrained, the problem becomes NP-hard, by a straightforward reduction from EDM. We’ll discuss NP-hardness in the next chapter.

��8��.�. Tuple Selection

Sham-Poobanana University has hired you to write an algorithm to schedule
their final exams. There are n different classes, each of which needs to schedulea final exam in one of r rooms during one of t different time slots. At most oneclass’s final exam can be scheduled in each room during each time slot; conversely,classes cannot be split into multiple rooms or multiple times. Moreover, eachexam must be overseen by one of p proctors. Each proctor can oversee at mostone exam at a time; each proctor is available for only certain time slots; and noproctor is allowed oversee more than 5 exams total. The input to the schedulingproblem consists of three arrays:• An integer array E[1 .. n] where E[i] is the number of students enrolled in
the ith class.
• An integer array S[1 .. r], where S[ j] is the number of seats in the jthroom. The ith class’s final exam can be held in the jth room if and only if
E[i]  S[ j].
• A boolean array A[1 .. t, 1 .. p] where A[k, `] = T
proctor is available during the kth time slot.

if and only if the `thlet N = n + r + t p denote the total size of the input. Your job is to design analgorithm that either schedules a room, a time slot, and a proctor for everyclass’s final exam, or correctly reports that no such schedule is possible.
This is a standard tuple-selection problem with four resources: classes,
rooms, time slots, and proctors. To solve this problem, we construct a flow
network G with six types of vertices—a source vertex s0 , a vertex ci for each class,a vertex r j for each room, a vertex t k for each time slot, a vertex p` for eachproctor, and a target vertex t 0 —and five types of edges, as shown in Figure . :
∞

1

1

1

5

sʹ

tʹ
times

rooms
classes

complete

proctors

Figure ��.�. A �ow network for the exam scheduling problem.

• An edge s0 ci with capacity 1 for each class i. (“Each class can hold at mostone final exam.”)or as they are better known outside the US, invigilators
Arguably, this information is better represented as a graph, but I thought that would makethe reduction more confusing.

�����. A����������� �� F���� ��� C���• An edge ci r j with capacity 1 for each class i and room j such that
E[i]  S[ j]. (“Class i can hold exams in room j if and only if the room hasenough seats.”) This is the only place where the enrollments E[i] and seat
numbers S[ j] are used.
• An edge r j t k with capacity 1 for each room j and time slot k. (“At mostone exam can be held in room j at time k.”)• An edge t k p` with capacity 1 for time slot k and proctor ` such that
A[`, k] = T. (“A proctor can oversee at most one exam at any time, andonly during times that they are available.”)• An edge p` t 0 with capacity 5 for each proctor `. (“Each proctor can oversee
at most 5 exams.”)(I’m calling the source and target vertices s0 and t 0 instead of s and t only
because the problem statement already uses the variable t to denote thenumber of time slots.) Altogether, G has n + r + t + p + 2 = O(N ) vertices andO(nr + r t + t p) = O(N 2 ) edges.
Each path from s0 to t 0 in G represents a unique valid choice of class, room,
time, and proctor for one final exam; specifically, the class fits into the room,and the proctor is available at that time. Conversely, for each valid choice (class,room, time, proctor), there is a corresponding path from s0 to t 0 in G. Thus,
we can construct a valid schedule for the maximum possible number of exams
by computing an maximum (s0 , t 0 )-flow f ⇤ in G, decomposing f ⇤ into paths
from s0 to t 0 , and then transcribing each path into a class-room-time-proctor
assignment. If | f ⇤ | = n, we can return the resulting schedule; otherwise, we
can correctly report that scheduling all n final exams is impossible.
Constructing G from the given input data by brute force takes O(E) time.
We can compute the maximum flow in O(V E) time using either Ford-Fulkerson(because | f ⇤ |  n < V ) or Orlin’s algorithm, and we can compute the flow
decomposition in O(V E) time. Thus, the overall algorithm runs in O(V E) =O(N 3 ) time.

��.� Disjoint-Path Covers
A path cover of a directed graph G is a collection of directed paths in G such thatevery vertex of G lies on at least one path. A disjoint-path cover of G is a pathcover such that every vertex of G lies on exactly one path. Every directed graphhas a trivial disjoint-path cover consisting of several paths of length zero, but
that’s boring. Instead, let’s look for disjoint-path covers that contain as few paths
as possible. This problem is NP-hard in general—a graph has a disjoint-pathcover of size 1 if and only if it contains a Hamiltonian path—but there is anefficient flow-based algorithm for directed acyclic graphs.
�6���.�. Disjoint-Path Covers

To solve this problem for a given directed acyclic graph G = (V, E), weconstruct a new bipartite graph G 0 = (V 0 , E 0 ) as follows.
• H contains two vertices v [ and v ] for every vertex v of G.

• H contains an undirected edge u[ v ] for every directed edge u v in G.
(If G is represented as an adjacency matrix, then G 0 is the bipartite graphrepresented by the same adjacency matrix!)

Figure ��.6. Reducing minimum disjoint-path cover of a dag to maximum bipartite matching; squaresare �at[ and diamonds are sharp] .

Now I claim that G can be covered by k disjoint paths if and only if the newgraph G 0 has a matching of size V k. As usual, we prove the equivalence in
two stages:( Suppose G has a disjoint path cover P with k paths; think of P as a subgraphof G. Every vertex in P has in-degree either 0 or 1; moreover, there is exactly
one vertex with in-degree 0 in each path in P. It follows that P has exactly
V k edges. Now define a subset M of the edges of G 0 as follows:
M := u[ v ] 2 E 0 u v 2 P .

By definition of disjoint-path cover, every vertex of G has at most one
incoming edge in P and at most one outgoing edge in P. We conclude thatevery vertex of G 0 is incident to at most one edge in M ; that is, M is amatching of size V k.
) Suppose G 0 has a matching M of size V
defining a subgraph P = (V, M 0 ), wherek. We project M 0 back to G by

M 0 := u v 2 E u[ v ] 2 M .

By definition of matching, every vertex of G has at most one incoming edgein P and at most one outgoing edge in P. It follows that P is a collectionof disjoint directed paths in G; since P includes every vertex, P defines an
disjoint path cover with V k edges. The number of paths in P is equal to
the number of vertices in G that have no incoming edge in M 0 . We conclude
that P contains exactly k paths.
�6�

��. A����������� �� F���� ��� C���It follows immediately that we can find a minimum disjoint-path cover in G bycomputing a maximum matching in G 0 , using Ford-Fulkerson’s maximum-flow
algorithm, in O(V 0 E 0 ) = O(V E) time.
Despite its formulation in terms of dags and paths, this is really a maximum
matching problem: We want to match as many vertices as possible to distinct
successors in the graph. The number of paths required to cover the dag is equal
to the number of vertices with no successor. (And of course, every bipartite
maximum matching problem is really a flow problem.)

Minimal Faculty Hiring
Let’s go back to Sham-Poobanana University for another “real-world” schedulingproblem. SPU offers several thousand courses every day. Due to extreme budget
cuts, the university needs to significantly reduce the size of its faculty. However,
because students pay tuition (and the university cannot afford lawyers), theuniversity must retain enough professors to guarantee that every class advertisedin the course catalog is actually taught. How few professors can SPU get away
with? Each remaining faculty member will be assigned a sequence of classes toteach on any given day. The classes assigned to each professor must not overlap;
moreover, there must be enough slack in each professor’s schedule for them towalk from one class to the next. For purposes of this problem, let’s assume thatevery professor is capable of teaching every class, and that professors will nothave office hours, lunches, or bathroom breaks.
Concretely, suppose there are n classes offered in m different locations. The
input to our problem consists of the following data:• An array C[1 .. n] of classes, where each class C[i] has three fields: thestarting time C[i].start, the ending time C[i].end, and the location C[i].loc.
• A two-dimensional array T [1 .. m, 1 .. m], where T [u, v] is the time required
to walk from location u to location v.
We want to find the minimum number of professors that can collectively teachevery class, such that whenever a professor is assigned to teach two classes iand j where C[ j].start C[i].start, we actually have
C[ j].start⇥⇤C[i].end + T C[i].loc, C[ j].loc .

We can solve this problem by reducing it to a disjoint-path cover problem asfollows. We construct a dag G = (V, E) whose vertices are classes and whoseedges represent pairs of classes that are scheduled far enough apart to be taught
For a somewhat more realistic (and less depressing) formulation of this problem, consider
airplanes and flights, or buses and bus routes, instead of professors and classes.
They will, however, be expected to answer student emails as they walk between classes.

�6���.6. Baseball Eliminationby the same professor. Specifically, a directed edge i j indicates that the sameprofessor can teach class i and then class j. It is easy to construct this dag inO(n2 ) time by brute force. Then we find a disjoint-path cover of G using thematching algorithm described above; each directed path in G represents a legal
class schedule for one professor. The entire algorithm runs in O(n2 + V E) =O(n 3 ) time.
Despite its initial description in terms of intervals and distances, this is reallya maximum matching problem (which means it’s really really a maximum-flow
problem). Specifically, we want to match as many classes as possible to thenext class taught by the same professor. The number of professors we need isequal to the number of classes with no assigned successor; each class without
an assigned successor is the last class that some professor teaches.

��.6

Baseball Elimination

Every year millions of American baseball fans eagerly watch their favorite team,hoping they will win a spot in the playoffs, and ultimately the World Series.
Sadly, most teams are “mathematically eliminated” days or even weeks before theregular season ends. Often, it is easy to spot when a team is eliminated—they
can’t win enough games to catch up to the current leader in their division.
But sometimes the situation is more subtle. For example, here are the actual
standings from the American League East on August ,.
Team

Won–Lost Left NYY BAL BOS TOR DET

New York Yankees

��–��

�8

Baltimore Orioles

��–6�

�8

�

�

8

�

�

�

�

�

Boston Red Sox

6�–66

��

8

�

�

Toronto Blue Jays

6�–��

��

�

�

�

Detroit Tigers

��–86

��

�

�

�

�

�
�

Detroit is clearly behind, but some die-hard Tigers fans may hold out hopethat their team can still win. After all, if Detroit wins all of their remaining
games, they will end the season withwins, more than any other team has
now. So as long as every other team loses every game. . . but that’s not possible,
If we assume that every time interval T [u, v] is equal, this scheduling problem can actually
be solved in O(n log n) time using a simple greedy algorithm.
Many American universities schedule ten-minute breaks between classes, under the remarkable belief that a human being can walk from any classroom to any other classroom on the same
campus in ten minutes. I invite anyone who thinks this belief is realistic to visit my campus andwalk from one Siebel Center to the other.

�6���. A����������� �� F���� ��� C���

because some of those other teams still have to play each other. Here is one
complete argument:
By winning all of their remaining games, Detroit can �nish the season with a record of
�6 and 86. If the Yankees win just � more games, then they will �nish the season witha �� and 8� record which would put them ahead of Detroit. So, let’s suppose the Tigers
go undefeated for the rest of the season and the Yankees fail to win another game.
The problem with this scenario is that New York still has 8 games left with Boston.
If the Red Sox win all of these games, they will end the season with at least �� wins
putting them ahead of the Tigers. Thus, the only way for Detroit to even have a chanceof �nishing in �rst place, is for New York to win exactly one of the 8 games with Boston
and lose all their other games. Meanwhile, the Sox must lose all the games they playagainst teams other than New York. This puts them in a �-way tie for �rst place. . . .
Now let’s look at what happens to the Orioles and Blue Jays in our scenario. Baltimore has � games left with with Boston and � with New York. So, if everything happens
as described above, the Orioles will �nish with at least �6 wins. So, Detroit can catch
Baltimore only if the Orioles lose all their games to teams other than New York andBoston. In particular, this means that Baltimore must lose all � of its remaining gameswith Toronto. The Blue Jays also have � games left with the Yankees and we have already seen that for Detroit to �nish in �rst place, Toronto must will all of these games.
But if that happens, the Blue Jays will win at least �� more games giving them at �nal
record of �� and 8� or better which means they will �nish ahead of the Tigers. So, nomatter what happens from this point in the season on, Detroit can not �nish in �rst
place in the American League East.

There has to be a better way to figure this out!
Here is a more abstract formulation of the problem. Our input consists of
two arrays W [1 .. n] and G[1 .. n, 1 .. n], where W [i] is the number of games
team i has already won, and G[i, j] is the number of upcoming games between
teams i and j. We want to determine whether team n can end the season withthe most wins (possibly tied with other teams).
In the mids, Benjamin Schwartz observed that this question can bemodeled as a maximum flow problem; about years later, Dan Gusfield, Charles
Martel, and David Fernández-Baca simplified Schwartz’s flow formulation toa pair selection problem. Specifically, we want to know whether it is possible
to select
P a winner for each game, so that team n comes in first place. Let
R[i] = j G[i, j] denote the number of remaining games for team i. We willassume that team n wins all R[n] of its remaining games. Then team n can comein first place if and only if every other team i wins at most W [n] + R[n] W [i]of its R[i] remaining games.
Since we want to select a winning team for each game, we start by building
a bipartite graph, whose nodes represent the games and the teams. We have
Both the example and this argument are taken from Eli Olinick’s web site https://s .smu.
edu/~olinick/riot/detroit.html, which is based on Olinick’s joint research with Ilan Adler, Alan
Erera, and Dorit Hochbaum.
We are implicitly assuming that no game ends in a tie and that every game is actually played.
Both assumptions are consistent with Major League Baseball rules, at least for games that affectpostseason standing, barring wars, natural disasters, or swarms of bees.

�6���.6. Baseball Eliminationn
2

game nodes g i, j , one for each pair 1  i < j < n, and n 1 team nodes t i ,one for each 1  i < n. For each pair i, j, we add edges g i, j t i and g i, j t jwith infinite capacity. We add a source vertex s and edges s g i, j with capacity
G[i, j] for each pair i, j. Finally, we add a target node t and edges t i t withcapacity W [n] W [i] + R[n] for each team i.
Figure . shows the graph derived from theAmerican League East
standings, where “team n” is the Detroit Tigers. All unlabeled edges haveinfinite capacity.
NYY
BAL

3

NYY
BOS

8

s

NYY

BAL

5

NYY
TOR

7
2
7

BAL
BOS
BAL
TOR

1

7
BOS

t

13

TOR

Figure ��.�. Cubs win! Cubs win!

Theorem. Team n can end the season in first place if and only if there is afeasible flow in this graph that saturates every edge leaving s.
Proof: Suppose it is possible for team n to end the season in first place. Thenevery team i < n wins at most W [n] + R[n] W [i] of the remaining games. For
each game between team i and team j that team i wins, add one unit of flow
along the path s g i, j t i t. Because there are exactly G[i, j] games between
teams i and j, every edge leaving s is saturated. Because each team i wins at
most W [n] + R[n] W [i] games, the resulting flow is feasible.
Conversely, let f be a feasible flow that saturates every edge out of s.
Suppose team i wins exactly f (g i, j t i ) games against team j, for all i and j.
Then teams i and j play f (g i, j t i ) + f (g i, j t j ) = f (s g i, j ) = G[i, j] games,so
P every upcoming game is played. Moreover, each team i wins a total of
j f (g i, j t i ) = f (t i t)  W [n]+R[n] W [i] upcoming games, and therefore
at most W [n] + R[n] games overall. Thus, if team n win all their upcoming
games, they end the season in first place.
É
In summary, to decide whether our favorite team can win, we construct theflow network, compute a maximum flow, and report whether than maximum
flow saturates every edge out of s. For example, in the graph in Figure . ,the total capacity of the edges leaving s is (because there are remaining
games). On the other hand, the total capacity of the edges entering t is only ,�6���. A����������� �� F���� ��� C���which implies that the maximum flow value is at most . We conclude that
Detroit is mathematically eliminated.
The flow network has O(n2 ) vertices and O(n2 ) edges, and it can beconstructed in O(n2 ) time. Using Orlin’s algorithm, we can compute themaximum flow in O(V E) = O(n 4 ) time.
This is not the fastest algorithm for the baseball elimination problem. In, Kevin Wayne proved that one can determine all teams that are mathematically eliminated in only O(n 3 ) time, essentially using a single maximum-flow
computation.

��.�

Project Selection

In our final example, suppose we are given a set of n projects that we could
possibly perform. Some projects cannot be started until certain other projects
are completed. The projects and their dependencies are described by a directed
acyclic graph G whose vertices are the projects, where each edge u v indicatesthat project u cannot be performed before project v. (This is exactly the form ofdependency graphs we considered in Chapter . .) Finally, each project v has
an associated profit $(v) which will be given to us if the project is completed;some projects have negative profits, which we interpret as positive costs. We canchoose to finish any subset X of the projects that includes all its dependents;that is, for every project x 2 X , every project that x depends on is also in X .
Our goal is to find a valid subset of the projects whose total profit is as large as
possible. In particular, if all of the jobs have negative profit, the correct answer
is to do nothing.
–2

–3

–5

–8

4

6

2

3

Figure ��.8. A dependency graph for a set of eight projects. Diamonds indicate pro�table projects;
squares indicate costly projects. Each edge u v means u depends on v .

At a high level, our task to partition the projects into two subsets S and T ,the jobs we Select and the jobs we Turn down. So intuitively, we’d like to model
our problem as a minimum cut problem in a certain graph. But in which graph?
How do we enforce prerequisites? We want to maximize profit, but we only
know how to find minimum cuts. And how do we convert negative profits into
positive capacities?
We got (un)lucky here; it is possible for a team to be eliminated even if the total capacity of
all edges into t is no smaller than the total capacity of edges out of s.

�66��.�. Project Selection

To transform our given constraint graph G into a flow network G 0 , we add asource vertex s and a target vertex t to the dependency graph, with an edges v for every profitable job v (with $(v) > 0), and an edge u t for every costly
job u (with $(u) < 0). Intuitively, we can think of s as a new job (“Sleep!”) withprofit/cost 0 that we must perform last. We assign capacities to the edges of G 0
as follows:• c(s v) = $(v) for every profitable job v;• c(u t) = $(u) for every costly job u;• c(u v) = 1 for every dependency edge u v.
All edge-capacities are positive, so this is a valid input to the maximum cut
problem.
Now consider an arbitrary (s, t)-cut (S, T ) in G 0 . For any edge u v in theoriginal dependency graph, if u 2 S and v 2 T , then kS, T k = 1. Thus, we canlegally select the jobs in S if and only if the capacity of the cut (S, T ) is finite.
t
3

2
–2
∞

∞

∞

4

5

8

–3

–5

∞

∞

6
4

∞

∞

2

∞

2

6

–8

3
3

s

Figure ��.�. The �ow network for the example dependency graph, along with its minimum cut. The
cut has capacity 13 and P = 15, so the total pro�t for the selected jobs is 2.

In fact, it turns out that cuts with smaller capacity correspond to job
selections with higher profit. Specifically, I claim that selecting the jobs in S
earns a total profit of P kS, T k, where P is the sum of all the positive profits:
XXP=
max{0, $(v)} =$(v).
v$(v)>0We can prove this claim by straightforward definition-chasing, as follows. For
any subset X of projects, we define three values. (Here, as usual, we definec(u v) = 0 when u v is not an edge.)X
X
cost(X ) :=$(u) =c(u t)
u2X$(u)<0yield(X ) :=X

v2X$(v)>0u2X$(v) =Xc(s v)v2X

�6�

��. A����������� �� F���� ��� C���

profit(X ) :=X
v2X$(v) = yield(X )cost(X ).

By definition, P = yield(V ) = yield(S) + yield(T ). Because the cut (S, T ) has
finite capacity, only edges of the form s v and u t can cross the cut. By
construction, every edge s v points to a profitable job and each edge u t points
from a costly job. Thus, kS, T k = cost(S) + yield(T ). We immediately conclude
that P kS, T k = yield(S) cost(S) = profit(S), as claimed.
It follows immediately that we can maximize our total profit by computing aminimum cut in G 0 . We can easily construct G 0 from G in O(V + E) time, and we
can compute the minimum (s, t)-cut in G 0 in O(V E) time using Orlin’s algorithm.
We conclude that the entire project-selection algorithm runs in O(V E) time.

Exercises. Let G = (V, E) be a directed graph where for each vertex v, the in-degreeand out-degree of v are equal. Suppose G contains k edge-disjoint paths
from some vertex u to another vertex v. Under these conditions, must G also
contain k edge-disjoint paths from v to u? Give a proof or a counterexample
with explanation.
. Given an undirected graph G = (V, E), with three vertices u, v, and w,
describe and analyze an algorithm to determine whether there is a pathfrom u to w that passes through v. [Hint: If G were a directed graph, thisproblem would be NP-hard!]. Consider a directed graph G = (V, E) with several source vertices s1 , s2 , . . . , sand target vertices t 1 , t 1 , . . . , t ⌧ , where no vertex is both a source and atarget. A multi-terminal flow is a function f : E ! R 0 that satisfies the flow
conservation constraint at every vertex that is neither a source nor a target.
The value | f | of a multi-terminal flow is the total excess flow out of all thesource vertices:◆
X ✓X
X| f | :=

i=1w

f (si w)u

f (u si )As usual, we are interested in finding flows with maximum value, subject tocapacity constraints on the edges. (In particular, we don’t care how muchflow moves from any particular source to any particular target.)(a) Consider the following algorithm for computing multi-terminal flows.
The variables f and f 0 represent flow functions. The subroutine
M F(G, s, t) solves the standard maximum flow problem withsource s and target t.
�68

Exercises

M

MF(G, s[1 .. ], t[1 .. ⌧]):
f0
hhInitialize the �owii
for i
1 to
for j
1 to ⌧f0
M F(G f , s[i], t[ j])f
f + f0hhUpdate the �owii
return f

Prove that this algorithm correctly computes a maximum multi-terminal
flow in G.
(b) Describe a more efficient algorithm to compute a maximum multiterminal flow in G.
. The Island of Sodor is home to a large number of towns and villages,
connected by an extensive rail network. Recently, several cases of a deadly
contagious disease (either swine flu or zombies; reports are unclear) havebeen reported in the village of Skarloey. The controller of the Sodor railway
plans to close down certain railway stations to prevent the disease fromspreading to Tidmouth, his home town. No trains can pass through a closed
station. To minimize expense (and public notice), he wants to close down
as few stations as possible. However, he cannot close the Skarloey station,
because that would expose him to the disease, and he cannot close the
Tidmouth station, because then he couldn’t visit his favorite pub.
Describe and analyze an algorithm to find the minimum number ofstations that must be closed to block all rail travel from Skarloey to Tidmouth.
The Sodor rail network is represented by an undirected graph, with a vertex
for each station and an edge for each rail connection between two stations.
Two special vertices s and t represent the stations in Skarloey and Tidmouth.
For example, given the following input graph, your algorithm should
return the integer 2.

st. An n ⇥ n grid is an undirected graph with n2 vertices organized into n rows
and n columns. We denote the vertex in the ith row and the jth column
by (i, j). Every vertex (i, j) has exactly four neighbors (i 1, j), (i + 1, j),(i, j 1), and (i, j + 1), except the boundary vertices, for which i = 1, i = n,
j = 1, or j = n.
Let (x 1 , y1 ), (x 2 , y2 ), . . . , (x m , ym ) be distinct vertices, called terminals,
in the n ⇥ n grid. The escape problem is to determine whether there are m
�6�

��. A����������� �� F���� ��� C���vertex-disjoint paths in the grid that connect the terminals to any m distinct
boundary vertices.

Figure ��.��. A positive instance of the escape problem, and its solution.

(a) Describe and analyze an efficient algorithm to solve the escape problem.
The running time of your algorithm should be a small polynomial functionof n.
(b) Now suppose the input to the escape problem consists of a single integer n
and the list of m terminal vertices. If m is very small, the previous running
time is actually exponential in the input size! Describe and analyze analgorithm to solve the escape problem in time polynomial in m.
™

(c) Modify the previous algorithm to output an explicit description of theescape paths (if they exist), still in time polynomial in m.

. The SPU Commuter Silence Department is installing a mini-golf course in
the basement of the See-Bull Center! The playing field is a closed polygon
bounded by m horizontal and vertical line segments, meeting at right angles.
The course has n starting points and n holes, in one-to-one correspondence.
It is always possible hit the ball along a straight line directly from eachstarting point to the corresponding hole, without touching the boundaryof the playing field. (Players are not allowed to bounce golf balls off thewalls; too much glass.) The n starting points and n holes are all at distinct
locations.
Sadly, the architect’s computer crashed just as construction was about tobegin. Thanks to the herculean efforts of their sysadmins, they were able torecover the locations of the starting points and the holes, but all information
about which starting points correspond to which holes was lost!
Describe and analyze an algorithm to compute a one-to-one correspondence between the starting points and the holes that meets the straight-line
requirement, or to report that no such correspondence exists. The input
consists of the x- and y-coordinates of the m corners of the playing field, then starting points, and the n holes. Assume you can determine in constanttime whether two line segments intersect, given the x- and y-coordinatesof their endpoints.
���Exercises

Figure ��.��. A mini-golf course with �ve starting points (?) and holes ( ), and a legal correspondence
between them.

. A cycle cover of a given directed graph G = (V, E) is a set of vertex-disjoint
cycles that cover every vertex in G. Describe and analyze an efficientalgorithm to find a cycle cover for a given graph, or correctly report that nocycle cover exists. [Hint: Use bipartite matching!]. Suppose you are given an n ⇥ n checkerboard with some of the squaresdeleted. You have a large set of dominos, just the right size to cover
two squares of the checkerboard. Describe and analyze an algorithm todetermine whether one tile the board with dominos—each domino mustcover exactly two undeleted squares, and each undeleted square must becovered by exactly one domino.
Your input is a boolean array Deleted[1 .. n, 1 .. n], where Deleted[i, j] =T
if and only if the square in row i and column j has been deleted.
Your output is a single boolean; you do not have to compute the actual
placement of dominos. For example, for the board shown in Figure . ,your algorithm should return T.

Figure ��.��. Covering a partial checkerboard with dominos.

. Suppose we are given an n ⇥ n square grid, some of whose squares arecolored black and the rest white. Describe and analyze an algorithm todetermine whether tokens can be placed on the grid so that• every token is on a white square;• every row of the grid contains exactly one token; and• every column of the grid contains exactly one token.
�����. A����������� �� F���� ��� C���Your input is a two dimensional array IsWhite[1 .. n, 1 .. n] of booleans,indicating which squares are white. Your output is a single boolean. For
example, given the grid in Figure . as input, your algorithm should
return T.

Figure ��.��. Marking every row and column in a grid.

. Suppose we are given a set of boxes, each specified by their height, width,and depth in centimeters. All three side lengths of every box lie strictly
between cm and cm. As you should expect, one box can be placed
inside another if the first box can be rotated so that its height, width, anddepth are respectively smaller than the height, width, and depth of thesecond box. Boxes can be nested recursively. Call a box is visible if it is notinside another box.
Describe and analyze an algorithm to nest the boxes so that the numberof visible boxes is as small as possible.
. Suppose we are given an n⇥ n grid, some of whose cells are marked; the gridis represented by an array M [1 .. n, 1 .. n] of booleans, where M [i, j] = T
if and only if cell (i, j) is marked. A monotone path through the grid starts
at the top-left cell, moves only right or down at each step, and ends atthe bottom-right cell. Our goal is to cover the marked cells with as few
monotone paths as possible.

Figure ��.��. Greedily covering the marked cells in a grid with four monotone paths.

(a) Describe an algorithm to find a monotone path that covers the largest
number of marked cells.
���Exercises(b) There is a natural greedy heuristic to find a small cover by monotone
paths: If there are any marked cells, find a monotone path ⇡ that covers
the largest number of marked cells, unmark any cells covered by ⇡ thosemarked cells, and recurse. Show that this algorithm does not always
compute an optimal solution.
(c) Describe and analyze an efficient algorithm to compute the smallest setof monotone paths that covers every marked cell.
. The Faculty Senate at Sham-Poobanana University has decided to convene acommittee to determine whether Uncle Gabby, Professor Bobo Cornelius,or Mofo the Psychic Gorilla should replace the recently disgraced Baron
Factotum as the new official mascot symbol of SPU’s athletic teams (TheFighting Pooh-bahs). Exactly one faculty member must be chosen from eachacademic department to serve on this committee. Some faculty members
have appointments in multiple departments, but each committee member
can represent only one department. For example, if Prof. Blagojevich isaffiliated with both the Department of Corruption and the Department of
Stupidity, and he is chosen as the Stupidity representative, then someone
else must represent Corruption. Finally, University policy requires thatevery faculty committee must contain exactly the same number of assistantprofessors, associate professors, and full professors. Fortunately, the numberof departments is a multiple of .
Describe and analyze an algorithm to choose a subset of the SPU faculty
to staff The Post-Factotum Simian Mascot Symbol Committee, or correctly
report that no valid committee is possible. Your input is a bipartite graphindicating which professors belong to which departments; each professor
vertex is labeled with that professor’s rank (assistant, associate, or full).
. The Department of Commuter Silence at Sham-Poobanana University has
a flexible curriculum with a complex set of graduation requirements. The
department offers n different courses, and there are m different requirements.
Each requirement specifies a subset of the n courses and the number ofcourses that must be taken from that subset. The subsets for different
requirements may overlap, but each course can be used to satisfy at mostone requirement.
For example, suppose there are n = 5 courses A, B, C, D, E and m = 2
graduation requirements:• You must take at least 2 courses from the subset {A, B, C}.

• You must take at least 2 courses from the subset {C, D, E}.

Then a student who has only taken courses B, C, D cannot graduate, but astudent who has taken either A, B, C, D or B, C, D, E can graduate.
�����. A����������� �� F���� ��� C���Describe and analyze an algorithm to determine whether a given student
can graduate. The input to your algorithm is the list of m requirements(each specifying a subset of the n courses and the number of courses thatmust be taken from that subset) and the list of courses the student has taken.
. You’re organizing the First Annual SPU Commuter Silence -Hour Dance
Exchange, to be held all day Friday, Saturday, and Sunday. Several -minutesets of music will be played during the event, and a large number of DJs
have applied to perform. You need to hire DJs according to the following
constraints.
• Exactly k sets of music must be played each day, and thus 3k sets
altogether.
• Each set must be played by a single DJ in a consistent music genre(ambient, bubblegum, dubstep, horrorcore, K-pop, Kwaito, mariachi,
straight-ahead jazz, trip-hop, Nashville country, parapara, ska, . . . ).
• Each genre must be played at most once per day.
• Each candidate DJ has given you a list of genres they are willing to play.
• Each DJ can play at most three sets during the entire event.
Suppose there are n candidate DJs and g different musical genres available.
Describe and analyze an efficient algorithm that either assigns a DJ and agenre to each of the 3k sets, or correctly reports that no such assignment ispossible.
. Suppose you are running a web site that is visited by the same set of people
every day. Each visitor claims membership in one or more demographic
groups; for example, a visitor might describe himself as male, – years
old, a father, a resident of Illinois, an academic, a blogger, and a fan of Gilbert
and Sullivan. Your site is supported by advertisers. Each advertiser has
told you which demographic groups should see its ads and how many of its
ads you must show each day. Altogether, there are n visitors, k demographic
groups, and m advertisers.
Describe an efficient algorithm to determine, given all the data describedin the previous paragraph, whether you can show each visitor exactly one
ad per day, so that every advertiser has its desired number of ads displayed,and every ad is seen by someone in an appropriate demographic group.
. Suppose we are given an array A[1 .. m][1 .. n] of non-negative real numbers.
We want to round A to an integer matrix, by replacing each entry x in A
I am a very good theoretical computer scientist, specifically, a geometric algorithm specialist.

���Exerciseswith either bxc or dxe, without changing the sum of entries in any row orcolumn of A. For example:
23
23
1.2 3.4 2.4
1 4 2
6
7
6
7
43.9 4.0 2.15 7 ! 44 4 25
7.9 1.6 0.5
8 1 1(a) Describe and analyze an efficient algorithm that either rounds A in thisfashion, or reports correctly that no such rounding is possible.
(b) Prove that a legal rounding is possible if and only if the sum of entries
in each row is an integer, and the sum of entries in each column is an
integer. In other words, prove that either your algorithm from part (a)returns a legal rounding, or a legal rounding is obviously impossible.
™

(c) Suppose we are guaranteed that none of the entries in the input matrix
A is an integer. Describe and analyze an even faster algorithm that either
rounds A or reports correctly that no such rounding is possible. For fullcredit, your algorithm must run in O(mn) time. [Hint: Don’t use flows.]. Ad-hoc networks are made up of low-powered wireless devices. In principle , these networks can be used on battlefields, in regions that haverecently suffered from natural disasters, and in other hard-to-reach areas.
The idea is that a large collection of cheap, simple devices could be distributed through the area of interest (for example, by dropping them from anairplane); the devices would then automatically configure themselves into afunctioning wireless network.
These devices can communicate only within a limited range. We assume
all the devices are identical; there is a distance D such that two devices cancommunicate if and only if the distance between them is at most D.
We would like our ad-hoc network to be reliable, but because the devices
are cheap and low-powered, they frequently fail. If a device detects that
it is likely to fail, it should transmit its information to some other backup
device within its communication range. We require each device x to have kpotential backup devices, all within distance D of x; we call these k devices
the backup set of x. Also, we do not want any device to be in the backup
set of too many other devices; otherwise, a single failure might affect a large
fraction of the network.
So suppose we are given the communication radius D, parameters b
and k, and an array d[1 .. n, 1 .. n] of distances, where d[i, j] is the distance
between device i and device j. Describe an algorithm that either computes
but not so much in practice�����. A����������� �� F���� ��� C���a backup set of size k for each of the n devices, such that no device appears
in more than b backup sets, or reports (correctly) that no good collection of
backup sets exists.
. Faced with the threat of brutally severe budget cuts, Potemkin University
has decided to hire actors to sit in classes as “students”, to ensure thatevery class they offer is completely full. Because actors are expensive, theuniversity wants to hire as few of them as possible.
Building on their previous leadership experience at the now-defunctSham-Poobanana University, the administrators at Potemkin have given
you a directed acyclic graph G = (V, E), whose vertices represent classes,
and where each edge i j indicates that the same “student” can attend
class i and then later attend class j. In addition, you are also given an arraycap[1 .. V ] listing the maximum number of “students” who can take eachclass. Describe an analyze an algorithm to compute the minimum numberof “students” that would allow every class to be filled to capacity.
. Quentin, Alice, and the other Brakebills Physical Kids are planning an
excursion through the Neitherlands to Fillory. The Neitherlands is a vast,
deserted city composed of several plazas, each containing a single fountainthat can magically transport people to a different world. Adjacent plazas areconnected by gates, which have been cursed by the Beast. The gates between
plazas are open only for five minutes every hour, all simultaneously—from: to : , then from : to : , and so on—and are otherwise locked.
During those five minutes, if more than one person passes through any single
gate, the Beast will detect their presence. Moreover, anyone attempting
to open a locked gate, or attempting to pass through more than one gate
within the same five-minute period will turn into a niffin. However, any
number of people can safely pass through different gates at the same time
and/or pass through the same gate at different times.
You are given a map of the Neitherlands, which is a graph G with avertex for each fountain and an edge for each gate, with the fountains to
Earth and Fillory clearly marked.
(a) Suppose you are also given a positive integer h. Describe and analyze
an algorithm to compute the maximum number of people that can walkfrom the Earth fountain to the Fillory fountain in at most h hours—that
is, after the gates have opened at most h times—without anyone alerting
the Beast or turning into a niffin. The running time of your algorithm
should depend on h. [Hint: Build a different graph.]This is very bad.
This is very very bad.

��6

Exercises(b) Describe an analyze an algorithm for part (a) whose running time ispolynomial in V and E, with no dependence on h.

®™

(c) On the other hand, suppose you are also given an integer k. Describe
and analyze an algorithm to compute the minimum number of hours thatallow k people to walk from the Earth fountain to the Fillory fountain,
without anyone alerting the Beast or turning into a niffin. [Hint: Usepart (a).]™

. Let G = (L t R, E) be a bipartite graph, whose left vertices L are indexed`1 , `2 , . . . , `n and whose right vertices are indexed r1 , r2 , . . . , rn . A matching M in G is non-crossing if, for every pair of edges `i r j and `i 0 r j 0 in M ,we have i < i 0 if and only if j < j 0 .
(a) Describe and analyze an algorithm to find the largest non-crossing
matching in G. [Hint: This is not really a flow problem.](b) Describe and analyze an algorithm to find the smallest number of noncrossing matchings M1 , M2 , . . . , Mk such that each edge in G is in exactly
one matching Mi . [Hint: This is really a flow problem.]™

. Let G = (L t R, E) be a bipartite graph, whose left vertices L are indexed`1 , `2 , . . . , `n in some arbitrary order.
(a) A matching M in G is dense if there are no consecutive unmatchedvertices in L; that is, for each index i, at least one of the vertices `i and`i+1 is incident to an edge in M . Describe an algorithm to determine
whether G has a dense matching.
(b) A matching M in G is sparse if there are no consecutive matched vertices
in L; that is, for each index i, at least one of the vertices `i and `i+1
is not incident to an edge in M . (In particular, the empty matching issparse.) Describe an algorithm to find the largest sparse matching in G.
(c) A matching M in G is palindromic if, for every index i, either `i and`n i+1 are both incident to edges in M , or neither `i nor `n i+1 is incident
to an edge in M . (In particular, the empty matching is palindromic.)
Describe an algorithm to find the largest palindromic matching in G.
None of these problems restrict which vertices in R are matched or unmatched.

™

. A rooted tree is a directed acyclic graph, in which every vertex has exactly
one incoming edge, except for the root, which has no incoming edges.
Equivalently, a rooted tree consists of a root vertex, which has edges pointing
to the roots of zero or more smaller rooted trees. Describe an efficientalgorithm to compute, given two rooted trees A and B, the largest rooted
�����. A����������� �� F���� ��� C���tree that is isomorphic to both a subgraph of A and a subgraph of B. Morebriefly, describe an algorithm to find the largest common subtree of tworooted trees.
[Hint: This would be a relatively straightforward dynamic programming
problem if either every node had O(1) children or the children of each node
were ordered from left to right. But for unordered trees with large degree,
you need another technique to combine recursive subproblems efficiently.]

��8