Ranking and drawing in subexponential time

Start Page
337
End Page
348
Citation
International Workshop on Combinatorial Algorithms IWOCA (2010)
Contribution to Conference
International Workshop on Combinatorial Algorithms IWOCA 2010  
Publisher DOI
10.1007/978-3-642-19222-7_34
Publisher
Springer Nature
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∗(2O(k√logk)), 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 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(k√logk)), 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]).
DDC Class
004: Informatik