Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers

Approval ballots provide an opportunity for agents to make a comment about every candidate, without incurring the overhead of determining a full ranking on the set of candidates; they are very natural for many practical settings. We study the computational complexity of the committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outliers render the committee selection problem intractable for approval, net approval, and minisum approval voting rules. We next study the parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter namely the number of candidates outside the committee)-, and the number of outliers (and its dual parameter namely the number of non-outliers). For approval, net approval, and minisum approval voting rules, we provide a dichotomous result, whiph resolves the parameterized complexity of this problem for all subsets of the above five natural parameters considered (by showing cither FPT or W[l]-hardncss for all subsets of parameters).