Solution to Problem 2: Rank Fraud

Let the ministers be M_1, M_2, ... M_N. The task of the prime minister is to order them as M_i1, M_i2, ... M_iN such that for each j, M_ij beat M_i{j+1} in the table-tennis tournament. As mentioned earlier, the description of the problem as a set (the set of Ministers) and a binary relationship (who beat who) suggests the use of graphs in solving this problem. Let the vertices of the graph be { 1, 2, 3, ..., N } representing the N ministers with a directed edge from i to j if j beats i in the table-tennis tournament. For instance, if the results of the matches between 4 ministers are as follows: Minister 1 beat ministers 2 and 4, Minister 2 beats none, Minister 3 beat ministers 1 and 2, and Minister 4 beat ministers 2 and 3. The graph representing these results would look like: -------------------------- | | 1 <------------- 2 -- | ^ | | | | ---------- | | | | | | | | | | 4 <------------- 3 <------ Examining this graph we can conclude that 2 loses to 3, 3 loses to 4 and 4 loses to 1 and thus 2, 3, 4, 1 would be a possible order in which the prime minister could present the ministers to the king. Thus out aim is to find a path through the directed graph that includes all the vertices (note that by definition any vertex can appear at the most once in any path). Such a path is called a `` Hamiltonian Path ''. There are no known algorithms that can compute or even check if a given graph contains a Hamiltonian path efficiently. It is believed that any algorithm to solve this problem will take at least 2^N steps where N is the number of vertices in the graph. However, the graph that is obtained from the results of the table-tennis tournament has a special feature --- for each pair of vertices i and j there is exactly one edge involving the two of them, either from i to j or from j to i. Such a directed graph is called a ``Tournament'' (since the results of round-robin tournaments, such as the above, produce such graphs). It turns out that first of all, every tournament does have a Hamiltonian path and secondly, such a path can be calculated quite efficiently. Let us see how. We construct paths of length i for each i < N. We may pick any edge in the tournament to get a path of length 1. Pick any path of length i-1, say v_1,v_2,v_3, ..., v_i. We show that it can be extended to a path of length i. Pick any vertex v that does not appear among v_1, v_2, ... v_i. Since i<N, such a vertex always exists. 1) If the edge between v and v_1 (recall there must be one, by the definition of a tournament) is from v to v_1 then our desired path is v, v_1, ..., v_i. 2) Otherwise, if the edge between v and v_i is from v_i to v then our desired path is v_1, v_2, ... v_i, v. 3) Otherwise the situation is as follows: v_1 ----> v_2 ----> v_3 ... v_{i-1} ----> v_i | ^ | | -----------------------> v ---------------------- We scan right from v_1 to v_i to find the first vertex v_j such that the edge between v and v_j is oriented from v to v_j. Such a vertex must exist (since the edge between v and v_i is oriented from v to v_i, there is at least one and thus there must be a left most and this left most is not v_1). For this j, we have edges v_{j-1} -----> v and v -----> v_j. Then, v_1 ----> v_2 ----> ... v_{j-1} ----> v ----> v_j ... ----> v_i is a path of length i. Thus, starting with any edge, one can successively construct paths of length 2,3, and so on up to N-1. Thus, we can construct a Hamiltonian path. How efficiently can this algorithm be implemented? In each iteration, we need to find a vertex that is not already in the path and insert it in the appropriate position. This can be done in time proportional to N. There are N-2 insertions and thus, this algorithm can be implemented in time proportional to N*N. The details are as follows: -------------------------------------------------------------------------- /* We assume that the graph is stored as an adjacency matrix A. */ /* Initialise H with a path of length 1 */ If (A[1][2]=1) { H[1]=1; H[2]=2; } else { H[1]=2; H[2]=1; } Present[1]=1; Present[2]=1; for i = 2 to N-1 do { for k = 3 to N do { if (Present[j]=0) break; } /* k is vertex that has not been inserted yet. */ /* so insert it. * if (G[k][H[1]] = 1) then insert k at the beginning of H else if (G[H[i]][k] = 1) insert k at the end of H else { /* case 3. find the position j to insert k */ for j=1 to N if (G[k][j] = 1) break; insert k between the (j-1)st and jth elements currently in H } Present[k] = 1 } Print out the array H. -------------------------------------------------------------------------

Copyright (c) IARCS 2003-2020; Last Updated: 10 Nov 2005