On the parameterized complexity of party nominations

Consider a fixed voting rule. 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, it is possible for every party to nominate a candidate such that the nominee from is a winner of the election that is obtained by restricting the votes to the nominated candidates. In previous work on this problem, proposed by [10], it was established that Possible President is NP-hard even when the voting rule is Plurality and the election is restricted to single-peaked votes. In this contribution, we initiate a study of the parameterized complexity of the problem. Our main result is that for a natural choice of parameter (namely the number of parties), the problem is W[2]-hard in general but is FPT on the 1D-Euclidean domain. On the other hand, if we parameterize by the size of the largest party, we encounter para-NP-hardness even on profiles that are both single-peaked and single-crossing. This strengthens previously established hardness results. We also show a polynomial time result for the related Necessary President problem on single-crossing elections.