Can I read Parameterized Computational Complexity of Control Problems in Voting Systems on EtoBox?

Parameterized Computational Complexity of Control Problems in Voting Systems by Hong Liu; Haodi Feng; Daming Zhu; Junfeng Luan is a Computer Science article available to read on EtoBox.

What is Parameterized Computational Complexity of Control Problems in Voting Systems about?

Voting systems are common tools in a variety of areas. This paper studies parameterized computational complexity of control of Plurality, Condorcet and Approval voting systems, respectively. The types of controls considered include adding or deleting candidates or voters, under constructive or destructive setting. We obtain the following results: (1) constructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter ''number of added candidates'', (2) destructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter ''number of added candidates'', (3) constructive control by adding voters in Condorcet voting is W[1]-hard with respect to the parameter ''number of added voters'', (4) constructive control by deleting voters in Condorcet voting is W[1]-hard with respect to the parameter ''number of deleted voters'', (5) constructive control by adding voters in Approval voting is W[1]-hard with respect to the parameter ''number of added voters'', and (6) constructive control by deleting voters in Approval voting is W[2]-hard with respect to the parameter ''number of deleted voters''.

Who reads Parameterized Computational Complexity of Control Problems in Voting Systems?

Author

Hong Liu; Haodi Feng; Daming Zhu; Junfeng Luan

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

2009

Language

EN

Field

Computer Science (Physical Sciences)