# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Ranking and Drawing in Subexponential Time

##### MPS-Authors

There are no MPG-Authors available

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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 (*Combinatorial Algorithms*. Berlin: Springer. doi:10.1007/978-3-642-19222-7_34.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0019-DC07-4

##### Abstract

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]).