  We consider election scenarios with incomplete information, a situation that
arises often in practice. There are several models of incomplete information
and accordingly, different notions of outcomes of such elections. In one
well-studied model of incompleteness, the votes are given by partial orders
over the candidates. In this context we can frame the problem of finding a
possible winner, which involves determining whether a given candidate wins in
at least one completion of a given set of partial votes for a specific voting
rule.
  The possible winner problem is well-known to be NP-complete in general, and
it is in fact known to be NP-complete for several voting rules where the number
of undetermined pairs in every vote is bounded only by some constant. In this
paper, we address the question of determining precisely the smallest number of
undetermined pairs for which the possible winner problem remains NP-complete.
In particular, we find the exact values of $t$ for which the possible winner
problem transitions to being NP-complete from being in P, where $t$ is the
maximum number of undetermined pairs in every vote. We demonstrate tight
results for a broad subclass of scoring rules which includes all the commonly
used scoring rules (such as plurality, veto, Borda, $k$-approval, and so on),
Copeland$^\alpha$ for every $\alpha\in[0,1]$, maximin, and Bucklin voting
rules. A somewhat surprising aspect of our results is that for many of these
rules, the possible winner problem turns out to be hard even if every vote has
at most one undetermined pair of candidates.
