Controlling Elections with Bounded Single-Peaked Width

The problems of controlling an election have been shown N P-complete in general but polynomial-time solvable in single-peaked elections for many voting correspondences. To explore the complexity border, we consider these control problems by adding/deleting votes in elections with bounded single-peaked width k. Single-peaked elections have singlepeaked width k = 1. We prove that the constructive control problems for Copeland α with 0 ≤ α < 1 turn out to be N Phard even with k = 2, while for Copeland 1 and Maximin, the constructive control problems remain polynomial-time solvable with k = 2 but become N P-hard with k = 3. In contrast, we show that the constructive control problems for Condorcet and weak Condorcet and the destructive control problems for Maximin and Copeland α with 0 ≤ α ≤ 1 are all polynomial-time solvable with k being a constant; more precisely, these problems are fixed-parameter tractable (FPT) with k as parameter. A byproduct of our results is that the Young winner determination problem is FPT with respect to k. Finally, for the class of voting correspondences passing the Smith-IIA criterion we provide a general characterization to identify voting correspondences whose control problems are FPT with respect to k.