On the Parameter­ized Complexity of Party Nominations

Consider a fixed voting rule R. In the Possible President problem, we are given an election where the candidates are partitioned into parties, and the problem is to determine if, given a party P, it is possible for every party to nominate a candidate such that the nominee from P is a winner of the election that is obtained by restricting the votes to the nominated candidates. In the Necessary President problem, we would like to find a nominee who wins no matter who else is nominated. In this talk, we explore the complexity of these problems, which can be thought of as the two natural extremes of the party nomination problem, with an emphasis on a parameterized perspective and algorithms on structured profiles.