Search code examples
algorithmgraph-algorithmtournament

Algorithm for possible win in a tournament

I'm preparing for exam and I'm stuck with this problem:

We have n teams that play with each other twice. Each play ends without a draw. The team with the most wins is declared a winner (can be more than one). Design an algorithm that given some set of initial outcomes of plays checks whether a certain team still has a chance to become a winner in this tournament.

I don't know how to approach. The problem was put in category "Flows and matchings", but I don't see how this can be a maximum flow problem.

Solution

  • Suppose we want team A to win.

    Clearly it is best if A wins all of its matches, so this gives us a target score. We can now compute the number of losses that each other team must suffer in order for A to win overall.

    The problem is that we can only get at most 1 loser from each of the remaining games. So we need to work out how to match teams to games, where each match corresponds to a particular team losing in a particular game.

    This is basically matching on a bipartite graph between teams and games, but we can also solve it with maximum flow via an extra source and sink node.

    1. Make a source node to each team with capacity equal to the number of losses that team must have.
    2. Make an edge from each team to each remaining game involving that team (with infinite capacity)
    3. Make an edge from each remaining game to the sink node with capacity equal to the number of times that game is to be played. (i.e. if both B vs C games are still to be played, the capacity is 2)

    Then if you can construct a valid flow from source to sink that reaches the capacity (on each of the source to team edges) you have proved that it is still possible for team A to win.