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 .
---- Election-Methods mailing list - see http://electorama.com/em for list info
