License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.459
URN: urn:nbn:de:0030-drops-28866
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2886/
Go to the corresponding LIPIcs Volume Portal

Fellows, Michael ; Jansen, Bart M. P. ; Lokshtanov, Daniel ; Rosamond, Frances A. ; Saurabh, Saket

Determining the Winner of a Dodgson Election is Hard

pdf-format:
40.pdf (0.4 MB)

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 =		{10.4230/LIPIcs.FSTTCS.2010.459},
  annote =	{Keywords: Dodgson Score, Parameterized Complexity, Kernelization Lower Bounds}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI