A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes

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.

Nadja Betzler, Susanne Hemmann, Rolf Niedermeier