The problem of finding a Kemeny optimal aggregation is as follows: Given items $1 \ldots n$ and a list of partial rankings $q_i$ (i.e. permutations of subsets) of these items, find a ranking $r$ of $1\ldots n$ that minimizes $\sum_i d(r, q_i)$. Where $d(r, q)$ is defined as a count of the number of pairs on which $r$ and $q$ agree, scaled so that complete agreement is 1 (i.e. scaled by $k(k-1)/2$ where $k = |q|$).
Finding a Kemeny-optimal solution is known to be NP-hard in n (not surprising, it's an optimisation problem on a search space of size $n!$). What I'm wondering is if it's in fact NP-complete - if there's an (efficient?) polynomial time algorithm for verifying if a given ranking is in fact Kemeny optimal. I've seen a paper or two claiming it is, but I've not been able to find any papers which prove it. (Possibly because I live and work outside the academic firewall). Any references / ideas?