How Hard is Control in Multi-Peaked Elections: A Parameterized Study

We study the complexity of voting control problems in multi-peaked elections. In particular, we focus on the constructive/destructive control by adding/deleting votes under Condorcet, Maximin and Copeland α voting systems. We show that the N P-hardness of these problems (except for the destructive control by adding/deleting votes under Condorcet, which is polynomial-time solvable in the general case) hold even in κ-peaked elections with κ being a very small constant. Furthermore, from the parameterized complexity point of view, our reductions actually show that these problems are W[1]-hard in κ-peaked elections with κ = 3, 4, with respect to the number of added/deleted votes.