Ulam Median is NP-hard for Four Permutations

2026/08/06 by Mursalin Habib
Computer Science · #cs.CC

paper · pdf

arxiv created 2026/08/06 · arxiv updated 2026/08/07

Abstract

We show that computing a median under the Ulam distance is NP-hard even when the input consists of exactly four permutations. Previously, NP-hardness was known only for an unbounded number of input permutations (Fischer et al., ESA '25). Our result is tight, since an Ulam median of three permutations can be computed in polynomial time (Chakraborty--Das--Krauthgamer, SODA '21).

Citations

• The Complexity of Kemeny Aggregation with Three Rankings
• Kemeny Rank Aggregation is NP-Hard for Three Voters
• Hardness of Median and Center in the Ulam Metric
• Robust-Sorting and Applications to Ulam-Median
• Fair Rank Aggregation
• Clustering Permutations: New Techniques with Streaming Applications
• Approximating the Median under the Ulam Metric
• A Consistent Extension of Condorcet’s Election Principle
• Algorithms on Strings, Trees and Sequences