Complexity of Controlling Nearly Single-Peaked Elections Revisited

In this paper, we investigate the complexity of Constructive Control by Adding/Deleting Votes (CCAV/CCDV) for r-approval, Condorcet, Maximin and Copeland α in k-axes and k-candidate partition single-peaked elections. In general, we prove that CCAV and CCDV for most of the voting correspondences mentioned above are NP-hard even when k is a very small constant. Exceptions are CCAV and CCDV for Condorcet and CCAV for r-approval in k-axes singlepeaked elections, which we show to be fixed-parameter tractable with respect to k. In addition, we give a polynomial-time algorithm for recognizing 2-axes elections, resolving an open question.