2026/07/30 by Péter Madarasi · 1 voice
Computer Science · Mathematics · #cs.CC #cs.DM #cs.GT #math.CO #math.OC
The Kemeny rule aggregates rankings by minimizing their total Kendall-tau distance from an aggregate order. We prove that Kemeny Score is NP-complete for exactly three unweighted rankings, even when every candidate pair is split 2-to-1. On the same profiles, the winner, unique-winner, and possible- and necessary-precedence problems are Θ2p-complete, while recognizing a Kemeny-optimal or uniquely Kemeny-optimal aggregate is coNP-complete. The hard instances induce tournaments of majority dimension exactly 3. The reduction also determines the exact maximum-cut value from the optimal Kemeny score and recovers a maximum cut from any Kemeny-optimal aggregate. For every fixed q≥3 and \lceil q/2\rceil≤ s≤ q, minimum pairwise support s yields a sharp dichotomy: the score problem is NP-complete, the winner and precedence problems are Θ2p-complete, and the recognition problems are coNP-complete when 3s≤2q; for 3s>2q, the majority tournament is transitive and its unique topological order is the unique Kemeny-optimal aggregate. Exact support s suffices in the hard case when s>q/2, and supports in s,s+1 suffice when s=q/2. These results give complete fixed-profile-size classifications and transfer to Slater orders, permutation medians, and maximum-likelihood central rankings in the Mallows model. Finally, a six-copy construction proves NP-completeness of both Kemeny Score and Kendall--Tau Center for three pairwise-equidistant rankings that still split every pair 2-to-1. For N output candidates, their common distance is \frac23\binom N2, the largest possible for an equidistant triple. The construction gives affine formulas for both optimal values, characterizes all Kemeny-optimal output orders, and shows that the output has a unique Kemeny-optimal order and a unique center exactly when the input has a unique Kemeny-optimal order.