---
title: "A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes"
authors:
  - "Nadja Betzler"
  - "Susanne Hemmann"
  - "Rolf Niedermeier"
doi: ""
url: "https://ijcai.org/proceedings/2009/20"
pdf: "https://ijcai.org/proceedings/2009/0020.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "53-57"
track: ""
keywords:
---

# A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes

Nadja Betzler, Susanne Hemmann, Rolf Niedermeier

*Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence*, pages 53-57.

## Abstract

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