VOTING - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

The problem is more commonly known as the “Kemeny Ranking Problem” and is NP-hard even if the number of voters is only 4. There is an obvious solution that takes only a polynomial factor longer than O(m!) where m is the number of candidates. Try all orderings of the candidates and check their distance to the voters. However, there is a more efficient method which is similar to the dynamic programming, O(poly(n) * 2^n)-time algorithm for the traveling salesman problem.

First, all that really matters is that we have an m x m table where entry (i,j) is the number of times candidate i is ranked higher than candidate j. This can be computed in time O(nm^2) by simply examining each voter and checking all O(m^2) pairs of candidates to see how they are ranked. The answer can now be computed in O(2^m * m^2) time. This can be accomplished through a dynamic programming approach which computes distances v[S] where S is any subset of candidates. Here v[S] is meant to indicate the distance of the optimum ordering if all candidates except the ones in S were discarded (and the rankings were contracted in the natural way). Clearly any singleton set {c} has v[{c}] = 0.

Now, to compute v[S], say we knew that candidate c (in S) was placed first in such an ordering. It suffices to compute v[S-{c}] recursively and then v[S] is just v[S-{c}] plus the total number of times some candidate c’ in S-{c} is ranked higher than c (which can be easily obtained with the table computed in the preprocessing step). Of course, we don’t know before hand of any candidate c which is placed first in an optimal ordering of S so we have to try all such candidates c and recursively compute all v[S-{c}] values. We keep the one that minimizes v[S-{c}] plus the number of disagreements with the voters that are introduced upon adding c to the top of the ranking of S-{c}.

Thus, for each of the 2^m subsets of candidates, we try all at most m clients and can perform the counting of the new disagreements in at most m steps. To deal with the possibility of multiple solutions, one can simply iterate through the potential first candidates c in S in increasing order and use the first c that minimizes the quantity v[S-{c}] + number of new disagreements.