Font Size: 

The Possible Winner problem asks whether some distinguished candidate may  become the winner of an election when the given incomplete votes are extended into complete ones in a favorable way. Possible Winner is NP-complete for common voting rules such as Borda, many other positional scoring rules, Bucklin, Copeland etc.  We investigate how three different parameterizations influence the computational complexity of Possible Winner for a number of voting rules.  We show  fixed-parameter tractability results with respect to the parameter "number of candidates" but intractability results with respect to the parameter "number of votes". Finally, we derive fixed-parameter tractability results with respect to the parameter "total number of undetermined candidate pairs" and identify an interesting polynomial-time solvable special case for Borda.