Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Ranking and Drawing in Subexponential Time

There are no MPG-Authors available
There are no locators available
Fulltext (public)
There are no public fulltexts available
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:
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]).