Parameterized Complexity of Multi-winner Determination: More Effort Towards Fixed-Parameter Tractability

摘要

We study the k-committee selection rules minimax approval, proportional approval, and Chamberlin-Courant's approval. It is known that WINNER DETERMINATION for these rules is NP-hard. Moreover, the parameterized complexity of the problem has also been studied with respect to some natural parameters. However, there are still numerous parameterizations that have not been considered. We revisit the parameterized complexity of WINNER DETERMINATION for these rules by considering several important single parameters, combined parameters, and structural parameters, aiming at detecting as many fixed-parameter tractability results as possible.