Ranking and drawing in subexponential time

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

doi:10.1007/978-3-642-19222-7_34

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 proceeding › Conference contribution › Academic › peer-review

9 Citations (Scopus)

113 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 language	English
Title of host publication	Combinatorial Algorithms (21st International Workshop, IWOCA '10, London, UK, July 26-28, 2010. Proceedings)
Editors	C.S. Iliopoulos, W.F. Smyth
Place of Publication	Berlin
Publisher	Springer
Pages	337-348
ISBN (Print)	978-3-642-19221-0
DOIs	https://doi.org/10.1007/978-3-642-19222-7_34
Publication status	Published - 2011

Publication series

Name	Lecture Notes in Computer Science
Volume	6460
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-642-19222-7_34

Metis242213Final published version, 258 KB

Cite this

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 (21st International Workshop, IWOCA '10, London, UK, July 26-28, 2010. Proceedings) (pp. 337-348). (Lecture Notes in Computer Science; Vol. 6460). Springer. https://doi.org/10.1007/978-3-642-19222-7_34

@inproceedings{ba78587421ee4c6c8b97a121a40c7478,

title = "Ranking and drawing in subexponential time",

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

author = "H. Fernau and F.V. Fomin and D. Lokshtanov and M. Mnich and G. Philip and S. Saurabh",

year = "2011",

doi = "10.1007/978-3-642-19222-7_34",

language = "English",

isbn = "978-3-642-19221-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "337--348",

editor = "C.S. Iliopoulos and W.F. Smyth",

booktitle = "Combinatorial Algorithms (21st International Workshop, IWOCA '10, London, UK, July 26-28, 2010. Proceedings)",

address = "Germany",

}

Fernau, H, Fomin, FV, Lokshtanov, D, Mnich, M, Philip, G & Saurabh, S 2011, Ranking and drawing in subexponential time. in CS Iliopoulos & WF Smyth (eds), Combinatorial Algorithms (21st International Workshop, IWOCA '10, London, UK, July 26-28, 2010. Proceedings). Lecture Notes in Computer Science, vol. 6460, Springer, Berlin, pp. 337-348. https://doi.org/10.1007/978-3-642-19222-7_34

Ranking and drawing in subexponential time. / Fernau, H.; Fomin, F.V.; Lokshtanov, D. et al.
Combinatorial Algorithms (21st International Workshop, IWOCA '10, London, UK, July 26-28, 2010. Proceedings). ed. / C.S. Iliopoulos; W.F. Smyth. Berlin: Springer, 2011. p. 337-348 (Lecture Notes in Computer Science; Vol. 6460).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Ranking and drawing in subexponential time

AU - Fernau, H.

AU - Fomin, F.V.

AU - Lokshtanov, D.

AU - Mnich, M.

AU - Philip, G.

AU - Saurabh, S.

PY - 2011

Y1 - 2011

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

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

U2 - 10.1007/978-3-642-19222-7_34

DO - 10.1007/978-3-642-19222-7_34

M3 - Conference contribution

SN - 978-3-642-19221-0

T3 - Lecture Notes in Computer Science

SP - 337

EP - 348

BT - Combinatorial Algorithms (21st International Workshop, IWOCA '10, London, UK, July 26-28, 2010. Proceedings)

A2 - Iliopoulos, C.S.

A2 - Smyth, W.F.

PB - Springer

CY - Berlin

ER -

Ranking and drawing in subexponential time

Abstract

Publication series

Access to Document

Fingerprint

Cite this