{"id":"arxiv/2607.28588","url":"https://arxiv.org/abs/2607.28588","tags":["cs.GT","cs.CC","cs.DM","math.CO","math.OC"],"score":0,"title":"The Complexity of Kemeny Aggregation with Three Rankings","domain":"cs.GT","source":"arxiv","authors":["Péter Madarasi"],"reviews":0,"subject":"cs.GT","summary":"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 $Θ_2^p$-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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-30","reactions":{}}