pith. sign in

arxiv: 2604.25734 · v1 · submitted 2026-04-28 · 💻 cs.DS · cs.CC

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study

Tian Bai , Fedor V. Fomin , Petr A. Golovach , Yash Hiren More , Simon Wietheger This is my paper

Pith reviewed 2026-05-07 15:02 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords Ulam metricrank aggregationk-centerk-medianparameterized complexitypermutationsfixed-parameter tractabilitypolynomial kernel
0
0 comments X

The pith

The Ulam k-center problem on permutations is NP-hard for d=1 yet fixed-parameter tractable and admits a polynomial kernel when parameterized by k plus d.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper initiates a parameterized complexity analysis of rank aggregation under the Ulam metric, which counts the minimum insertions and deletions needed to convert one permutation into another. It focuses on the k-center problem that minimizes the largest distance from any input permutation to a chosen center, and the k-median problem that minimizes the sum of distances. The central finding is that k-center remains NP-hard even when the distance bound d equals 1, but both problems become fixed-parameter tractable for the combined parameter k plus d, supported by a polynomial kernel that reduces the instance size. For k-median the work additionally establishes W[1]-hardness when parameterized by d alone while supplying an XP algorithm.

Core claim

The Ulam k-center problem remains NP-hard when d=1, but is fixed-parameter tractable when parameterized by k+d. The algorithm relies on a novel local-search framework that handles the non-local character of Ulam distances. No polynomial kernel exists for the k+d parameterization unless NP is contained in coNP/poly. For the Ulam k-median problem parameterized by d the problem is W[1]-hard and admits only an XP algorithm, yet a polynomial kernel exists for the combined parameter k+d and therefore yields an FPT algorithm.

What carries the argument

A novel local-search framework tailored to the non-local nature of Ulam distances on permutations, which enables the design of the FPT algorithm and kernel for the k+d parameterization.

If this is right

  • Ulam k-center admits an FPT algorithm parameterized by k+d.
  • Ulam k-center has no polynomial kernel for parameter k+d unless NP is contained in coNP/poly.
  • Ulam k-median is W[1]-hard parameterized by d alone.
  • Ulam k-median admits an XP algorithm parameterized by d.
  • Ulam k-median has a polynomial kernel for parameter k+d, yielding an FPT algorithm.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The local-search technique may extend to clustering under other string-edit metrics on sequences beyond permutations.
  • Rank-aggregation tasks in voting or genomics with modest numbers of clusters and limited disagreement can be solved exactly after kernelization.
  • The differing hardness profiles of the center and median objectives under the same metric indicate that the choice of aggregation criterion strongly influences which parameters yield tractability.

Load-bearing premise

The local-search procedure correctly accounts for the global edit operations that define Ulam distance while keeping the search space bounded by a function of k and d.

What would settle it

An explicit small instance with k=3 and d=4 on which the local-search algorithm returns a clustering whose maximum Ulam distance exceeds the claimed optimum would falsify the FPT result; equivalently, a reduction proving W[1]-hardness for k-center parameterized by k+d.

read the original 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$-center and $k$-median clustering settings, parameterized by the number of centers $k$ and the distance budget $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$. We show that the Ulam $k$-center problem remains NP-hard when $d=1$, but is fixed-parameter tractable when parameterized by $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$ parameterization unless NP $\subseteq$ coNP/poly. For the Ulam $k$-median problem parameterized by the total distance $d$, we establish W[1]-hardness and provide an XP algorithm. We also provide a polynomial kernel for the parameter $k + d$, which in turn yields a fixed-parameter tractable algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript initiates a parameterized complexity analysis of rank aggregation under the Ulam metric, focusing on the k-center and k-median problems (and their single-center special cases) parameterized by the number of centers k and distance budget d. It claims that Ulam k-center is NP-hard already for d=1 yet FPT for parameter k+d via a novel local-search framework that handles the non-local character of Ulam distance; that no polynomial kernel exists for k+d unless NP ⊆ coNP/poly; that Ulam k-median is W[1]-hard for parameter d (with an XP algorithm) yet admits a polynomial kernel for k+d that yields FPT.

Significance. If the algorithmic and hardness claims hold, the paper supplies the first systematic FPT landscape for Ulam-based clustering, cleanly separating the center and median variants and introducing a local-search technique adapted to edit-distance non-locality. The polynomial kernel for k+d on both problems and the explicit W[1]-hardness for median-by-d are technically substantive contributions that could inform similar studies on other permutation metrics.

major comments (2)
  1. [local-search framework] The central FPT claim for Ulam k-center parameterized by k+d rests on the correctness of the novel local-search framework; without the full description of how the framework enumerates and verifies candidate centers while accounting for the non-local Ulam distance (including any implicit distance-oracle assumptions), it is impossible to confirm that every step supports the stated running time.
  2. [hardness reduction for k-median] The W[1]-hardness reduction for Ulam k-median parameterized by d is a load-bearing negative result; the manuscript must explicitly verify that the reduction preserves the Ulam distance properties and does not inadvertently create instances where the total distance budget can be satisfied by local edits only.
