Abstract

The P OSSIBLE W INNER problem asks whether some distinguished candidate may become the win-ner of an election when the given incomplete votes are extended into complete ones in a favorable way. P OSSIBLE W INNER is NP-complete for com-mon voting rules such as Borda, many other posi-tional scoring rules, Bucklin, Copeland etc. We in-vestigate how three different parameterizations in-fluence the computational complexity of P OSSI-BLE W INNER for a number of voting rules. We show fixed-parameter tractability results with re-spect to the parameter “number of candidates” but intractability results with respect to the parame-ter “number of votes”.  Finally, we derive fixed-parameter tractability results with respect to the pa-rameter “total number of undetermined candidate pairs” and identify an interesting polynomial-time solvable special case for Borda