24.06.2010

We study fixed parameter algorithms for three problems: Kemeny rank aggregation, feedback arc set tournament, and betweenness tournament. For Kemeny rank aggregation we give an algorithm with runtime O^*(2^{O(\sqrt{OPT})}), where n is the number of candidates, OPT ≤ \binom{n}{2} is the cost of the optimal ranking, and O^*(⋅) hides polynomial factors. This is a dramatic improvement on the previously best known runtime of O^*(2^O(OPT)). For feedback arc set tournament we give an algorithm with runtime O^*(2^{O(\sqrt{OPT})}), an improvement on the previously best known O^*(OPT^{O(\sqrt{OPT})}) Alon et al. [2009]. For betweenness tournament we give an algorithm with runtime O^*(2^{O(\sqrt{OPT/n})}), where n is the number of vertices and OPT ≤ \binom{n}{3} is the optimal cost. This improves on the previously known O^*(OPT^O(OPT1/3) Saurabh [2009]), especially when OPT is small. Unusually we can solve instances with OPT as large as n (log n)² in polynomial time!