HEXAGONbeta

Ulam Metric kk-Center in Parameterized Linear Time

Primarily AI-generated textHuman understanding: some partscs.DS — Data Structures and Algorithmscs.CC — Computational Complexitymath.CO — Combinatorics

Contributed by Matěj Kripner ↗, Václav Rozhoň ↗, Robert Šámal ↗, Martin Šindelář, Adrián Zámečník

Version 1 / Nov 04, 2026 / CC BY 4.0

Abstract

Continuous Ulam Metric kk-Center asks for at most kk permutations whose radius-dd balls cover the input rankings. For mm rankings of nn symbols, a deterministic algorithm takes 2O(kdlog⁡(k+d+2))mn2^{O(kd\log(k+d+2))}mn word operations. Permanent reference rankings, short insertion lists, and small obstructions obtained by patience sorting control the search. For one center, this answers a question of Bai, Fomin, Golovach, More, and Wietheger with linear input dependence. An arbitrary-alphabet Hamming embedding with a nonexpansive retraction also gives the matching 2o(dlog⁡d)2^{o(d\log d)} exclusion under the Exponential Time Hypothesis.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.

Tools used

Bolzano team
Bolzano

References

  1. Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, and Simon Wietheger. Clustering permutations under the Ulam metric: A parameterized complexity study. In Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis, editors, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) , volume 374 of Leibniz International Proceedings in Informatics (LIPIcs) , Article 19, pages 19:1--19:23. Schloss Dagstuhl--Leibniz-Zentrum f ü r Informatik, 2026. https://doi.org/10.4230/LIPIcs.ICALP.2026.19.DOI
  2. Tian Bai, Fedor V. Fomin, Petr A. Golovach, Yash Hiren More, and Simon Wietheger. Clustering permutations under the Ulam metric: A parameterized complexity study. Full version of the ICALP 2026 paper, arXiv:2604.25734v1 [cs.DS] , 2026. https://arxiv.org/abs/2604.25734.arXiv
  3. 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. https://doi.org/10.1016/j.jda.2014.10.002.DOI
  4. Diptarka Chakraborty, Kshitij Gajjar, and Agastya Vibhuti Jha. Approximating the center ranking under Ulam. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) , volume 213 of LIPIcs , Article 12, pages 12:1--12:21, 2021. https://doi.org/10.4230/LIPIcs.FSTTCS.2021.12.DOI
  5. David Aldous and Persi Diaconis. Longest increasing subsequences: From patience sorting to the Baik--Deift--Johansson theorem. Bulletin of the American Mathematical Society , 36(4):413--432, 1999. https://doi.org/10.1090/S0273-0979-99-00796-X.DOI
  6. Nick Fischer and Mursalin Habib. An optimal algorithm for binary closest string. arXiv:2605.31417v1 [cs.DS] , 2026. https://arxiv.org/abs/2605.31417.arXiv
  7. Jens Gramm, Rolf Niedermeier, and Peter Rossmanith. Fixed-parameter algorithms for Closest String and related problems. Algorithmica , 37(1):25--42, 2003. https://doi.org/10.1007/s00453-003-1028-3.DOI
  8. Daniel Lokshtanov, D á niel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. SIAM Journal on Computing , 47(3):675--702, 2018. https://doi.org/10.1137/16M1104834.DOI
  9. Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., and Saeed Seddighin. On complexity of 1-center in various metrics. In APPROX/RANDOM 2023 , volume 275 of LIPIcs , Article 1, 2023. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.1.DOI
  10. Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S. Hardness of median and center in the Ulam metric. In ESA 2025 , volume 351 of LIPIcs , pages 111:1--111:17, 2025. https://doi.org/10.4230/LIPIcs.ESA.2025.111.DOI
Show all 11 referencesShow fewer references
  1. Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong, Debarati Das, Mursalin Habib, and Tien Long Nguyen. Ulam rank aggregation is hard to approximate for four rankings. arXiv:2609.05874v1 [cs.CC] , September 2026. https://arxiv.org/abs/2609.05874v1.arXiv

Version history

  1. v1Submitted by Václav RozhoňInitial depositCurrentNov 03, 2026