minor comments (2)
  1. [abstract] The abstract states an XP algorithm for k-median by d but does not indicate its dependence on n or d; a brief sentence clarifying the exponent would improve readability.
  2. [kernelization section] The no-kernel result for k-center is stated only in the abstract; the manuscript should include a short pointer to the coNP/poly assumption and the standard kernelization lower-bound technique employed.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the two major comments below by committing to targeted expansions that strengthen the exposition without altering the technical claims.

read point-by-point responses

  1. Referee: [local-search framework] The central FPT claim for Ulam k-center parameterized by k+d rests on the correctness of the novel local-search framework; without the full description of how the framework enumerates and verifies candidate centers while accounting for the non-local Ulam distance (including any implicit distance-oracle assumptions), it is impossible to confirm that every step supports the stated running time.

    Authors: We agree that the current description of the local-search framework would benefit from greater explicitness. In the revision we will add a self-contained subsection containing (i) full pseudocode for the enumeration and verification of candidate centers, (ii) a precise accounting of how non-local Ulam edits are handled at each step, and (iii) a line-by-line running-time analysis that makes every oracle call and data-structure operation explicit. This will eliminate any ambiguity regarding implicit assumptions and confirm the claimed FPT bound. revision: yes

  2. Referee: [hardness reduction for k-median] The W[1]-hardness reduction for Ulam k-median parameterized by d is a load-bearing negative result; the manuscript must explicitly verify that the reduction preserves the Ulam distance properties and does not inadvertently create instances where the total distance budget can be satisfied by local edits only.

    Authors: We concur that an explicit verification of the reduction is required. The revised manuscript will include a new lemma together with a dedicated paragraph that (a) proves the Ulam distance between constructed permutations equals the distance in the source instance, and (b) shows by direct calculation that any solution satisfying the budget must perform the global edits encoded by the reduction rather than relying on local transpositions. Concrete distance computations on the reduced instances will be supplied to illustrate the argument. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's claims rest on new algorithmic constructions (novel local-search framework for Ulam k-center FPT by k+d) and explicit reductions (NP-hardness for d=1, W[1]-hardness for k-median by d, no poly kernel unless NP coNP/poly). The polynomial kernel for k+d is stated to yield FPT via standard kernelization, with no self-referential definitions, fitted inputs renamed as predictions, or load-bearing self-citations. All steps are independent proofs and algorithms as described in the abstract; no equation or claim reduces to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard complexity-theoretic assumptions and classical parameterized-algorithm techniques without introducing new free parameters or postulated entities.

axioms (1)
  • domain assumption NP is not contained in coNP/poly
    Invoked to establish the polynomial-kernel lower bound for k-center parameterized by k+d.

