Sports elimination by maximum flow

ID: sports-elimination-by-maximum-flow

For a league in which every remaining game gives exactly one win, first give the target team all its remaining wins, obtaining . Make a node for each unordered pair of other teams, with source capacity equal to their remaining games. Route each game-node flow to one of its two teams, and cap the team's total additional wins at for a strict target victory. A negative cap immediately rules out success. Otherwise an integral maximum flow saturating every game-source arc specifies the winners of all games and proves feasibility. Each actual game is counted once; duplicating ordered pairs changes the problem.

New to topics? Read the docs here!