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

07/09/2021
by   Yongjie Yang, et al.
0

We study winner determination for three prevalent k-committee selection rules, namely minimax approval voting (MAV), proportional approval voting (PAV), and Chamberlin-Courant's approval voting (CCAV). It is known that winner determination for these rules is NP-hard. Parameterized complexity of the problem has been studied with respect to some natural parameters recently. However, there are still numerous parameters that have not been considered. We revisit the parameterized complexity of winner determination by considering several important single parameters, combined parameters, and structural parameters, aiming at detecting more interesting parameters leading to fixed-parameter tractability res

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset