@article{Fernau2014, 
author = {Henning Fernau and Fedor V. Fomin and Daniel Lokshtanov and Matthias Mnich and Geevarghese Philip and Saket Saurabh},
title = {Social Choice Meets Graph Drawing: How to Get Subexponential Time Algorithms for Ranking and Drawing Problems},
year = {2014},
journal = {Tsinghua Science and Technology},
volume = {19},
number = {4},
pages = {374-386},
keywords = {Kemeny aggregation, one-sided crossing minimization, parameterized complexity, subexponential-time algorithms, social choice theory, graph drawing, directed feedback arc set},
url = {https://www.sciopen.com/article/10.1109/TST.2014.6867519},
doi = {10.1109/TST.2014.6867519},
abstract = {We analyze a common feature of  p-Kemeny AGGregation ( p-KAGG) and  p-One-Sided Crossing Minimization ( p-OSCM) to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for  p-KAGG—a problem in social choice theory—and for  p-OSCM—a problem in graph drawing. These algorithms run in time  O*(2O(klogk)), where  k is the parameter, and significantly improve the previous best algorithms with running times  𝒪*⁢(1.403k) and  𝒪*⁢(1.4656k), 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(klogk)), 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]).}
}