  In the Possible Winner 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 Possible Winner 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. In
this paper, we settle this open question for many common voting rules.
  We show that the Possible Winner 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 Coalitional Manipulation problem which is
an important special case of the Possible Winner 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 Possible Winner problem is harder than the Coalitional Manipulation
problem since the Coalitional Manipulation problem admits a polynomial kernel
whereas the Possible Winner problem does not admit a polynomial kernel.
