Name
Abstract | ||
|---|---|---|
Computing the Dodgson Score of a candidate in an election is a hard computational problem, which has been analyzed using classical and parameterized analysis. In this paper we resolve two open problems regarding the parameterized complexity of Dodgson Score. We show that Dodgson Score parameterized by the target score value k does not have a polynomial kernel unless the polynomial hierarchy collapses to the third level; this complements a result of Fellows, Rosamond and Slinko who obtain a non-trivial kernel of exponential size for a generalization of this problem. We also prove that Dodgson Score parameterized by the number n of votes is hard for W[1]. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.4230/LIPIcs.FSTTCS.2010.459 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
Dodgson Score,Parameterized Complexity,Kernelization Lower Bounds | Polynomial hierarchy,Kernel (linear algebra),Discrete mathematics,Parameterized complexity,Computational problem,Combinatorics,Exponential function,Polynomial kernel,Mathematics | Conference |
Volume | ISSN | Citations |
8 | 1868-8969 | 2 |
PageRank | References | Authors |
0.64 | 7 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael R. Fellows | 1 | 4138 | 319.37 |
| Bart M. P. Jansen | 2 | 232 | 20.86 |
| Daniel Lokshtanov | 3 | 1438 | 110.05 |
| Frances A. Rosamond | 4 | 304 | 15.94 |
| Saket Saurabh | 5 | 2023 | 179.50 |