License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-28866
URL:

; ; ; ;

Determining the Winner of a Dodgson Election is Hard

pdf-format:


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

BibTeX - Entry

@InProceedings{fellows_et_al:LIPIcs:2010:2886,
  author =	{Michael Fellows and Bart M. P. Jansen and Daniel Lokshtanov and Frances A. Rosamond and Saket Saurabh},
  title =	{{Determining the Winner of a Dodgson Election is Hard}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{459--468},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Kamal Lodaya and Meena Mahajan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2886},
  URN =		{urn:nbn:de:0030-drops-28866},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.459},
  annote =	{Keywords: Dodgson Score, Parameterized Complexity, Kernelization Lower Bounds}
}

Keywords: Dodgson Score, Parameterized Complexity, Kernelization Lower Bounds
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Issue date: 2010
Date of publication: 2010


DROPS-Home | Fulltext Search | Imprint Published by LZI