Ranking and drawing in subexponential time

H. Fernau, F.V. Fomin, D. Lokshtanov, M. Mnich, G. Philip, S. Saurabh

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)
95 Downloads (Pure)

Abstract

In 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*(2^{O(\sqrt{k} log k)}), 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 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*(2^{O(\sqrt{k} log k)}), 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]).
Original languageEnglish
Title of host publicationCombinatorial Algorithms (21st International Workshop, IWOCA '10, London, UK, July 26-28, 2010. Proceedings)
EditorsC.S. Iliopoulos, W.F. Smyth
Place of PublicationBerlin
PublisherSpringer
Pages337-348
ISBN (Print)978-3-642-19221-0
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6460
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Ranking and drawing in subexponential time'. Together they form a unique fingerprint.

Cite this