Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, Simon Wietheger · 2026
Read Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study by Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, Simon Wietheger (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25734.txt.
Introduction
Bai and four colleagues study rank aggregation under the Ulam metric, an edit distance on permutations. Center minimizes the worst distance to input rankings; median minimizes total distance. Both are NP-hard even for one center. The authors prove k-center stays NP-hard at budget one, yet becomes fixed-parameter tractable in centers plus budget through local search. No polynomial kernel exists there unless NP sits inside coNP/poly. For k-median they prove W[1]-hardness, give an XP algorithm, and a kernel yielding tractability.
Catalog record
| CREATOR | Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, Simon Wietheger |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 112756 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.25734
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, Simon Wietheger Abstract Rank aggregation seeks a representative permutation for a collection of rankings and plays a central role in areas such as social choice, information retrieval, and computational biology. Two fundamental aggregation tasks are the center and median problems, which minimize the maximum and the total distance to the input permutations, respectively. While these problems are well understood under Kendall’s tau and related distances, their parameterized complexity under the Ulam metric, an edit-distance-based metric on permutations, has remained largely unexplored. In this work, we initiate a systematic study of the parameterized complexity of rank aggregation under the Ulam metric. We consider both the center and median problems, as well as their generalizations to the k k -center and k k -median clustering settings, parameterized by the number of centers k k and the distance budget d d (corresponding to the maximum distance for center variants and the total distance for median variants). Both problems are known to be NP-hard already for k = 1 k=1 . We show that the Ulam k k -center problem remains NP-hard when d = 1 d=1 , but is fixed-parameter tractable when parameterized by k + d k+d . Our algorithm is based on a novel local-search framework tailored to the non-local nature of Ulam distances. We complement this by proving that no polynomial kernel exists for the k + d k+d parameterization unless 𝖭𝖯 ⊆ 𝖼𝗈𝖭𝖯 / 𝗉𝗈𝗅𝗒 {\mathsf{NP}}\subseteq{\mathsf{coNP}}/{\mathsf{poly}} . For the Ulam k k -median problem parameterized by the total distance d d , we establish 𝖶 [ 1 ] {\mathsf{W}}[1] -hardness and provide an 𝖷𝖯 {\mathsf{XP}} algorithm. We also provide a polynomial kernel for the parameter k + d k+d , which in turn yields a fixed-parameter tractable algorithm. University of Bergen, Bergen, [email protected]://orcid.org/0000-0003-1669-285XFunded by the European Union, GA # 101126560; Bergen research and training program for future AI leaders across the disciplines, LEAD AI and by the Trond Mohn forskningsstiftelse (grant no. TMS2023TMT01). University of Bergen, Bergen, [email protected]://orcid.org/0000-0003-1955-4612Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (NewPC grant agreement No. 101199930). University of Bergen, Bergen, [email protected]://orcid.org/0000-0002-2619-2990Supported by the Research Council of Norway under the BWCA (grant no. 314528) and Extreme-Algorithms (grant no 355137) projects. University of Bergen, Bergen, [email protected]://orcid.org/0000-0003-8651-6686Supported by the Trond Mohn forskningsstiftelse (grant no. TMS2023TMT01). TU Wien, Vienna, [email protected]://orcid.org/0000-0002-0734-0708Supported by the Austrian Science Foundation (FWF, project 10.55776/Y1329). ccs Theory of computation Parameterized complexity and exact algorithms ccs Mathematics of computing Permutations and combinations keywords parameterized complexity, Ulam distance, rank aggregation, clustering † † runningtitle: Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study † † runningauthor: T. Bai, F. V. Fomin, P. A. Golovach, Y. H. More, S. Wietheger † † copyright: Tian Bai, Fedor V. Fomin, Petr. A. Golovach, Yash Hire More, Simon Wietheger † † editors: Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis † † event-title: 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) † † event-shorttitle: ICALP 2026 † † event-acronym: ICALP † † year: 2026 † † event-date: July 7–10, 2026 † † event-location: Royal Holloway, University of London, Egham, United Kingdom † † series-volume: 374 † † articleno: 57 1 Introduction Rank aggregation is the problem of computing a representative ranking from a collection of permutations representing the preferences of individual voters. The roots for a mathematical investigation of this problem can be traced back to early studies of social choice theory and voting systems like Borda (1781) and Condorcet (1785), as well as later seminal works such as the ones by Arrow [ 4 ] or Diaconis and Graham [ 20 ] . Rank aggregation constitutes a fundamental task with broad applications in social choice theory, information retrieval, computational biology, and database systems [ 1 , 4 , 21 , 31 , 19 ] . Algorithmically, two canonical rank aggregation tasks are to compute the center and the median of permutations. Given a distance function \mathrm{dist}(\cdot,\cdot) on the space {{\cal S}}_{n} of permutations over n symbols, the center of a permutation set \Pi\subseteq{{\cal S}}_{n} is a permutation \sigma\in{{\cal S}}_{n} minimizing \max_{\pi\in\Pi}\mathrm{dist}(\pi,\sigma), whereas the median of \Pi is a permutation \sigma\in{{\cal S}}_{n} minimizing \sum_{\pi\in\Pi}\mathrm{dist}(\pi,\sigma). Among distance measures for rank aggregation, Kendall’s tau and the Ulam metric are the two most natural and fundamental metrics, extensively studied in both theory and applications [ 14 ] . Kendall’s tau distance counts the number of pairwise disagreements between two permutations, thereby capturing local inconsistencies in ranking order. In contrast, the Ulam metric is an edit distance that measures the minimum number of element move operations (deletion and insertion) required to transform one permutation into another. This metric captures global structural differences by isolating the longest common subsequence (the elements that are not moved) and quantifying how many elements must be relocated to achieve alignment. The tasks of computing centers and medians under Kendall’s tau metric are well understood from different computational perspectives [ 2 , 10 , 21 , 22 , 28 , 31 , 34 ] . Finding the optimal center or median under Kendall’s tau is {\mathsf{NP}} -hard already if there are just four input permutations [ 10 , 21 ] . Additionally, the median under Kendall’s tau, also known as Kemeny rankings , admits a polynomial-time approximation scheme (PTAS) [ 28 ] . Both versions of rank aggregation under Kendall’s tau admit fixed-parameter tractable (FPT) algorithms parameterized by the solution cost [ 5 , 7 ] , and other natural parameters [ 9 , 8 , 16 , 17 , 23 ] . In contrast, the study of rank aggregation under the Ulam metric is relatively unexplored, especially from the perspective of parameterized complexity. A key reason is that Ulam distance is a global measure whose combinatorial structure is inherently harder to exploit algorithmically than the local nature of Kendall’s tau. Consequently, some algorithmic work has focused on estimating the distance itself. Andoni and Nguyen [ 3 ] and Naumovitz et al. [ 30 ] developed sublinear-time approximation schemes to estimate the Ulam distance between two permutations, using connections to calculate the longest common subsequence. Finding an optimal center under the Ulam metric was shown to be {\mathsf{NP}} -hard over a decade ago [ 5 ] , while the median problem was only recently proven {\mathsf{NP}} -hard [ 24 ] . A folklore 2 -approximation exists for both the median and center variants under the Ulam metric. Recently, Chakraborty et al. [ 15 ] obtained a (1.5-\varepsilon) -approximation (with any \varepsilon>0 ) for the center problem with running time exponential in m (the number of input permutations). At a similar time, the first approximation algorithm to break the barrier of 2 for the median problem appeared [ 12 ] . The subsequent work [ 13 ] extends the approximation framework to the setting of finding k medians, achieving a similar approximation guarantee in time (k\log(mn))^{{{\cal O}}(k)}mn^{3} , where n is the size of the alphabet and m is the number of input permutations. Very recently, Jaiswal et al. [ 27 ] improved on this work and provide