Determining the Winner of a Dodgson Election is Hard

M.R. Fellows; B.M.P. Jansen; D. Lokshtanov; F.A. Rosamond; S. Saurabh

doi:10.4230/LIPIcs.FSTTCS.2010.459

Determining the Winner of a Dodgson Election is Hard

M.R. Fellows, B.M.P. Jansen, D. Lokshtanov, F.A. Rosamond, S. Saurabh

extern

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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

Original language	English
Title of host publication	Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Editors	K. Lodaya, M. Mahajan
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Pages	459-468
Number of pages	10
DOIs	https://doi.org/10.4230/LIPIcs.FSTTCS.2010.459
Publication status	Published - 15 Dec 2010

Bibliographical note

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Access to Document

10.4230/LIPIcs.FSTTCS.2010.459

Cite this

Fellows, M. R., Jansen, B. M. P., Lokshtanov, D., Rosamond, F. A., & Saurabh, S. (2010). Determining the Winner of a Dodgson Election is Hard. In K. Lodaya, & M. Mahajan (Eds.), Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) (pp. 459-468). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2010.459

@inproceedings{48f89956da8d4c14a85acb1d6dd629b2,

title = "Determining the Winner of a Dodgson Election is Hard",

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].",

author = "M.R. Fellows and B.M.P. Jansen and D. Lokshtanov and F.A. Rosamond and S. Saurabh",

note = "IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)",

year = "2010",

month = dec,

day = "15",

doi = "10.4230/LIPIcs.FSTTCS.2010.459",

language = "English",

pages = "459--468",

editor = "K. Lodaya and M. Mahajan",

booktitle = "Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik",

}

Fellows, MR, Jansen, BMP, Lokshtanov, D, Rosamond, FA & Saurabh, S 2010, Determining the Winner of a Dodgson Election is Hard. in K Lodaya & M Mahajan (eds), Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 459-468. https://doi.org/10.4230/LIPIcs.FSTTCS.2010.459

Determining the Winner of a Dodgson Election is Hard. / Fellows, M.R.; Jansen, B.M.P.; Lokshtanov, D. et al.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). ed. / K. Lodaya; M. Mahajan. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010. p. 459-468.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Determining the Winner of a Dodgson Election is Hard

AU - Fellows, M.R.

AU - Jansen, B.M.P.

AU - Lokshtanov, D.

AU - Rosamond, F.A.

AU - Saurabh, S.

N1 - IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

PY - 2010/12/15

Y1 - 2010/12/15

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

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

U2 - 10.4230/LIPIcs.FSTTCS.2010.459

DO - 10.4230/LIPIcs.FSTTCS.2010.459

M3 - Conference contribution

SP - 459

EP - 468

BT - Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

A2 - Lodaya, K.

A2 - Mahajan, M.

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

CY - Dagstuhl, Germany

ER -

Fellows MR, Jansen BMP, Lokshtanov D, Rosamond FA, Saurabh S. Determining the Winner of a Dodgson Election is Hard. In Lodaya K, Mahajan M, editors, Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. 2010. p. 459-468 doi: 10.4230/LIPIcs.FSTTCS.2010.459

Determining the Winner of a Dodgson Election is Hard

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this