2026-07-22T00:07:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2886 2024-03-06T10:33:41Z ddc:004 open_access

Determining the Winner of a Dodgson Election is Hard Fellows, Michael Jansen, Bart M. P. Lokshtanov, Daniel Rosamond, Frances A. Saurabh, Saket Dodgson Score Parameterized Complexity Kernelization Lower Bounds 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]$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Fellows and Bart M. P. Jansen and Daniel Lokshtanov and Frances A. Rosamond and Saket Saurabh 2010 Is Part Of LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2010.459 urn:nbn:de:0030-drops-28866 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.459 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode