Source code online books for professionals by professionals

Baseball elimination. The solution to this problem was first published by Benjamin L. Schwartz in 1966. If you’re 
like me, you could forgo the baseball context and imagine this being about a round-robin tournament of jousting 
knights instead (as discussed in Chapter 4). Anyway, the idea is as follows: You have a partially completed tournament 
(baseball-related or otherwise), and you want to know if a certain team, say, the Mars Greenskins, can possibly win 
the tournament. That is, if they can at most win W games in total (if they win every remaining game), is it possible to 
reach a situation where no other team has more than W wins?
It’s not obvious how this problem can be solved by reduction to maximum flow, but let’s have a go. We’ll build a 
network with integral flow, where each unit of flow represents one of the remaining games. We create nodes x
1
, … , x
n
 
to represent the other teams, as well as nodes p
ij
 to represent each pair of nodes x
i
 and x
j
 . In addition, of course, we 
have the source s and the sink t. Add an edge from s to every team node, and one from every pair node to t. For a pair 
node p
ij
 , add edges from x
i
 and x
j
 with infinite capacity. The edge from pair node p
ij
 to t gets a capacity equal to the 
number of games left between x
i
 and x
j
. If team x
i
 has won w
i
 games already, the edge from s to x
i
 gets a capacity of  
W - w
i
 (the number it can win without overtaking the Greenskins).
As I said, each unit of flow represents one game. Imagine tracking a single unit from s to t. First, we come to a 
team node, representing the team that won this game. Then we come to a pair node, representing which team we 
were up against. Finally, moving along an edge to t, we gobble up a unit of capacity representing one match between 
the two teams in question. The only way we can saturate all the edges into t is if all the remaining games can be played 
under these conditions—that is, with no team winning more than W games in total. Thus, finding the maximum flow 
gives us our answer. For a more detailed correctness proof, either see Section 4.3 of Introduction to Graph Theory by 
Douglas B. West (see the references for Chapter 2) or take a look at the original source, Possible winners in partially 
completed tournaments, by B. L. Schwartz.

---

ChApTeR 10 
■
 MATChINgs, CuTs, ANd Flows 
222