Fernau, HenningHenningFernauFomin, Fedor V.Fedor V.FominLokshtanov, DanielDanielLokshtanovMnich, MatthiasMatthiasMnichPhilip, GeevargheseGeevarghesePhilipSaurabh, SaketSaketSaurabh2020-01-242020-01-242011International Workshop on Combinatorial Algorithms IWOCA (2010)http://hdl.handle.net/11420/4552In this paper we obtain parameterized subexponential-time algorithms for p -Kemeny Aggregation (p-KAGG) — a problem in social choice theory — and for p -One-Sided Crossing Minimization (p-OSCM) – a problem in graph drawing (see the introduction for definitions). These algorithms run in time O∗(2O(k√logk)), where k is the parameter, and significantly improve the previous best algorithms with running times O∗(1.403 k ) and O∗(1.4656 k ), respectively. We also study natural “above-guarantee” versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p -Directed Feedback Arc Set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of “votes” in the input to p-KAGG is odd the above guarantee version can still be solved in time O∗(2O(k√logk)), while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails (equivalently, unless FPT=M[1]).enInformatikConference Paper10.1007/978-3-642-19222-7_34Other