Course contentsShow
← Computer Science
Lesson 1053 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Baseball Elimination Problem

Determine if a team can still win a tournament by modeling game outcomes as a flow network.

Baseball Elimination Problem

What you'll learn: You'll learn how to determine if a baseball team can still win their division by modeling remaining games as a maximum flow network.

The Real-World Problem

Imagine it's late in the baseball season. Team X has won 70 games, and the division leader has 75 wins. Can Team X still win the division? At first glance, you might think "yes, if they win all their remaining games and the leader loses enough." But what if multiple teams ahead of them play each other—guaranteeing some of them will get more wins? This interdependency makes the problem tricky.

Modeling as a Flow Network

Here's the clever insight: create a flow network where:

  • Source (s) connects to nodes representing each remaining game between other teams (not involving Team X)
  • Each game node has capacity equal to the number of games those two teams will play against each other
  • Game nodes connect to the team nodes involved in that game (infinite capacity edges)
  • Each team node connects to the sink (t) with capacity = (Team X's potential max wins) - (that team's current wins)

Why This Works

You're asking: "Can we distribute the remaining game wins among other teams such that no team exceeds Team X's best possible total?" If the max flow equals the total number of remaining games (all games accounted for without violating capacity constraints), then Team X is not eliminated. If flow is less than total games, some team must exceed X's maximum possible wins—Team X is mathematically eliminated.

This transforms a combinatorial scheduling problem into a flow problem you can solve with algorithms like Edmonds-Karp or Dinic's.

Key Takeaway: The Baseball Elimination Problem uses max flow to determine if a team can still win by checking whether remaining games can be distributed among opponents without anyone surpassing the team's maximum achievable wins.