Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Ranking and Drawing in Subexponential Time

There are no MPG-Authors in the publication available
External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Fernau, H., Fomin, F. V., Lokshtanov, D., Mnich, M., Philip, G., & Saurabh, S. (2011). Ranking and Drawing in Subexponential Time. In C. S. Iliopoulos, & W. F. Smyth (Eds.), Combinatorial Algorithms. Berlin: Springer. doi:10.1007/978-3-642-19222-7_34.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-DC07-4
In this paper we obtain parameterized subexponential-time algorithms for \kaggLG{} (\kagg{}) --- a problem in social choice theory --- and for \oscmLG{} (\oscm{}) -- a problem in graph drawing (see the introduction for definitions). These algorithms run in time \Oh^*}(2^{\Oh(\sqrt{k}\log k)}), where k is the parameter, and significantly improve the previous best algorithms with running times \Oh^{*}(1.403^k) and \Oh^{*}(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 {\sc p-Directed Feedback Arc Set}. Our results for the above-guarantee version of \kagg{} reveal an interesting contrast. We show that when the number of ``votes'' in the input to \kagg{} is {\em odd} the above guarantee version can still be solved in time O^{*}(2^{\Oh(\sqrt{k}\log k)}), while if it is {\em even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails (equivalently, unless FPT=M[1]).