Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Determining the winner of a Dodgson election is hard

Fellows, Michael R., Jansen, Bart, Lokshtanov, Daniel, Rosamond, Frances A. and Saurabh, Saket (2010). Determining the winner of a Dodgson election is hard. In: Lodaya, Kamal and Mahajan, Meena IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), Chennai, India, 15-18 December 2010.

Document type: Conference Paper
Attached Files (Some files may be inaccessible until you login with your CDU eSpace credentials)
Name Description MIMEType Size Downloads
Download this reading Fellows_9585.pdf Published version application/pdf 2.01MB 13
Reading the attached file works best in Firefox, Chrome and IE 9 or later.

IRMA ID 81704288xPUB482
Author Fellows, Michael R.
Jansen, Bart
Lokshtanov, Daniel
Rosamond, Frances A.
Saurabh, Saket
Title Determining the winner of a Dodgson election is hard
Conference Name IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Conference Location Chennai, India
Conference Dates 15-18 December 2010
Conference Publication Title IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Editor Lodaya, Kamal
Mahajan, Meena
Place of Publication Germany
Publisher LIPICS
Publication Year 2010
Volume Number 8
ISBN 978-3-939897-23-1   (check CDU catalogue  open catalogue search in new window)
ISSN 1868-8969   (check CDU catalogue  open catalogue search in new window)
Start Page 459
End Page 468
Total Pages 10
Field of Research 0802 - Computation Theory and Mathematics
HERDC Category E1 - Conference Publication (DIISR)
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]$.
Keyword Dodgson Score
Parameterized Complexity
Kernelization Lower Bounds
Additional Notes http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.459 This is an Open Access article distributed under the terms of the Creative Commons Attribution License 3.0, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Description for Link Link to published version
Link to CC Attribution 3.0 License
URL http://drops.dagstuhl.de/opus/volltexte/2010/2886/pdf/40.pdf
http://creativecommons.org/licenses/by-nc-nd/3.0/


© copyright

Every reasonable effort has been made to ensure that permission has been obtained for items included in CDU eSpace. If you believe that your rights have been infringed by this repository, please contact digitisation@cdu.edu.au.

 
Versions
Version Filter Type
Access Statistics: 57 Abstract Views, 15 File Downloads  -  Detailed Statistics
Created: Tue, 28 Feb 2012, 23:09:41 CST