The Control Complexity of r-Approval: From the Single-Peaked Case to the General Case

A natural generalization of the single-peaked elections is the k-peaked elections, where at most k peaks are allowed in each vote. Motivated by N P-hardness in general and polynomial-time solvability in single-peaked elections, we aim at establishing a complexity dichotomy of several control problems for r-approval voting in k-peaked elections with respect to k. It turns out that most N P-completeness results in general also hold in k-peaked elections, even for k = 2, 3. On the other hand, we derive polynomial-time algorithms for certain control problems for k = 2. In addition, we also study the problems from the viewpoint of parameterized complexity and achieve both F PT and W-hardness results. Several of our results apply to approval voting and sincere-strategy preference-based approval voting as well.