Parameterized Aspects of Distinct Kemeny Rank Aggregation
This work addresses the problem of efficient rank aggregation for computational social choice and data analysis, but it is incremental as it builds on existing FPT algorithms for known parameters.
The paper tackles the computational challenge of finding all distinct Kemeny rankings, which is NP-hard, by analyzing parameterized complexity with respect to various parameters and shows that desirable numbers of rankings can be found without substantial runtime increases, also providing FPT approximation algorithms.
The Kemeny method is one of the popular tools for rank aggregation. However, computing an optimal Kemeny ranking is NP-hard. Consequently, the computational task of finding a Kemeny ranking has been studied under the lens of parameterized complexity with respect to many parameters. We first present a comprehensive relationship, both theoretical and empirical, among these parameters. Further, we study the problem of computing all distinct Kemeny rankings under the lens of parameterized complexity. We consider the target Kemeny score, number of candidates, average distance of input rankings, maximum range of any candidate, and unanimity width as our parameters. For all these parameters, we already have FPT algorithms. We find that any desirable number of Kemeny rankings can also be found without substantial increase in running time. We also present FPT approximation algorithms for Kemeny rank aggregation with respect to these parameters.