The Complexity of Kemeny Aggregation with Three Rankings
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.28588
curl -X POST /api/v1/records/arxiv/2607.28588/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.28588/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'