IJCAI Conference 2009 Conference Paper
- Nadja Betzler
- Susanne Hemmann
- Rolf Niedermeier
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 in- fluence the computational complexity of POSSI- BLE 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 fixedparameter tractability results with respect to the parameter “total number of undetermined candidate pairs” and identify an interesting polynomial-time solvable special case for Borda.