[EM] Condorcet-Kemeny calculations are not NP-hard

[Kristofer Munsterhjelm]

Richard Fobes wrote:
> Contrary to common belief, solving the Condorcet-Kemeny problem is _not_ 
> NP-hard.  It can be solved in polynomial time, even in the most 
> challenging cases.

That's strange, because the decision version of the general problem 
(minimum feedback arc set) is NP-complete, and can be shown as such by a 
reduction from vertex cover.

Does that mean that turning the general problem more specialized 
(minimum feedback arc set on tournaments, not all graphs) makes it no 
longer NP-hard/complete (for optimization and decision respectively)? It 
still sounds strange, but I guess I'll just have to wait for your 
description of that algorithm.

> In the meantime, until I have shared my proof, please keep in mind 
> that there are no proofs of the contrary belief, which is that 
> Condorcet-Kemeny calculations are NP-hard. Until there is a proof one
>  way or another, I suggest that the appropriate assumption should be 
> "we don't yet know".

"Ranking tournaments" by Alon claims to have a proof that minimum 
feedback arc set on tournaments is NP-hard. I don't have the required 
knowledge to check it, but the paper itself can be found at 
www.tau.ac.il/~nogaa/PDFS/paley.pdf .