pith-pipeline@v0.9.0 · 5619 in / 1203 out tokens · 108424 ms · 2026-05-07T15:02:02.127768+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    1 Alok Aggarwal and Jeffrey S. Vitter. The input/output complexity of sorting and related problems.Communications of the ACM, 31(9):1116–1127, 1988.doi:10.1145/48529.48535. 2 Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering.Journal of the ACM, 55(5):23:1–23:27, 2008.doi:10.1145/1411509. 1411513. 3...

    work page doi:10.1145/48529.48535 1988

  2. [2]

    jstor.org/stable/j.ctt1nqb90

    URL: http://www. jstor.org/stable/j.ctt1nqb90. 5 Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, and Andreas Hofmeier. On the hardness of maximum rank aggregation problems.Journal of Discrete Algorithms, 31:2–13, 2015.doi:10.1016/j.jda.2014.10.002. 6 Manu Basavaraju, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan, and Saket Saurabh. On the kern...

    work page doi:10.1016/j.jda.2014.10.002 2015

  3. [3]

    URL: https://www

    Algorithmic Aspects in Information and Management. URL: https://www. sciencedirect.com/science/article/pii/S0304397509005696, doi:10.1016/j.tcs.2009. 08.033. 8 Nadja Betzler, Jiong Guo, and Rolf Niedermeier. Parameterized computational complexity of Dodgson and Young elections.Information and Computation, 208(2):165–177,

    work page doi:10.1016/j.tcs.2009 2009

  4. [4]

    9 Nadja Betzler, Jiong Guo, Rolf Niedermeier, and Johannes Uhlmann

    doi:10.1016/j.ic.2009.10.001. 9 Nadja Betzler, Jiong Guo, Rolf Niedermeier, and Johannes Uhlmann. Parameterized complexity of candidate control in elections and related digraph problems.Theoretical Computer Science, 410:5425–5442, 2009.doi:10.1016/j.tcs.2009.05.029. 10 Therese Biedl, Franz-Josef Brandenburg, and Xiaotie Deng. On the complexity of crossing...

    work page doi:10.1016/j.ic.2009.10.001 2009

  5. [5]

    Random separation: A new method for solving fixed-cardinality optimization problems

    11 Leizhen Cai, Siu Man Chan, and Siu On Chan. Random separation: A new method for solving fixed-cardinality optimization problems. InSecond International Workshop on Parameterized and Exact Computation (IWPEC), volume 4169 ofLecture Notes in Computer Science, pages 239–250. Springer, 2006.doi:10.1007/11847250\_22. 12Diptarka Chakraborty, Debarati Das, an...

    work page doi:10.1007/11847250 2006

  6. [6]

    15 Diptarka Chakraborty, Kshitij Gajjar, and Agastya Vibhuti Jha

    URL: http://papers.nips.cc/paper_files/paper/2022/ hash/974309ef51ebd89034adc64a57e304f2-Abstract-Conference.html. 15 Diptarka Chakraborty, Kshitij Gajjar, and Agastya Vibhuti Jha. Approximating the center ranking under ulam. InFoundations of Software Technology and Theoretical Computer Science, 2021.doi:10.4230/LIPIcs.FSTTCS.2021.12. 16 Ronald Christian,...

    work page doi:10.4230/lipics.fsttcs.2021.12 2022

  7. [7]

    30 ClusteringPermutationsundertheUlamMetric: AParameterizedComplexityStudy 17 Luís Cunha, Ignasi Sau, and Uéverton S

    doi: 10.1007/s10058-007-0028-1. 30 ClusteringPermutationsundertheUlamMetric: AParameterizedComplexityStudy 17 Luís Cunha, Ignasi Sau, and Uéverton S. Souza. On the parameterized complexity of the median and closest problems under some permutation metrics.Algorithms Mol. Biol., 19(1):24, 2024.doi:10.1186/s13015-024-00269-z. 18 Marek Cygan, Fedor V. Fomin, ...

    work page doi:10.1007/s10058-007-0028-1 2024

  8. [8]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    URL: http://dx.doi.org/10.1007/978-3-319-21275-3,doi:10.1007/978-3-319-21275-3. 19 Debarati Das and Amit Kumar. Breaking the two approximation barrier for various consensus clustering problems. InProceedings of the ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 323–372. SIAM, 2025.doi:10.1137/1.9781611978322.10. 20 Persi Diaconis and R. L. Graham...

    work page doi:10.1007/978-3-319-21275-3 2025

  9. [9]

    21 Cynthia Dwork, Ravi Kumar, Moni Naor, and D

    URL:http: //www.jstor.org/stable/2984804. 21 Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. InProceedings of the 10th International Conference on World Wide Web (WWW), pages 613–622. ACM, 2001.doi:10.1145/371920.372165. 22 Ronald Fagin, Ravi Kumar, and D. Sivakumar. Efficient similarity search and classificat...

    work page doi:10.1145/371920.372165 2001

  10. [10]

    URL:https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.ESA.2025.111,doi:10.4230/LIPIcs.ESA.2025.111

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL:https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.ESA.2025.111,doi:10.4230/LIPIcs.ESA.2025.111. 25 FedorVFomin, DanielLokshtanov, SaketSaurabh, andMeiravZehavi.Kernelization: theory of parameterized preprocessing. Cambridge University Press, 2019.doi:10.1017/9781107415157. 26 Jens Gramm, Rol...

    work page doi:10.4230/lipics.esa.2025.111 2025

  11. [11]

    URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.100, doi:10.4230/LIPIcs.ICALP.2025.100

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.100, doi:10.4230/LIPIcs.ICALP.2025.100. 28Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. InProceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 95–103. ACM, 2007.doi:10.1145/12507...

    work page doi:10.4230/lipics.icalp.2025.100 2025

  12. [12]

    T. Bai, F. V. Fomin, P. A. Golovach, Y. H. More, S. Wietheger 31 32 Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems.J. Comput. Syst. Sci., 67(4):757– 771, 2003.doi:10.1016/S0022-0000(03)00078-3. 33 Svatopluk Poljak. A note on stable sets and colorings of graphs...

    work page doi:10.1016/s0022-0000(03)00078-3 2003

  13. [13]

    34 Anke van Zuylen and David P

    URL:http://eudml.org/doc/16622. 34 Anke van Zuylen and David P. Williamson. Deterministic algorithms for rank aggregation and other ranking and clustering problems. InApproximation and Online Algorithms, pages 260–273. Springer, 2007.doi:10.1007/978-3-540-77918-6_21

    work page doi:10.1007/978-3-540-77918-6_21 2007