Kernelization Complexity of Possible Winner and Coalitional Manipulation Problems in Voting

In the P W problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the P W problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge [10]. In this paper, we settle this open question for many common voting rules. We show that the P W problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that include the Borda voting rule do not admit a polynomial kernel with the number of candidates as the parameter. We show however that the C M problem which is an important special case of the P W problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the P W problem is harder than the C M problem since the C M problem admits a polynomial kernel whereas the P W problem does not admit a polynomial kernel.