Clustering Permutations Under the Ulam Metric: A Parameterized Complexity Study

Bai, Tian; Fomin, Fedor V.; Golovach, Petr A.; More, Yash Hiren; Wietheger, Simon

doi:10.4230/LIPIcs.ICALP.2026.19

Clustering Permutations Under the Ulam Metric:
A Parameterized Complexity Study

Tian Bai

University of Bergen, Norway Fedor V. Fomin

University of Bergen, Norway Petr A. Golovach

University of Bergen, Norway Yash Hiren More

University of Bergen, Norway Simon Wietheger

TU Wien, Austria

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 ${\mathsf{NP}}\subseteq{\mathsf{coNP}}/{\mathsf{poly}}$ . For the Ulam $k$ -median problem parameterized by the total distance $d$ , we establish ${\mathsf{W}}[1]$ -hardness and provide an ${\mathsf{XP}}$ algorithm. We also provide a polynomial kernel for the parameter $k+d$ , which in turn yields a fixed-parameter tractable algorithm.

Keywords and phrases:

parameterized complexity, Ulam distance, rank aggregation, clustering

Category:

Track A: Algorithms, Complexity and Games

Funding:

Tian Bai: Funded 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).

Fedor V. Fomin: ^†^†margin:

Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (NewPC grant agreement No. 101199930).

Petr A. Golovach: Supported by the Research Council of Norway under the BWCA (grant no. 314528) and Extreme-Algorithms (grant no 355137) projects.

Yash Hiren More: Supported by the Trond Mohn forskningsstiftelse (grant no. TMS2023TMT01).

Simon Wietheger: Supported by the Austrian Science Foundation (FWF, project 10.55776/Y1329).

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Parameterized complexity and exact algorithms ; Mathematics of computing

\rightarrow

Permutations and combinations

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

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 those 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, 30, 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, 27, 30, 33]. 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) [27]. 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 [8, 9, 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. [29] 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 the number of input permutations $m$ . 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. [26] improved on this work and provided a randomized algorithm running in $\tilde{O}((2k)^{k}nd)$ time. All three works on the median problem provide guarantees close to but below an approximation factor of $2$ .

To the best of our knowledge, no prior work has considered Ulam-based aggregation through parameterized exact algorithms, despite the metric’s intimate connection to edit distance and longest common subsequence – domains where parameterized techniques have proven highly effective. The clustering problems under the Ulam metric seem more challenging, as the Ulam metric is a more complex and less local measure than Kendall’s tau, which may suggest that the computational landscape of Ulam-based aggregation could be significantly different. One may notice that the Ulam distance is a smaller parameter than Kendall’s tau, as every permutation can be transformed into the other by only moving the elements that are in a different order in the two permutations. It may happen that two permutations with Ulam distance $1$ could differ in the relative order of an unbounded number of pairs of elements. This highlights a fundamental structural disparity between the two distance measures, which leads to the following natural question:

What is the parameterized complexity of rank aggregation under the Ulam metric?

1.1 Clustering Under the Ulam Metric: Definitions and Main Results

In this work, we initiate a systematic study of the parameterized complexity of rank aggregation under the Ulam metric. Beyond the classical parameter $d$ , which captures the solution cost (the maximum distance or the sum of distances, respectively), we consider substantially more general variants of the problem: $k$ -center and $k$ -median clustering under the Ulam metric [13]. These extensions, denoted by Ulam Metric $k$ -Center and Ulam Metric $k$ -Median, are both natural and well established in the rank aggregation literature. In these problems, one seeks $k$ representative permutations that minimize, respectively, the maximum distance to any assigned permutation ( $k$ -center) or the total sum of distances ( $k$ -median).

Formally, let ${{\cal S}}_{n}(\Sigma)$ be the set of all permutations over an alphabet $\Sigma$ of size $n$ , and let $\mathrm{dist}_{U}(\pi,\sigma)$ be the Ulam distance between $\pi$ and $\sigma$ in ${{\cal S}}_{n}(\Sigma)$ (see Section 2 for the formal definitions). We define our problems of interest as follows.

Ulam Metric $k$ -Center

Input: An alphabet $\Sigma$ of size $n$ , a set of permutations $\Pi=\{\pi_{1},\pi_{2},\dots,\pi_{m}\}\subseteq{{\cal S}}_{n}(\Sigma)$ , and integers $k$ and $d$ .

Task: Decide whether there exists a set $S=\{\sigma_{1},\sigma_{2},\ldots,\sigma_{k}\}\subseteq{{\cal S}}_{n}(\Sigma)$ of $k$ centers such that

\max_{\pi\in\Pi}\min_{\sigma\in S}\mathrm{dist}_{U}(\pi,\sigma)\leq d.

Ulam Metric $k$ -Median

Input: An alphabet $\Sigma$ of size $n$ , a multiset of permutations $\Pi=\{\pi_{1},\pi_{2},\dots,\pi_{m}\}\subseteq{{\cal S}}_{n}(\Sigma)$ , and integers $k$ and $d$ .

Task: Decide whether there exists a set $S=\{\sigma_{1},\sigma_{2},\ldots,\sigma_{k}\}\subseteq{{\cal S}}_{n}(\Sigma)$ of $k$ medians such that

\sum_{\pi\in\Pi}\min_{\sigma\in S}\mathrm{dist}_{U}(\pi,\sigma)\leq d.

We remark that, in both clustering problems, the centers or medians are not required to belong to the input set of permutations $\Pi$ . Hence, we consider variants of the problems that are referred to as continuous in some literature. Both problems are known to be ${\mathsf{NP}}$ -hard already for $k=1$ : hardness for the center variant was shown by Bachmaier et al. [5] and for the median by Fischer et al. [24].

We summarize our main results in Table 1. Most notably, we establish fixed-parameter tractability for both problems when parameterized simultaneously by $k$ and $d$ . Prior to our work, the parameterized complexity of these two clustering problems with respect to $d$ was not even settled for the much simpler case $k=1$ .

We contrast this tractability result by establishing hardness for parameterization by $d$ alone: Ulam Metric $k$ -Center is already ${\mathsf{NP}}$ -hard on instances with $d=1$ . In contrast, Ulam Metric $k$ -Median is in ${\mathsf{XP}}$ parameterized by $d$ (that is, solvable in polynomial time for each fixed $d$ ), but is ${\mathsf{W}}[1]$ -hard for parameter $d$ , ruling out fixed-parameter tractability under well-established complexity assumptions. Finally, we discover yet another difference in the tractability landscapes of Ulam Metric $k$ -Center and Ulam Metric $k$ -Median. While the latter admits a polynomial-sized kernel, we rule out the existence of such a kernel for Ulam Metric $k$ -Center under established complexity assumptions. Our results for the Ulam metric complement the mature theory developed for Kendall’s tau. We also hope that they provide rigorous foundations for consensus ranking in applications where global structural coherence under the Ulam metric is essential.

In the following, we provide a detailed overview of our results and the techniques employed. Formal proofs are deferred to Sections 3 and 4. Some details and proofs marked by $(\star)$ are omitted due to space constraints.

Table 1: Summary of our results.

Parameters	$k$ -center	$k$ -median
$k$	${\mathsf{NP}}$ -hard even if $k=1$ [5]	${\mathsf{NP}}$ -hard even if $k=1$ [24]
$d$	${\mathsf{NP}}$ -hard even if $d=1$ (Theorem 1)	${\mathsf{W}}[1]$ -hard, ${\mathsf{XP}}$ (Theorems 5 and 4)
$k+d$	${\mathsf{FPT}}$ (Theorem 2)	${\mathsf{FPT}}$ (Corollary 7)
	no polynomial kernel (Theorem 3)	polynomial kernel (Theorem 6)

1.2 Contributions and Techniques for Ulam Metric $k$ -Center

The first group of results in our work concerns Ulam Metric $k$ -Center. As previous work already established that it is unlikely to obtain polynomial time algorithms even for instances aiming for $k=1$ center, it is natural to ask for the tractability on instances where we instead restrict the radius of the centers to $d=1$ . We answer this question negatively by establishing the ${\mathsf{NP}}$ -hardness of Ulam Metric $k$ -Center for $d$ is any positive constant at least $1$ . This hardness result is established via a reduction from the Vertex Cover problem on triangle-free graphs.

Theorem 1 ( $\star$ ).

Ulam Metric $k$ -Center is ${\mathsf{NP}}$ -hard even if $d$ is fixed to any positive constant at least $1$ .

The construction for $d=1$ is relatively straightforward but closes an important gap: it establishes that parameterization by $d$ alone cannot yield fixed-parameter tractability under standard complexity assumptions. The main idea of the reduction is to construct an alphabet consisting of two symbols $v,\bar{v}$ per vertex $v$ in the vertex cover instance. The input set $\Pi$ contains one permutation per edge, all sharing a common base ordering except that the symbol pairs of the two endpoints of the edge are swapped in the respective permutation. A vertex cover then corresponds to a set of center permutations, each encoding a vertex by swapping the respective symbol pair in the base ordering. Then each permutation encoding an edge has Ulam distance $1$ to only those permutations encoding vertices to which the edge is incident, which ensures an equivalence between the vertex cover instance and the Ulam Metric $k$ -Center instance. We defer a formal proof to Section 3, but provide an exemplary reduction in Figure 1.

	$\displaystyle\Sigma$	$\displaystyle{}=\{v,\bar{v},w,\bar{w},x,\bar{x},y,\bar{y},z,\bar{z}\}$
	$\displaystyle\Pi$	$\displaystyle{}=\{\pi_{vw},\pi_{wx},\pi_{wy},\pi_{xz}\}$
	$\displaystyle S$	$\displaystyle{}=\{\sigma_{w},\sigma_{x}\}$

	$\displaystyle\pi_{vw}$	$\displaystyle{}=\hbox{\pagecolor{black!40}$\displaystyle\bar{v}\ v$}\ \hbox{% \pagecolor{black!40}$\displaystyle\bar{w}\ w$}\ \hbox{\pagecolor{black!20}$% \displaystyle x\ \bar{x}$}\ \hbox{\pagecolor{black!20}$\displaystyle y\ \bar{y% }$}\ \hbox{\pagecolor{black!20}$\displaystyle z\ \bar{z}$}$
	$\displaystyle\pi_{wx}$	$\displaystyle{}=\hbox{\pagecolor{black!20}$\displaystyle v\ \bar{v}$}\ \hbox{% \pagecolor{black!40}$\displaystyle\bar{w}\ w$}\ \hbox{\pagecolor{black!40}$% \displaystyle\bar{x}\ x$}\ \hbox{\pagecolor{black!20}$\displaystyle y\ \bar{y}% $}\ \hbox{\pagecolor{black!20}$\displaystyle z\ \bar{z}$}$
	$\displaystyle\pi_{wy}$	$\displaystyle{}=\hbox{\pagecolor{black!20}$\displaystyle v\ \bar{v}$}\ \hbox{% \pagecolor{black!40}$\displaystyle\bar{w}\ w$}\ \hbox{\pagecolor{black!20}$% \displaystyle x\ \bar{x}$}\ \hbox{\pagecolor{black!40}$\displaystyle\bar{y}\ y% $}\ \hbox{\pagecolor{black!20}$\displaystyle z\ \bar{z}$}$
	$\displaystyle\pi_{xz}$	$\displaystyle{}=\hbox{\pagecolor{black!20}$\displaystyle v\ \bar{v}$}\ \hbox{% \pagecolor{black!20}$\displaystyle w\ \bar{w}$}\ \hbox{\pagecolor{black!40}$% \displaystyle\bar{x}\ x$}\ \hbox{\pagecolor{black!20}$\displaystyle y\ \bar{y}% $}\ \hbox{\pagecolor{black!40}$\displaystyle\bar{z}\ z$}$
	$\displaystyle\sigma_{w}$	$\displaystyle{}=\hbox{\pagecolor{black!20}$\displaystyle v\ \bar{v}$}\ \hbox{% \pagecolor{black!40}$\displaystyle\bar{w}\ w$}\ \hbox{\pagecolor{black!20}$% \displaystyle x\ \bar{x}$}\ \hbox{\pagecolor{black!20}$\displaystyle y\ \bar{y% }$}\ \hbox{\pagecolor{black!20}$\displaystyle z\ \bar{z}$}$
	$\displaystyle\sigma_{x}$	$\displaystyle{}=\hbox{\pagecolor{black!20}$\displaystyle v\ \bar{v}$}\ \hbox{% \pagecolor{black!20}$\displaystyle w\ \bar{w}$}\ \hbox{\pagecolor{black!40}$% \displaystyle\bar{x}\ x$}\ \hbox{\pagecolor{black!20}$\displaystyle y\ \bar{y}% $}\ \hbox{\pagecolor{black!20}$\displaystyle z\ \bar{z}$}$

Figure 1: Exemplary vertex cover instance with solution

\{w,x\}

(black vertices) and the constructed instance of Ulam Metric

k

-Center with solution

S=\{\sigma_{w},\sigma_{x}\}

.

A nontrivial challenge is that a single permutation – swapping symbol pairs of multiple vertices – might cover several edges without corresponding to any single vertex in a cover. We circumvent this problem by basing our reduction on triangle-free instances of Vertex Cover, so this case will never occur. Furthermore, a direct reduction from the $d=1$ case to general $d$ is non-trivial; we overcome this by augmenting the $d=1$ construction with additional corresponding symbols for each vertex.

The ${\mathsf{NP}}$ -hardness of Ulam Metric $k$ -Center even if $d=1$ or if $k=1$ naturally raises the question of the parameterized complexity of the problem with the combined parameter $k+d$ . The following theorem establishes fixed-parameter tractability with respect to this combined parameter.

Theorem 2.

Ulam Metric $k$ -Center can be solved in $2^{{{\cal O}}(d^{2}k(d+k))}\cdot mn^{1+o(1)}$ time, where $m\coloneqq|\Pi|$ and $n\coloneqq|\Sigma|$ .

On first glance, it may seem that the finite number of permutations in our space would allow for an approach based on some simple branching and local search around some permutation $\pi\in\Pi$ . This approach is infeasible, however, as for a permutation $\pi$ of length $n\gg d$ , there are $n^{\Omega(d)}$ permutations within Ulam distance $d$ from $\pi$ , each of which is a potential candidate for the center. This lower bound follows from a simple counting argument. One can choose $d$ symbols from the first half of $\pi$ in $\binom{n/2}{d}$ ways and insert them into the second half in at least $(n/2)^{d}$ distinct ways, yielding a unique permutation at Ulam distance at most $d$ from $\pi$ .

A natural alternative is to adapt techniques from string-based clustering, which typically perform bounded local search around a candidate solution and iteratively improve it by resolving “dissimilarities” with inputs that exceed the target distance $d$ . Such a paradigm is well-known and has been highly successful for problems such as Closest String [25] where the “dissimilarities” correspond to bits contributing to the Hamming distance. However, two permutations can admit $\Omega((n/d)^{d})$ distinct $\mathrm{LCS}$ s of the same maximum length, making it impossible to pinpoint a canonical set of elements to guide local improvements. Thus, such techniques from string-based clustering cannot directly apply to the Ulam metric, and more involved methods are required. Our algorithm embarks on a similar approach as the one by Gramm et al. [25]. Rather sooner than later, however, the issue of not having a unique witness $\mathrm{LCS}$ requires much more involved techniques and branching procedures tailored to the Ulam metric to establish fixed-parameter tractability.

In our algorithm, we construct a family of candidate permutations that are at bounded Ulam distances from hypothetical centers. These permutations will eventually converge towards the center permutations. If $k=1$ , then such a candidate can be initially chosen as an arbitrary permutation from $\Pi$ ; note that it should be at the Ulam distance at most $d$ from a center in any YES-instance of the problem. For $k\geq 2$ , we initiate the set of candidates using the idea behind the standard $2$ -approximation for the $k$ -Center problem. On each step, we either conclude that the current set of candidates can serve as centers, that is, each permutation in $\Pi$ is at distance at most $d$ from one of the candidates, or find a guide permutation $\pi_{g}$ at distance at least $d+1$ from all the candidates. Then we can guess a candidate permutation $\pi_{c}$ that should be transformed to a center for the cluster containing the guide. Our crucial result (Lemma 16) shows that, given $\pi_{c}$ and $\pi_{g}$ , we can efficiently (in FPT time) enumerate a set of permutations with distance one to $\pi_{c}$ such that for any hypothetical center, there is a permutation in the set that is closer to the center than $\pi_{c}$ was, see Figure 2 for a visualization of this idea. The proof of Lemma 16 is rather sophisticated and combines the random separation [11] and branching techniques. The random separation is used to highlight elements of $\pi_{c}$ and $\pi_{g}$ that should be moved to make these permutations closer to the center and the neighbors of these elements that are not moved. Then we identify an element of $\pi_{c}$ that should be moved and, after that, find an appropriate place for this element using branching. Repeatedly invoking Lemma 16, we ensure that the candidate permutations converge to the centers.

Figure 2: Illustration of the key idea behind our FPT algorithm for the

k

-center problem under Ulam distance.

\pi_{c}

denotes a candidate center,

\pi_{g}

a guide permutation with distance between

d

and

2d

from

\pi_{c}

, and

\sigma

represents the true (optimal) center that covers both

\pi_{c}

and

\pi_{g}

. We enumerate in FPT time a set of permutations (shown as

\{p_{1},p_{2},p_{3},p_{4}\}

) at distance

1

from

\pi_{c}

. Among these candidates, at least one candidate (shown as

p_{3}

) reduces the Ulam distance to

\sigma

and thus corresponds to a correct branch.

The fixed-parameter tractability of Ulam Metric $k$ -Center with parameter $k+d$ established in Theorem 2 immediately leads to the question about the existence of a polynomial kernel for this problem. The following theorem provides a negative answer to this question.

Theorem 3 ( $\star$ ).

Ulam Metric $k$ -Center does not admit a polynomial-sized kernel for the parameter $k+d$ unless $\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$ .

The lower bound of Theorem 3 holds already for $k=1$ . The proof is based on a Polynomial Parameterized Transformation (PPT) reduction from the classical Closest String problem to Ulam Metric $k$ -Center. To build such a transformation, we employ a distance-preserving transformation between binary strings and permutations, where for every pair of binary strings, their Hamming distance is the same as the Ulam distance between the permutations to which they translate. The reduction establishes that from the perspective of parameterized complexity with respect to the radius $d$ , Ulam Metric $k$ -Center is at least as hard as Closest String. Theorem 3 then follows by pipelining the PPT with established lower bounds on the kernelization of Closest String by Basavaraju et al. [6].

1.3 Contributions and Techniques for Ulam Metric $k$ -Median

The second group of results is concerned with Ulam Metric $k$ -Median. Recall that the problem is ${\mathsf{NP}}$ -hard for $k=1$ [5]. While Ulam Metric $k$ -Center is also ${\mathsf{NP}}$ -hard for $d=1$ , this is not the case for Ulam Metric $k$ -Median. It is easy to obtain a polynomial-time algorithm for this problem for each fixed value of $d$ .

Theorem 4 ( $\star$ ).

Ulam Metric $k$ -Median can be solved in ${{\cal O}}((mn)^{2d})$ time, where $m\coloneqq|\Pi|$ and $n\coloneqq|\Sigma|$ .

The algorithm builds on a simple branching technique, where we observe that the medians can be obtained by applying a total of $d$ move-operations on the input set, and we branch on these $d$ moves by brute-force. The result in Theorem 4 is tight in the sense that the existence of an $\mathsf{FPT}$ -algorithm for the parameterization by $d$ is unlikely due to the following lower bound.

Theorem 5.

Ulam Metric $k$ -Median is ${\mathsf{W}}[1]$ -hard parameterized by $d$ .

Our proof of Theorem 5 relies on a careful reduction from Multicolored Clique. The instance is designed in a way that all but one of the medians in any hypothetical solution are already present in the input set $\Pi$ . The challenge is to find that additional median in a way that it is sufficiently close to a number of input permutations. Crucially, the permutations are designed in such a way that this is only possible if all edges covered by the median form a clique, see Figure 3 for a schematic example. On a high level, we construct the instance such that there is one special symbol per color, and the position of that symbol in the additional median encodes which vertex of that color is selected for the multi-colored clique.

Figure 3: Illustration of the reduction from Multicolored Clique to Ulam Metric

k

-Median. Left shows an instance of Multicolored Clique with four color classes (

\{w\},\{x\},\{y,y^{\prime}\},

and

\{z,z^{\prime}\}

) and a colorful clique

Q=\{w,x,y,z\}

. Right shows the schematic solution to the constructed Ulam Metric

k

-Median instance. Each edge is encoded as an input permutation; edges whose endpoints form a multicolored clique are covered by a single external median

\sigma_{Q}

(underlined), while all other edges each serve as their own median in singleton clusters (also underlined).

Interestingly, our proof indicates that the hardness of the problem does not so much depend on identifying which symbols need to be moved but also importantly on deciding where to move these symbols.

In contrast to the lower bound on the polynomial kernel for Ulam Metric $k$ -Center obtained in Theorem 3, Ulam Metric $k$ -Median admits a polynomial kernel.

Theorem 6 ( $\star$ ).

Ulam Metric $k$ -Median admits a kernel with ${{\cal O}}(d^{2}+dk)$ permutations over an alphabet of size ${{\cal O}}(d^{4}+d^{2}k^{2})$ , computable in ${{\cal O}}(m^{2}n\log n)$ time, where $m\coloneqq|\Pi|$ and $n\coloneqq|\Sigma|$ .

Our kernelization result is based on the observation that for any YES-instance of Ulam Metric $k$ -Median, $\Pi$ contains at most $k+d$ distinct permutations. This allows us to reduce the size of $\Pi$ . Then we reduce the size of the alphabet $\Sigma$ by making replacements of identical subpermutations by shorter ones. Here, we use the fact that two permutations at Ulam distance at least $d+1$ cannot belong to the same median in any solution. Thus, we can identify some sets of permutations such that every set of permutations that shares a median in a hypothetical solution is a subset to one of the sets. We show that the pairwise Ulam distance within each set are small. Combined with the fact that there are only few distinct permutations, this implies that in each set there are many (or long) identical subpermutations, which we can then shorten to reduce the size of the alphabet $\Sigma$ .

Combining Theorems 6 and 4, we immediately obtain an $\mathsf{FPT}$ -algorithm with the following running time.

Corollary 7.

Ulam Metric $k$ -Median can be solved in $(kd)^{{{\cal O}}(d)}+{{\cal O}}(m^{2}n\log n)$ time, where $m\coloneqq|\Pi|$ and $n\coloneqq|\Sigma|$ .

2 Preliminaries

Basic notation.

We use $[n]$ to denote the set $\{1,2,\ldots,n\}$ . Let $\Sigma$ be a finite alphabet with $|\Sigma|=n$ . A permutation of length $n$ over $\Sigma$ is a bijection $\pi\coloneq[n]\to\Sigma$ . We write ${{\cal S}}_{n}(\Sigma)$ for the set of all permutations of length $n$ over $\Sigma$ . Thus, each $\pi\in{{\cal S}}_{n}(\Sigma)$ is an ordering of the symbols of $\Sigma$ . We often write a permutation as a sequence $\pi=\pi(1)\pi(2)\cdots\pi(n)$ .

A subsequence of a permutation $\pi$ is obtained by deleting zero or more elements from $\pi$ while maintaining the relative order of the remaining elements. A common subsequence of two permutations $\pi_{1}$ and $\pi_{2}$ is a subsequence that appears in both permutations. We denote by $\mathrm{LCS}(\pi_{1},\pi_{2})$ the length of the longest common subsequence of $\pi_{1}$ and $\pi_{2}$ .

Ulam distance.

A move operation on a permutation $\pi$ removes one element from its current position and inserts it at another position, while maintaining the relative order of all other elements.

For two permutations $\pi,\sigma\in{{\cal S}}_{n}(\Sigma)$ , the Ulam distance $\mathrm{dist}_{U}(\pi,\sigma)$ is the minimum number of move operations needed to transform $\pi$ into $\sigma$ :

\mathrm{dist}_{U}(\pi,\sigma)=\min\{\,d:\text{$\pi$ can be turned into $\sigma% $ using $d$ moves}\,\}.

A classical identity characterizes this metric in terms of the longest common subsequence:

\mathrm{dist}_{U}(\pi,\sigma)=n-\mathrm{LCS}(\pi,\sigma).

Thus, the Ulam distance measures the minimum number of elements that must be relocated to make the permutations consistent in relative order. We remark that a longest common subsequence, and thereby the Ulam distance, between two permutations of length $n$ can be computed in time in $O(n\log n)$ by relabeling the alphabet such that the first permutation has increasing order and then finding a longest increasing sequence in the other (relabeled) permutation. The Ulam distance on permutations is analogous to the Levenshtein edit distance on strings in the following sense: both distances identify a longest common subsequence and keep it untouched while performing edit operations on the remaining symbols.

For a set ${{\cal S}}\subseteq{{\cal S}}_{n}(\Sigma)$ of permutations and $\pi\in{{\cal S}}_{n}(\Sigma)$ , we write $\mathrm{dist}_{U}(\pi,{{\cal S}})$ to denote the minimum distance from $\pi$ to any permutation in ${{\cal S}}$ , that is, $\mathrm{dist}_{U}(\pi,{{\cal S}})=\min_{\sigma\in{{\cal S}}}\mathrm{dist}_{U}(% \pi,\sigma)$ .

For two strings $s, t$ of equal length over an alphabet, the Hamming distance $\mathrm{dist}_{H}(s,t)$ counts the number of positions where the corresponding symbols differ.

Graphs.

We work with simple undirected graphs. For a graph $G$ , we denote by $V(G)$ its vertex set and by $E(G)$ its edge set. A vertex cover of a graph $G$ is a subset $X\subseteq V(G)$ such that every edge in $E(G)$ has at least one endpoint in $X$ . A clique in a graph $G$ is a subset of vertices such that every pair of vertices in the subset is connected by an edge. A graph is triangle-free if it contains no clique of size $3$ . A proper vertex coloring of a graph $G$ assigns colors to vertices such that no two adjacent vertices share the same color.

Parameterized Complexity.

A parameterized problem is a language $L\subseteq\Sigma^{*}\times\mathbb{N}$ where $\Sigma^{*}$ is a set of strings over a finite alphabet $\Sigma$ . An input of a parameterized problem is a pair $(x,k)$ where $x$ is a string over $\Sigma$ and $k\in\mathbb{N}$ is a parameter. A parameterized problem is fixed-parameter tractable (or $\mathsf{FPT}$ ) if it can be solved in $f(k)\cdot|x|^{\mathcal{O}(1)}$ time for some computable function $f$ . The complexity class $\mathsf{FPT}$ consists of all fixed-parameter tractable parameterized problems. A parameterized problem is in the class $\mathsf{XP}$ if it can be solved in $|x|^{f(k)}$ time for a computable function $f(\cdot)$ . The standard way to rule out the existence of an $\mathsf{FPT}$ -algorithm for a parameterized problem under the standard parameterized complexity assumption that ${\mathsf{FPT}}\neq{\mathsf{W}}[1]$ is to show that it is $\mathsf{W}$ [1]-hard, that is, at least as hard as any problem in the class of parameterized problems ${\mathsf{W}}[1]$ . A problem is para- ${\mathsf{NP}}$ -hard if it is ${\mathsf{NP}}$ -hard even when the parameter $k$ is a constant.

A kernelization algorithm or kernel for a parameterized problem $L$ is a polynomial-time algorithm that takes as its input an instance $(x,k)$ of $L$ and returns an instance $(x^{\prime},k^{\prime})$ of the same problem such that (i) $(x,k)\in L$ if and only if $(x^{\prime},k^{\prime})\in L$ and (ii) $|x^{\prime}|+k^{\prime}\leq f(k)$ for some computable function $f\colon\mathbb{N}\rightarrow\mathbb{N}$ . The function $f(\cdot)$ is the size of the kernel; a kernel is polynomial if $f$ is a polynomial. A decidable parameterized problem is $\mathsf{FPT}$ if and only if it admits a kernel. However, up to some standard complexity-theoretic assumptions, there are $\mathsf{FPT}$ problems that have no polynomial kernels. One of the ways to exclude a polynomial kernel for a parameterized problem is to show that there is a polynomial parameter transformation from a parameterized problem for which the existence of a polynomial kernel does not exist unless $\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$ , where a polynomial parameter transformation is a polynomial-time reduction such that the parameter in the new instance is bounded by a polynomial in the original parameter.

3 The Complexity of Ulam Metric $k$ -Center

In this section, we study the Ulam Metric $k$ -Center problem. We first show that the problem is already ${\mathsf{NP}}$ -hard for $d=1$ . Our main result in this section is the fixed-parameter tractability of the problem parameterized by $k+d$ . Nevertheless, under standard complexity assumptions, the problem does not admit a polynomial kernel parameterized by $k+d$ .

3.1 Lower Bound for Constant Radius $𝒅$

We prove that Ulam Metric $k$ -Center is ${\mathsf{NP}}$ -hard when the radius is fixed to the constant $d$ , via a reduction from Vertex Cover. Notice that Vertex Cover remains ${\mathsf{NP}}$ -hard in triangle-free graphs [32]. This follows from a standard $2$ -subdivision transformation: replacing each edge by a path of length $3$ eliminates all triangles and increases the size of a minimum vertex cover by exactly one per original edge. We may thus assume without loss of generality that the input graph is triangle-free, which suffices to prove Theorem 1. The idea of the reduction is to have two symbols per vertex. All permutations relevant to the reduction look almost entirely the same, except that only the pair of symbols for one or two vertices are swapped to encode that respective vertex or edge. If we let the input set of permutations encode all edges of the graph this way, then a vertex cover corresponds to a set of permutations encoding vertices. This holds as each permutation encoding an edge has Ulam distance $1$ to only those permutations encoding vertices to which the edge is incident.

Theorem 1 ( $\star$ ). [Restated, see original statement.]

Ulam Metric $k$ -Center is ${\mathsf{NP}}$ -hard even if $d$ is fixed to any positive constant at least $1$ .

3.2 Fixed-Parameter Tractability by $k+d$

Since the problem is ${\mathsf{NP}}$ -hard even for constant $d$ or $k$ , neither parameter yields tractability on its own. We therefore consider the combined parameter $k+d$ , and show that the Ulam center problem is fixed-parameter tractable under this parameterization.

Our algorithm relies on iteratively updating candidate permutations to eventually converge towards the center permutations by moving one symbol in a candidate in each step. Specifically, given a candidate permutation $\pi_{c}$ and a guide permutation $\pi_{g}$ , we can enumerate (in ${\mathsf{FPT}}$ time) a set $P$ of permutations that differ from $\pi_{c}$ by one move. Among them, at least one gets closer to any true center that covers both $\pi_{c}$ and $\pi_{g}$ . The key technical ingredient is captured in Lemma 16.

Our approach is based on the $2$ -colorings of the symbols in $\pi_{g}$ and $\pi_{c}$ . The $2$ -colorings encode which symbols are allowed to be moved toward a specific permutation $\sigma\in P$ . We formalize when such a $2$ -coloring is fitting with respect to $\sigma$ , an exemplary coloring is visualized in Figure 4.

Figure 4: A permutation

\pi

with a $d$ -fitting coloring with respect to a permutation

\sigma

, with witness

\Sigma_{\pi}=\{1,2,3,4,5\}

. Substrings highlighted in red form blocks. The rightmost block contains more than

d

red symbols, meaning that it cannot contain any moved symbol.

Definition 8 ( $d$ -fitting coloring and witness).

Let $d\in{\mathbb{N}}$ , $\pi\in{{\cal S}}_{n}(\Sigma)$ , and $\operatorname{\mathrm{col}}\colon\Sigma\to\{\operatorname{\texttt{red}},% \operatorname{\texttt{blue}}\}$ be a coloring function of $\pi$ . We say $\operatorname{\mathrm{col}}$ is a $d$ -fitting coloring (of $\pi$ ) with respect to some permutation $\sigma\in{{\cal S}}_{n}(\Sigma)$ , if there is a subset of symbols $\Sigma_{\pi}\subseteq\Sigma$ such that

$\blacksquare$

$|\Sigma_{\pi}|=\mathrm{dist}_{U}(\pi,\sigma)$ and $\sigma$ can be obtained from $\pi$ by moving the symbols in $\Sigma_{\pi}$ ;
$\blacksquare$

for every symbol in $x\in\Sigma_{\pi}$ , we have $\operatorname{\mathrm{col}}(x)=\operatorname{\texttt{red}}$ ; and
$\blacksquare$

for every symbol $x\in\Sigma\setminus\Sigma_{\pi}$ , if $x$ appears in $\pi$ within $3d$ symbols (before or after) of some symbol in $\Sigma_{\pi}$ , then $\operatorname{\mathrm{col}}(x)=\operatorname{\texttt{blue}}$ .

Moreover, such a subset of symbols $\Sigma_{\pi}$ is called a witness of the coloring $\operatorname{\mathrm{col}}$ to be $d$ -fitting.

Intuitively, red symbols are candidates for being moved (i.e., they may or may not actually be moved), but blue symbols are definitely not moved. Moreover, if a red symbol is indeed one of the moved symbols (i.e., it belongs to $\Sigma_{\pi}$ ), then all symbols within distance $3d$ of it must be correctly colored blue (if they are not moved) or red (if they are moved). In other words, whenever the coloring correctly identifies a moved symbol as red, it must also correctly color its entire $3d$ -neighborhood.

Consequently, the red symbols in a $d$ -fitting coloring $\operatorname{\mathrm{col}}$ of $\pi$ w.r.t. $\sigma$ that are not separated by $3d$ consecutive blue symbols are tied to each other in the sense that either both or none of them belong to any witness $\Sigma_{\pi}$ . This motivates the following definitions of blocks.

Definition 9 (Blocks).

Let $d\in{\mathbb{N}}$ , $\pi\in{{\cal S}}_{n}(\Sigma)$ and $\operatorname{\mathrm{col}}\colon\Sigma\to\{\operatorname{\texttt{red}},% \operatorname{\texttt{blue}}\}$ . A block is a maximal substring (i.e., consecutive sequence) $\beta$ of $\pi$ such that

$\blacksquare$

the first and last symbols of $\beta$ are colored red; and
$\blacksquare$

$\beta$ contains no $3d$ consecutive blue symbols.

See also Figure 4 for a visualization of blocks. By definition, any two blocks are disjoint and separated by at least $3d$ blue vertices in $\pi$ . We immediately obtain the following observation by recoloring all symbols in a block blue if it contains more than $d$ red symbols.

Observation 10.

Let $d\in{\mathbb{N}}$ , $\pi\in{{\cal S}}_{n}(\Sigma)$ . Suppose $\operatorname{\mathrm{col}}$ is a $d$ -fitting coloring of $\pi$ w.r.t. some permutation $\sigma\in{{\cal S}}_{n}(\Sigma)$ . If $\mathrm{dist}_{U}(\pi,\sigma)\leq d$ , there is a $d$ -fitting coloring $\operatorname{\mathrm{col}}^{\prime}$ of $\pi$ w.r.t. $\sigma$ such that there are at most $d$ red symbols in each block. Moreover, such a coloring $\operatorname{\mathrm{col}}^{\prime}$ can be obtained from $\operatorname{\mathrm{col}}$ in ${{\cal O}}(n)$ time.

We next argue how the notion of $d$ -fitting colorings and that of witnesses provide a means to find a permutation that is one step closer to any true center $\sigma$ than the candidate $\pi_{c}$ .

Lemma 11.

Let $d\in{\mathbb{N}}$ , $\pi_{c},\pi_{g}\in{{\cal S}}_{n}(\Sigma)$ . Let $\operatorname{\mathrm{col}}_{c}$ and $\operatorname{\mathrm{col}}_{g}$ be $d$ -fitting colorings of $\pi_{c}$ and $\pi_{g}$ w.r.t. some permutation $\sigma\in{{\cal S}}_{n}(\Sigma)$ with $1\leq\mathrm{dist}_{U}(\pi_{c},\sigma)\leq d$ and $\mathrm{dist}_{U}(\pi_{g},\sigma)\leq d$ . Consider any symbol $x\in\Sigma$ such that there are witnesses $\Sigma_{c}$ and $\Sigma_{g}$ of $\operatorname{\mathrm{col}}_{c}$ and $\operatorname{\mathrm{col}}_{g}$ , respectively, with $x\in\Sigma_{c}\setminus\Sigma_{g}$ . Then in time ${{\cal O}}(dn)$ we can compute and enumerate a set $P$ with $|P|\leq 6d+2$ and there is $\tilde{\pi}\in P$ with $\mathrm{dist}_{U}(\tilde{\pi},\sigma)=\mathrm{dist}_{U}(\pi_{c},\sigma)-1$ . The computation does not require the sets $\Sigma_{c}$ and $\Sigma_{g}$ as input.

Proof.

Consider an arbitrary pair $\Sigma_{c}$ and $\Sigma_{g}$ of witnesses. Intuitively, $x\in\Sigma_{c}$ means that by moving $x$ to a specific new location in $\pi_{c}$ , we make $\pi_{c}$ closer to $\sigma$ . As $x\notin\Sigma_{g}$ , the position of $x$ in $\pi_{g}$ gives an indication for that location.

To see where to move $x$ in $\pi_{c}$ , let $b_{l}$ be the closest symbol to the left of $x$ in $\pi_{g}$ that is still blue in both permutations, and let $b_{r}$ be the closest such symbol to the right of $x$ in $\pi_{g}$ . If there is no such symbol on the right and/or left, consider $b_{l}$ or $b_{r}$ to be a phantom blue symbol before/after the first/last symbol of the permutation, respectively. As $\Sigma_{g}$ does not contain any blue symbols, it does not contain any of $x,b_{l},$ and $b_{r}$ . Thus, as $x$ lies between $b_{l}$ and $b_{r}$ in $\pi_{g}$ , it lies between them in $\sigma$ as well. As $b_{l}$ and $b_{r}$ are blue in $\operatorname{\mathrm{col}}_{c}$ as well, they do not change their position between $\pi_{c}$ and $\sigma$ . We add all permutations to $P$ that are obtained by moving $x$ in $\pi_{c}$ to some location between $b_{l}$ and $b_{r}$ . This ensures that we consider all possible ways of moving $x$ closer to its position in $\sigma$ , leading to the fact that $P$ always contains a permutation $\tilde{\pi}$ that is one step closer to $\sigma$ than $\pi_{c}$ .

We argue that we only need to add at most $6d+2$ such permutations to $P$ . Consider the next $2d+1$ symbols to the left of $x$ in $\pi_{g}$ . Note that they belong to at most one block in $\pi_{g}$ . In each block, there are at most $d$ red symbols, and at least $d+1$ of these symbols are blue in $\operatorname{\mathrm{col}}_{g}$ . Thereby, these symbols do not appear in any witness $\Sigma_{g}$ of $\operatorname{\mathrm{col}}_{g}$ . Let $L$ be the set of these blue symbols (select the closest $d+1$ to $x$ , if there are more than $d+1$ ). As $\mathrm{dist}_{U}(\pi_{g},\sigma)\leq d$ , the symbols in $L$ appear as a subsequence of $\sigma$ which is interrupted only by at most $d$ other symbols. Call the set of these interrupting symbols $I$ . As the symbols in $L\cup I$ occur consecutively in $\sigma$ , the symbols in $(L\cup I)\setminus\Sigma_{c}$ appear consecutively in $\pi_{c}$ , except some potential interruptions by symbols in $\Sigma_{c}$ . Thus, the symbols in $L\setminus\Sigma_{c}$ have a pairwise maximal distance of at most $|L|+|I|+|\Sigma_{c}|-1\leq 3d$ in $\pi_{c}$ . Thus, they belong to at most one block in $\pi_{c}$ and so at most $d$ of them are red in $\operatorname{\mathrm{col}}_{c}$ . Hence, there is a symbol $b_{l}\in L$ which is blue in both $\operatorname{\mathrm{col}}_{g}$ and $\operatorname{\mathrm{col}}_{r}$ . The same line of argument shows that a suitable symbol $b_{r}$ exists among the $2d+1$ symbols to the right of $x$ in $\pi_{g}$ .

As the distance between $b_{l}$ and $b_{r}$ is at most $4d+2$ in $\pi_{g}$ and $\mathrm{dist}_{U}(\pi_{c},\pi_{g})\leq 2d$ , the distance between $b_{l}$ and $b_{r}$ in $\pi_{c}$ is at most $6d+2$ , giving that many possibilities on where to insert $x$ . If one or both of $b_{l}$ and $b_{r}$ are phantom symbols at the beginning/end of a permutation, the same upper bound applies.

We can find $b_{\ell}$ and $b_{r}$ in time $O(d)$ by starting a search outwards from $x$ in $\pi_{c}$ . Listing all obtained permutations takes time in ${{\cal O}}(dn)$ . $\hfill\blacktriangleleft$

It remains to show how to find such a symbol $x$ . For technical reasons, we require a weak notion of consistency between two $d$ -fitting colorings, which motivates the following definition.

Definition 12 (Consistent $d$ -fitting colorings).

Let $d\in{\mathbb{N}}$ , $\pi_{c},\pi_{g}\in{{\cal S}}_{n}(\Sigma)$ , and $\operatorname{\mathrm{col}}_{c},\operatorname{\mathrm{col}}_{g}$ be $d$ -fitting colorings of $\pi_{c}$ and $\pi_{g}$ with respect to some permutation $\sigma\in{{\cal S}}_{n}(\Sigma)$ , respectively. We say that $\operatorname{\mathrm{col}}_{c}$ and $\operatorname{\mathrm{col}}_{g}$ are consistent $d$ -fitting with respect to $\sigma$ if there are respective witnesses $\Sigma_{c},\Sigma_{g}\subseteq\Sigma$ , such that for every symbol $x\in\Sigma_{c}\cup\Sigma_{g}$ , we have $\operatorname{\mathrm{col}}_{g}(x)=\operatorname{\texttt{red}}$ if and only if $x\in\Sigma_{g}$ , and $\operatorname{\mathrm{col}}_{c}(x)=\operatorname{\texttt{red}}$ if and only if $x\in\Sigma_{c}$ .

We first show how to enumerate a set of candidate pairs of colorings to be consistent $d$ -fitting with respect to any $\sigma$ .

Lemma 13.

Let $d\in{\mathbb{N}}$ and $\pi_{c},\pi_{g}\in{{\cal S}}_{n}(\Sigma)$ . There is a set ${\cal C}$ of $2$ -coloring pairs such that

$\blacksquare$

the size of ${\cal C}$ is bounded by $|{\cal C}|\leq 2^{{{\cal O}}(d^{2})}\log n$ ; and
$\blacksquare$

for every $\sigma\in{{\cal S}}_{n}(\Sigma)$ with $\mathrm{dist}_{U}(\pi_{c},\sigma)\leq d$ and $\mathrm{dist}_{U}(\pi_{g},\sigma)\leq d$ , ${\cal C}$ contains a consistent $d$ -fitting coloring pair of $\pi_{c}$ and $\pi_{g}$ w.r.t. $\sigma$ .

Moreover, such a set can be computed and listed in $2^{{{\cal O}}(d^{2})}n\log n$ time, where $n\coloneqq|\Sigma|$ .

Proof.

We construct the collection ${\cal C}$ using the notion of $(a,b)$ -universality. An $(a,b)$ -universal set ${{\cal U}}\subseteq\{0,1\}^{a}$ is a set of bitstrings of length $a$ , such that for each subset ${{\cal S}}\subseteq[a]$ of size $b$ , the projection of ${{\cal U}}$ onto the coordinates in ${{\cal S}}$ yields all $2^{b}$ possible bitstrings of length $b$ . Equivalently, if we restrict each string in ${{\cal U}}$ to any fixed set of $b$ coordinates, all possible $2^{b}$ binary patterns appear. Naor, Schulman, and Srinivasan [28] showed that such a set exists with size at most $2^{b}b^{{{\cal O}}(\log b)}\log a$ , and can be listed in time $2^{b}b^{{{\cal O}}(\log b)}a\log a$ .

In our setting, we take $a=2n$ and $b=12d^{2}+4d$ . Applying the above, we obtain an $(a,b)$ -universal set ${\cal C}\subseteq\{0,1\}^{a}$ of size

2^{b}b^{{{\cal O}}(\log b)}\log(a)=2^{{{\cal O}}(d^{2}+\log^{2}d)}\log n=2^{{{% \cal O}}(d^{2})}\log n,

which can be listed it in time $2^{{{\cal O}}(d^{2})}n\log n$ . Each bitstring in $\{0,1\}^{2n}$ naturally defines a pair of $2$ -colorings of the symbols in $\Sigma$ : the first $n$ bits define the coloring $\operatorname{\mathrm{col}}_{c}$ of $\pi_{c}$ and the last $n$ bits define a coloring $\operatorname{\mathrm{col}}_{g}$ of $\pi_{g}$ .

Now, consider any permutation $\sigma$ with $\mathrm{dist}_{U}(\pi_{c},\sigma)\leq d$ and $\mathrm{dist}_{U}(\pi_{g},\sigma)\leq d$ . Let $\Sigma_{c}$ and $\Sigma_{g}$ be minimum-sized sets of moved symbols in $\pi_{c}$ and $\pi_{g}$ , respectively, to obtain $\sigma$ . By Definitions 8 and 12, the $2$ -colorings $\operatorname{\mathrm{col}}_{c}$ and $\operatorname{\mathrm{col}}_{g}$ are consistent $d$ -fitting w.r.t. $\sigma$ if

(i)

every symbol in $\Sigma_{c}$ (resp., $\Sigma_{g}$ ) is colored red in $\operatorname{\mathrm{col}}_{c}$ (resp., $\operatorname{\mathrm{col}}_{g}$ );
(ii)

every symbol in $\Sigma\setminus\Sigma_{c}$ (resp., $\Sigma\setminus\Sigma_{g}$ ) within distance $3d$ of a moved symbol in $\Sigma_{c}$ (resp., $\Sigma_{g}$ ) is colored blue in $\operatorname{\mathrm{col}}_{c}$ (resp., $\operatorname{\mathrm{col}}_{g}$ ); and
(iii)

every symbol in $\Sigma_{g}\setminus\Sigma_{c}$ (resp., $\Sigma_{c}\setminus\Sigma_{g}$ ) is colored blue in $\operatorname{\mathrm{col}}_{g}$ (resp., $\operatorname{\mathrm{col}}_{c}$ ).

Recall that both sets have size at most $d$ . The number of symbols involved in these conditions is at most

(|\Sigma_{c}|+|\Sigma_{g}|)+2\cdot 3d(|\Sigma_{c}|+|\Sigma_{g}|)+(|\Sigma_{c}|% +|\Sigma_{g}|)\leq 12d^{2}+4d=b.

Because our $(a,b)$ -universal set contains all possible pairs of colorings on any set of $b$ positions, it must contain a pair that assigns suitable colors to all $b$ involved symbols. Hence, this pair is consistent $d$ -fitting w.r.t. $\sigma$ . $\hfill\blacktriangleleft$

Given a guide $\pi_{g}$ and the candidate $\pi_{c}$ , Lemma 13 allows us to guess a consistent $d$ -fitting coloring pair $(\operatorname{\mathrm{col}}_{c},\operatorname{\mathrm{col}}_{g})$ w.r.t. some center $\sigma$ within distance $d$ of both. We now use the colorings $\operatorname{\mathrm{col}}_{c}$ and $\operatorname{\mathrm{col}}_{g}$ to capture the structural relationship between the two permutations. To this end, we consider a certain vertex cover of their permutation graph. Here, a permutation graph $G_{\pi_{c},\pi_{g}}$ of two permutations $\pi_{c},\pi_{g}\in{{\cal S}}_{n}(\Sigma)$ is the graph whose vertex set is the alphabet $\Sigma$ and its edges are exactly the (unordered) pairs of vertices whose order is reversed between $\pi_{c}$ and $\pi_{g}$ . For each edge in $G_{\pi_{c},\pi_{g}}$ , exactly one of $\pi_{c}$ and $\pi_{g}$ has the two incident symbols in the same order as the center $\sigma$ . A vertex cover of $G_{\pi_{c},\pi_{g}}$ thus gives an indication of which symbols need to be moved to transform $\pi_{g}$ and $\pi_{c}$ into $\sigma$ .

Lemma 14.

Let $d\in{\mathbb{N}}$ , $\pi_{c},\pi_{g}\in{{\cal S}}_{n}(\Sigma)$ . Let $\operatorname{\mathrm{col}}_{c}$ and $\operatorname{\mathrm{col}}_{g}$ be consistent $d$ -fitting colorings of $\pi_{c}$ and $\pi_{g}$ w.r.t. some permutation $\sigma\in{{\cal S}}_{n}(\Sigma)$ . For every pair of witnesses $\Sigma_{c},\Sigma_{g}$ for $\operatorname{\mathrm{col}}_{c}$ and $\operatorname{\mathrm{col}}_{g}$ there is an inclusion-wise minimal vertex cover $X$ of $G_{\pi_{c},\pi_{g}}$ with $X\subseteq\Sigma_{c}\cup\Sigma_{g}$ .

Proof.

We begin by showing that $\Sigma_{c}\cup\Sigma_{g}$ is a vertex cover of $G_{\pi_{c},\pi_{g}}$ . Consider an edge $x y$ in $G_{\pi_{c},\pi_{g}}$ . By definition of the permutation graphs, $x$ and $y$ appear in reversed order in $\pi_{c}$ and $\pi_{g}$ . Since $\sigma$ is obtained from $\pi_{c}$ (resp., $\pi_{g}$ ) by moving symbols in $\Sigma_{c}$ (resp., $\Sigma_{g}$ ), at least one of $x$ and $y$ must be moved in one of the two permutations. Hence, at least one of $x$ and $y$ belongs to $\Sigma_{c}\cup\Sigma_{g}$ , showing that $\Sigma_{c}\cup\Sigma_{g}$ is a vertex cover of $G_{\pi_{c},\pi_{g}}$ .

The lemma follows by exhaustively removing elements from $\Sigma_{c}\cup\Sigma_{g}$ upon whose removal all edges are still covered. $\hfill\blacktriangleleft$

Such a vertex cover indeed suffices to find a suitable vertex $x$ as required for Lemma 11.

Lemma 15.

Let $d\in{\mathbb{N}}$ , $\pi_{c},\pi_{g}\in{{\cal S}}_{n}(\Sigma)$ . Let $\operatorname{\mathrm{col}}_{c}$ and $\operatorname{\mathrm{col}}_{g}$ be consistent $d$ -fitting colorings of $\pi_{c}$ and $\pi_{g}$ w.r.t. some permutation $\sigma\in{{\cal S}}_{n}(\Sigma)$ with $\mathrm{dist}_{U}(\pi_{c},\sigma)\leq d$ and $\mathrm{dist}_{U}(\pi_{g},\sigma)\leq d$ . Consider an inclusion-wise minimal vertex cover $X$ of $G_{\pi_{c},\pi_{g}}$ with $X\subseteq\Sigma_{c}\cup\Sigma_{g}$ for a pair of witnesses $\Sigma_{c},\Sigma_{g}$ for $\operatorname{\mathrm{col}}_{c}$ and $\operatorname{\mathrm{col}}_{g}$ . Then in time ${{\cal O}}(|X|)$ we can find a symbol $x\in\Sigma$ with $x\in\Sigma_{c}\setminus\Sigma_{g}$ . The computation does not require the sets $\Sigma_{c}$ and $\Sigma_{g}$ as input.

Proof.

Observe that $\pi_{g}$ can be transformed into $\pi_{c}$ by deleting and reinserting the symbols in $X$ , so $\mathrm{dist}_{U}(\pi_{g},\pi_{c})>d$ implies that $|X|>d$ . As $\mathrm{dist}_{U}(\pi_{g},\sigma)=|\Sigma_{g}|\leq d$ , we have that there is a symbol $x\in X$ such that $x\in\Sigma_{c}\setminus\Sigma_{g}$ . As $\operatorname{\mathrm{col}}_{g}$ and $\operatorname{\mathrm{col}}_{c}$ are consistent $d$ -fitting, we have that $\operatorname{\mathrm{col}}_{c}(x)=\operatorname{\texttt{red}}$ and $\operatorname{\mathrm{col}}_{g}(x)=\operatorname{\texttt{blue}}$ . It suffices to consider any such colored symbol $x^{\prime}$ , as $\operatorname{\mathrm{col}}_{g}(x^{\prime})=\operatorname{\texttt{blue}}$ implies $x^{\prime}\notin\Sigma_{g}$ and thus, by $X\subseteq\Sigma_{c}\cup\Sigma_{g}$ we have $x^{\prime}\in\Sigma_{c}\setminus\Sigma_{g}$ . $\hfill\blacktriangleleft$ With this, we are ready to forge our central tool:

Lemma 16.

Let $d\in{\mathbb{N}}$ , and $\pi_{g},\pi_{c}\in{{\cal S}}_{n}(\Sigma)$ be two permutations with $d<\mathrm{dist}_{U}(\pi_{g},\pi_{c})\leq 2d$ . There exists a set of permutations $P\subseteq{{\cal S}}_{n}(\Sigma)$ satisfying

$\blacksquare$

the size of $P$ is bounded by $|P|\leq 2^{{{\cal O}}(d^{2})}\log n$ ; and
$\blacksquare$

for each permutation $\sigma\in{{\cal S}}_{n}(\Sigma)$ with $\mathrm{dist}_{U}(\pi_{g},\sigma)\leq d$ and $\mathrm{dist}_{U}(\pi_{c},\sigma)\leq d$ , $P$ contains a permutation $\tilde{\pi}\in P$ that is one step closer to $\sigma$ than $\pi_{c}$ , i.e., $\mathrm{dist}_{U}(\tilde{\pi},\sigma)=\mathrm{dist}_{U}(\pi_{c},\sigma)-1$ .

Furthermore, such a set can be computed in $2^{{{\cal O}}(d^{2})}n\log n$ time.

Proof.

We compute a collection ${\cal C}$ of pairs of $2$ -colorings of $\Sigma$ according to Lemma 13. For each $\sigma\in{{\cal S}}_{n}(\Sigma)$ with $\mathrm{dist}_{U}(\pi_{g},\sigma)\leq d$ and $\mathrm{dist}_{U}(\pi_{c},\sigma)\leq d$ , there exists a consistent $d$ -fitting pair of colorings $(\operatorname{\mathrm{col}}_{c},\operatorname{\mathrm{col}}_{g})\in{\cal C}$ w.r.t. $\sigma$ . Thus, for each pair in ${\cal C}$ we perform the following procedure, adding permutations to $P$ as we go along.

Based on Observation 10, we can assume that both $\operatorname{\mathrm{col}}_{c}$ and $\operatorname{\mathrm{col}}_{g}$ have at most $d$ red symbols in each block (if not, we recolor some blocks blue accordingly). We list all inclusion-wise minimal vertex covers of $G_{\pi_{c},\pi_{g}}$ that have size at most $2d$ . We can do so by a simple and well-known branching technique: Start with an empty cover, iteratively take any uncovered edge $v w$ and create two branches where you add $v$ or $w$ to the vertex cover, respectively, and repeat this procedure $2d$ times (or until all edges are covered). This list of at most $2^{2d}=4^{d}$ covers may contain some that are not inclusion-wise minimal, but these can be filtered out in time ${{\cal O}}(4^{d}\cdot|V(G_{\pi_{c},\pi_{g}})|)={{\cal O}}(4^{d}n)$ .

By Lemma 14 and as every witness for $\operatorname{\mathrm{col}}_{c}$ or $\operatorname{\mathrm{col}}_{g}$ has size at most $d$ , at least one of the listed vertex covers consists only of vertices in $\Sigma_{c}\cup\Sigma_{g}$ , where $\Sigma_{c}$ and $\Sigma_{g}$ are witnesses for the respective colorings. This holds true for every permutation $\sigma$ for which the current colorings are consistent $d$ -fitting. Using Lemma 15 on each of the vertex covers, we obtain a set of at most $4^{d}$ symbols, and for every suitable $\sigma$ at least one of these symbols is included in $\Sigma_{c}\setminus\Sigma_{g}$ for respective witnesses. We note that applying Lemma 15 to vertex covers containing vertices which do not stem from union of witnesses might yield incorrect symbols, but for each of the vertex covers we still add at most one symbol. We apply Lemma 11 to each of the $4^{d}$ symbols, thereby producing a set of $4^{d}\cdot(6d+2)$ permutations, which we all add to $P$ . Note that the lemmas guarantee that for every $\sigma$ for which the colorings are consistent $d$ -fitting, we added at least one permutation which is one step closer to $\sigma$ than the current candidate $\pi_{c}$ .

The final size of $P$ is bounded by

|P|\leq|{\cal C}|\cdot 4^{d}(6d+2)\leq 2^{{{\cal O}}(d^{2})}\log n.

The runtime estimate is based on combining the size of ${\cal C}$ from Lemma 13 with the time to find the unique vertex cover respecting a given pair of colorings. All other steps, like processing the blocks, are asymptotically dominated by that time. There are at most $2^{{{\cal O}}(d^{2})}\log n$ pairs of colorings to enumerate. For each pair, the branching procedure on the vertex covers takes ${{\cal O}}\bigl(4^{d}\cdot(|E(G_{\pi_{c},\pi_{g}})|+|V(G_{\pi_{c},\pi_{g}})|)% \bigr)={{\cal O}}(4^{d}dn)$ time as $|V(G_{\pi_{c},\pi_{g}})|=n$ and the existence of a vertex cover of size $2d$ implies that $|E(G_{\pi_{c},\pi_{g}})|\leq 2dn$ . Thus, the total time to compute $P$ is in

2^{{{\cal O}}(d^{2})}\log n\cdot{{\cal O}}(4^{d}dn)=2^{{{\cal O}}(d^{2})}n\log n.\

$\hfill\blacktriangleleft$

Now we are ready to prove Theorem 2.

Theorem 2. [Restated, see original statement.]

Ulam Metric $k$ -Center can be solved in $2^{{{\cal O}}(d^{2}k(d+k))}\cdot mn^{1+o(1)}$ time, where $m\coloneqq|\Pi|$ and $n\coloneqq|\Sigma|$ .

Proof.

We may assume without loss of generality that any YES-instance admits a solution with exactly $k$ centers. Indeed, if a solution exists with fewer than $k$ centers, we can always add arbitrary permutations as centers until we reach exactly $k$ centers. In addition, we exclude the trivial YES-instances where $k>m$ . Now, consider a hypothetical solution $S^{*}=\{\sigma_{1}^{*},\sigma_{2}^{*},\ldots,\sigma_{k}^{*}\}$ consisting of $k$ centers. For each $i\in[k]$ , let the $i$ th cluster be the set of permutations in $\Pi$ with distance at most $d$ to $\sigma_{i}^{*}$ . If a permutation would fit into multiple clusters, we assign it to only one of them arbitrarily.

We describe our algorithm as a branching procedure. It maintains a candidate set $S\subseteq{{\cal S}}_{n}(\Sigma)$ of size at most $k$ along with a budget $b_{i}$ for each candidate $\sigma_{i}\in S$ . Here, $S$ is intended to evolve into a solution to the Ulam Metric $k$ -Center instance, and each budget $b_{i}$ indicates how many modifications to $\sigma_{i}$ remain (or have been used so far). In each branch, the algorithm checks whether the current candidate set $S$ covers all permutations in $\Pi$ within distance $d$ . The algorithm halts and accepts the instance if and only if at least one branch finds a valid solution. We now describe the procedure in detail; see Algorithm 1 for a high-level overview.

Algorithm 1 Solving Ulam Metric

k

-Center for radius

d

on permutations

\Pi

.

In the course of the algorithm, we one by one initialize each candidate $\sigma_{i}$ as a permutation from $\Pi$ , and evolve it into the $i$ th center. Initially, pick the permutation $\pi_{1}\in\Pi$ and set the first candidate $\sigma_{1}$ to equal this permutation: $\sigma_{1}\coloneqq\pi$ . Then, the algorithm adds it as the first candidate to $S$ and initializes its budget as $b_{1}\coloneqq d$ .

Next, the algorithm branches on a permutation $\pi\in\Pi$ that has distance more than $d$ to each of the candidates in $S$ . If there is none, then the current candidates form a solution, and we accept the instance. Otherwise, the permutation $\pi$ either belongs to one of the existing clusters or to a new cluster.

$\blacksquare$

Existing cluster: For each candidate $\sigma_{i}\in S$ with remaining budget $b_{i}>0$ and distance at most $2d$ to $\pi$ , we consider the case where $\pi$ belongs to the $i$ th cluster. We invoke Lemma 16 with $d$ , guide $\pi_{g}=\pi$ , and $\pi_{c}=\sigma_{i}$ to obtain the set $P$ of permutations. For each permutation $\sigma_{i}^{\prime}\in P$ , we create a new branch where we replace $\sigma_{i}$ by $\sigma_{i}^{\prime}$ and decrease its budget by one.
$\blacksquare$

New cluster: If $|S|<k$ , we create a branch where $\pi$ belongs to a new cluster. Specifically, we let $\sigma_{|S|+1}=\pi$ as a new candidate, initialize its budget as $b_{|S|+1}=d$ , and add it to $S$ .

If none of the two above cases applies, we reject the branch. We accept the instance if and only if at least one branch accepts it. If none of the branches accepts the instance, we reject the branch.

Observe that if the algorithm accepts an instance, it indeed finds a solution. Conversely, consider a YES-instance of Ulam Metric $k$ -Center witnessed by some solution $S^{*}=\{\sigma_{1}^{*},\sigma_{2}^{*},\ldots,\sigma_{k}^{*}\}$ . When branching on a permutation $\pi\in\Pi$ not covered by the current candidates $S$ , there exists a branch where $\pi$ is assigned to the cluster to which it belongs in $S^{*}$ . Moreover, when $\pi$ is assigned to the $i$ th cluster from the current candidates $S$ , by Lemma 16, there is a permutation $\sigma_{i}^{\prime}\in P$ that is one step closer to $\sigma_{i}^{*}$ than $\sigma_{i}$ . Thus, in the respective branch, we replace $\sigma_{i}$ by $\sigma_{i}^{\prime}$ , moving it one step closer to $\sigma_{i}^{*}$ . Since each candidate starts with the distance at most $d$ to its respective center in $S^{*}$ , after receiving at most $d$ updates, it will have converged to that center. From this point on, it will not receive any more updates since there are no permutations assigned to that cluster with a distance of more than $d$ . Therefore, there is a branch in which the algorithm finds the solution $S^{*}$ and accepts the instance.

Finally, we analyze the running time of the algorithm. Recall that the input of the branching procedure contains a set of candidates $S$ along with their budgets $\{b_{i}:\sigma_{i}\in S\}$ . Define the measure of the current input of a branch as

\mu\coloneqq(k-|S|)(d+1)+\sum_{i=1}^{|S|}b_{i}.

and denote by $T(\mu)$ the worst-case running time of the algorithm on inputs with measure $\mu$ .

Observe that each time we add a new candidate to $S$ or modify an existing candidate in $S$ , the measure $\mu$ decreases by one. On the one hand, when we add a new candidate to $S$ , the size of $S$ increases by one while the budget of the new candidate is initialized to $d$ . Thus, the measure decreases by $(d+1)-d=1$ and there is at most one such branch. On the other hand, when we modify a candidate to a permutation from $P$ , its budget decreases by one while the size of $S$ remains unchanged. Thus, the measure decreases by $1$ as well, and there are at most $|S|\cdot|P|\leq k\cdot 2^{{{\cal O}}(d^{2})}\log n$ such branches by Lemma 16. Moreover, computing $P$ takes time in $2^{{{\cal O}}(d^{2})}n\log n$ , and the remaining time spend on this iteration is dominated by the computation of all Ulam distances to the current candidates (achievable in ${{\cal O}}(kmn\log n)$ time). Therefore, we have the recurrence

T(\mu)\leq 2^{{{\cal O}}(d^{2})}n\log n+{{\cal O}}(kmn\log n)+\big(1+k\cdot 2^% {{{\cal O}}(d^{2})}\log n\big)\cdot T(\mu-1).

Notice that the measure satisfies $\mu\leq k(d+1)$ and the algorithm halts when $\mu=0$ . Solving the recurrence yields

	$\displaystyle T(k(d+1))={}$	$\displaystyle\big(1+k\cdot 2^{{{\cal O}}(d^{2})}\log n\big)^{k(d+1)}\cdot(2^{{% {\cal O}}(d^{2})}n\log n+kmn\log n)$
	$\displaystyle={}$	$\displaystyle 2^{{{\cal O}}(d^{3}k)}\cdot k^{{{\cal O}}(dk)}\cdot(\log n)^{k(d% +1)}\cdot{{\cal O}}(mn\log n).$

Observe that

(\log n)^{k(d+1)}=2^{k(d+1)\log\log n}\leq 2^{k^{2}(d+1)^{2}+(\log\log n)^{2}}% =2^{k^{2}(d+1)^{2}}\cdot n^{(\log\log n)^{2}/\log n},

which bounds the total running time by

\displaystyle 2^{{{\cal O}}(d^{3}k+d^{2}k^{2})}\cdot k^{{{\cal O}}(dk)}\cdot{{% \cal O}}\big(mn^{1+(\log\log n)^{2}/\log n}\log n\big)=2^{{{\cal O}}(d^{2}k(d+% k))}\cdot mn^{1+o(1)}.

This shows that Ulam Metric $k$ -Center is in ${\mathsf{FPT}}$ by $k+d$ . $\hfill\blacktriangleleft$

We prove that the fixed-parameter tractability of Ulam distance with respect to $k+d$ does not extend to a polynomial kernel via a reduction from a problem on binary strings.

Theorem 3 ( $\star$ ). [Restated, see original statement.]

Ulam Metric $k$ -Center does not admit a polynomial-sized kernel for the parameter $k+d$ unless $\mathrm{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$ .

4 The Complexity of Ulam Metric $𝒌$ -Median

This section studies the parameterized complexity of Ulam Metric $k$ -Median with respect to the parameters $d$ and $k+d$ . We first prove that Ulam Metric $k$ -Median is ${\mathsf{W}}[1]$ -hard parameterized by $d$ but is in ${\mathsf{XP}}$ for this parameterization. Then we show a polynomial kernel parameterized by both $k$ and $d$ , implying fixed-parameter tractability for this parameterization.

We first rule out fixed-parameter tractability by $d$ alone under established complexity assumptions. We then contrast it with a simple ${\mathsf{XP}}$ -algorithm for Ulam Metric $k$ -Median.

For the hardness result, we give a reduction from Multicolored Clique. An instance of Multicolored Clique consists of a graph $G$ with a proper vertex coloring using $k^{\prime}$ colors, and asks whether $G$ contains a clique of size $k^{\prime}$ . The problem is known to be ${\mathsf{W}}[1]$ -hard when parameterized by $k^{\prime}$ [31]. For clarity, we here describe the reduction and then separately prove that it preserves YES-instances and NO-instances.

Let ${\cal C}=\{c_{1},c_{2},\ldots,c_{k^{\prime}}\}$ denote the color set, let $V(G)=\{v_{1},v_{2},\ldots,v_{n^{\prime}}\}$ be the vertex set of $G$ and let $E(G)=\{e_{1},e_{2},\ldots,e_{m^{\prime}}\}$ be the edge set of $G$ , where $n^{\prime}=|V(G)|$ and $m^{\prime}=|E(G)|$ . Without loss of generality, we assume that $k^{\prime}\geq 4$ , as instances with smaller values can be solved in polynomial time by brute-force.

We construct an instance $(\Pi,k,d)$ of Ulam Metric $k$ -Median with $k=m^{\prime}-\binom{k^{\prime}}{2}+1$ . The idea of the reduction is to create one permutation for each edge in $G$ . We build the instance in a way such that the existence of a multicolored clique $Q\subseteq V(G)$ allows the construction of a center permutation $\sigma_{Q}$ such that edges with both endpoints in $Q$ have small total distance to $\sigma_{Q}$ , while every other edge can take itself as its center. Consequently, the number of centers required is $m^{\prime}-\binom{|Q|}{2}+1=k$ , and the median distance is entirely contributed by the edges inside $Q$ . It remains to choose a suitable value for $d$ .

Formally, let $q=\binom{k^{\prime}}{2}(k^{\prime}-2)+1$ . Furthermore, we define the alphabet as the union of the color set, some $v$ -symbols representing the vertices, and some $x$ -, $y$ -, and $z$ -symbols representing the edges:

\Sigma={\cal C}\cup\big\{v_{j}^{i}:i\in[q],v_{j}\in V(G)\big\}\cup\big\{x_{j}^% {i},y_{j}^{i},z_{j}^{i}:i\in[q],e_{j}\in E(G)\big\}.

We have $n=|\Sigma|=k^{\prime}+n^{\prime}q+3m^{\prime}q$ . We first construct a base permutation $\pi_{\mathrm{base}}\in S_{n}(\Sigma)$ that starts with alternating between the $x$ - and $y$ -symbols, followed by the $v$ - and the $z$ -symbols, and finally the color-symbols:

	$\displaystyle\pi_{\mathrm{base}}\coloneq{}$	$\displaystyle\hbox{\pagecolor{black!20}$\displaystyle x_{1}^{1}\;y_{1}^{1}% \cdots x_{1}^{q}\;y_{1}^{q}$}\ \hbox{\pagecolor{black!20}$\displaystyle x_{2}^% {1}\;y_{2}^{1}\cdots x_{2}^{q}\;y_{2}^{q}$}\cdots\hbox{\pagecolor{black!20}$% \displaystyle x_{m^{\prime}}^{1}\;y_{m^{\prime}}^{1}\cdots x_{m^{\prime}}^{q}% \;y_{m^{\prime}}^{q}$}\;$
		$\displaystyle\hbox{\pagecolor{black!20}$\displaystyle v_{1}^{1}\;v_{1}^{2}% \cdots v_{1}^{q}$}\;\hbox{\pagecolor{black!20}$\displaystyle v_{2}^{1}\;v_{2}^% {2}\cdots v_{2}^{q}$}\cdots\hbox{\pagecolor{black!20}$\displaystyle v_{n^{% \prime}}^{1}\;v_{n^{\prime}}^{2}\cdots v_{n^{\prime}}^{q}$}\;$
		$\displaystyle\hbox{\pagecolor{black!20}$\displaystyle z_{1}^{1}\;z_{1}^{2}% \cdots z_{1}^{q}$}\;\hbox{\pagecolor{black!20}$\displaystyle z_{2}^{1}\;z_{2}^% {2}\cdots z_{2}^{q}$}\cdots\hbox{\pagecolor{black!20}$\displaystyle z_{m^{% \prime}}^{1}\;z_{m^{\prime}}^{2}\cdots z_{m^{\prime}}^{q}$}$
		$\displaystyle\hbox{\pagecolor{black!20}$\displaystyle c_{1}\;c_{2}\cdots c_{k^% {\prime}}$}.$

For each edge $e_{j}=v_{a}v_{b}\in E(G)$ with $a<b$ , we introduce a permutation $\pi_{e_{j}}$ obtained from $\pi_{\mathrm{base}}$ as follows. Suppose $v_{a}$ has color $c_{\alpha}$ and $v_{b}$ has color $c_{\beta}$ . Swap $x_{j}^{i}$ and $y_{j}^{i}$ for each $i\in[q]$ ; move $c_{\alpha}$ to the right of $v_{a}^{q}$ ; move $c_{\beta}$ to the right of $v_{b}^{q}$ ; and move the remaining color-symbols to the right of $z^{q}_{j}$ without changing their relative order. That is,

	$\displaystyle\pi_{e_{j}}\coloneq{}$	$\displaystyle\hbox{\pagecolor{black!20}$\displaystyle x_{1}^{1}\;y_{1}^{1}% \cdots x_{1}^{q}\;y_{1}^{q}$}\cdots\hbox{\pagecolor{black!40}$\displaystyle y_% {j}^{1}\;x_{j}^{1}\cdots y_{j}^{q}\;x_{j}^{q}$}\cdots\hbox{\pagecolor{black!20% }$\displaystyle x_{m^{\prime}}^{1}\;y_{m^{\prime}}^{1}\cdots x_{m^{\prime}}^{q% }\;y_{m^{\prime}}^{q}$}$
		$\displaystyle\hbox{\pagecolor{black!20}$\displaystyle v_{1}^{1}\cdots v_{1}^{q% }$}\cdots\hbox{\pagecolor{black!20}$\displaystyle v_{a}^{1}\cdots v_{a}^{q}$}% \;\hbox{\pagecolor{black!40}$\displaystyle c_{\alpha}$}\cdots\hbox{\pagecolor{% black!20}$\displaystyle v_{b}^{1}\cdots v_{b}^{q}$}\;\hbox{\pagecolor{black!40% }$\displaystyle c_{\beta}$}\cdots\hbox{\pagecolor{black!20}$\displaystyle v_{n% ^{\prime}}^{1}\cdots v_{n^{\prime}}^{q}$}$
		$\displaystyle\hbox{\pagecolor{black!20}$\displaystyle z_{1}^{1}\cdots z_{1}^{q% }$}\cdots\hbox{\pagecolor{black!20}$\displaystyle z_{j}^{1}\cdots z_{j}^{q}$}% \;\hbox{\pagecolor{black!40}$\displaystyle\chi_{\alpha,\beta}$}\;\hbox{% \pagecolor{black!20}$\displaystyle z_{j+1}^{1}\cdots z_{j+1}^{q}$}\cdots\hbox{% \pagecolor{black!20}$\displaystyle z_{m^{\prime}}^{1}\cdots z^{q}_{m^{\prime}}% $},$

where $\chi_{\alpha,\beta}=\hbox{\pagecolor{black!20}$\displaystyle c_{1}\cdots c_{% \alpha-1}\;c_{\alpha+1}\cdots c_{\beta-1}\;c_{\beta+1}\cdots c_{k^{\prime}}$}$ . Finally, recall that $k=m^{\prime}-\binom{k^{\prime}}{2}+1$ . We set $d=\binom{k^{\prime}}{2}(q+(k^{\prime}-2))$ , and let the set of permutations consist of all permutations for edges in the graph, i.e., $\Pi=\{\pi_{e_{j}}:e_{j}\in E(G)\}$ .

Lemma 17.

The stated reduction from MultiColoredClique to Ulam Metric $k$ -Median preserves YES-instances.

Proof.

Assume that $G$ contains a clique $Q$ of size at least $k^{\prime}$ , which contains exactly one vertex of each color. We prove that there is a set $S$ of size $k$ that is a solution for the Ulam Metric $k$ -Median instance $(\Pi,k,d)$ . For each vertex $v_{j}\in Q$ , let $c_{\varphi(j)}$ be the color of $v_{j}$ . Define $\sigma_{Q}$ to be the permutation obtained from $\pi_{\mathrm{base}}$ by moving each symbol $c_{\varphi(j)}\in C$ right after the symbol $v_{j}^{q}\in Q$ . (There is no color-symbol after $v_{j}^{q}$ if $v_{j}\not\in Q$ .) That is, if $Q=\{v_{j_{1}},v_{j_{2}},\ldots,v_{j_{k^{\prime}}}\}$ with $j_{1}<j_{2}<\cdots<j_{k^{\prime}}$ , then

	$\displaystyle\sigma_{Q}\coloneq{}$	$\displaystyle\hbox{\pagecolor{black!20}$\displaystyle x_{1}^{1}\;y_{1}^{1}% \cdots x_{1}^{q}\;y_{1}^{q}$}\;\hbox{\pagecolor{black!20}$\displaystyle x_{2}^% {1}\;y_{2}^{1}\cdots x_{2}^{q}\;y_{2}^{q}$}\cdots\hbox{\pagecolor{black!20}$% \displaystyle x_{m^{\prime}}^{1}\;y_{m^{\prime}}^{1}\cdots x_{m^{\prime}}^{q}% \;y_{m^{\prime}}^{q}$}\;$
		$\displaystyle\hbox{\pagecolor{black!20}$\displaystyle v_{1}^{1}\cdots v_{1}^{q% }$}\cdots\hbox{\pagecolor{black!20}$\displaystyle v_{j_{1}-1}^{1}\cdots v_{j_{% 1}-1}^{q}$}\;\hbox{\pagecolor{black!20}$\displaystyle v_{j_{1}}^{1}\cdots v_{j% _{1}}^{q}$}\;\hbox{\pagecolor{black!40}$\displaystyle c_{\varphi(j_{1})}$}\;% \hbox{\pagecolor{black!20}$\displaystyle v_{j_{1}+1}^{1}\cdots v_{j_{1}+1}^{q}$}$
		$\displaystyle\phantom{\hbox{\pagecolor{black!20}$\displaystyle v_{1}^{1}\cdots v% _{1}^{q}$}}\cdots\hbox{\pagecolor{black!20}$\displaystyle v_{j_{i}-1}^{1}% \cdots v_{j_{i}-1}^{q}$}\;\hbox{\pagecolor{black!20}$\displaystyle v_{j_{i}}^{% 1}\cdots v_{j_{i}}^{q}$}\;\hbox{\pagecolor{black!40}$\displaystyle c_{\varphi(% j_{i})}$}\;\hbox{\pagecolor{black!20}$\displaystyle v_{j_{i}+1}^{1}\cdots v_{j% _{i}+1}^{q}$}$
		$\displaystyle\phantom{\hbox{\pagecolor{black!20}$\displaystyle v_{1}^{1}\cdots v% _{1}^{q}$}}\cdots\hbox{\pagecolor{black!20}$\displaystyle v_{j_{k^{\prime}}-1}% ^{1}\cdots v_{j_{k^{\prime}}-1}^{q}$}\;\hbox{\pagecolor{black!20}$% \displaystyle v_{j_{k^{\prime}}}^{1}\cdots v_{j_{k^{\prime}}}^{q}$}\;\hbox{% \pagecolor{black!40}$\displaystyle c_{\varphi(j_{k^{\prime}})}$}\;\hbox{% \pagecolor{black!20}$\displaystyle v_{j_{k^{\prime}}+1}^{1}\cdots v_{j_{k^{% \prime}}+1}^{q}$}$
		$\displaystyle\cdots\hbox{\pagecolor{black!20}$\displaystyle v_{n^{\prime}}^{1}% \cdots v_{n^{\prime}}^{q}$}\;\hbox{\pagecolor{black!20}$\displaystyle z_{1}^{1% }\cdots z_{1}^{q}$}\;\hbox{\pagecolor{black!20}$\displaystyle z_{2}^{1}\cdots z% _{2}^{q}$}\cdots\hbox{\pagecolor{black!20}$\displaystyle z_{m^{\prime}}^{1}% \cdots z_{m^{\prime}}^{q}$}.$

We then let $S=\{\sigma_{Q}\}\cup\Pi\setminus\Pi_{Q}$ , where $\Pi_{Q}\subseteq\Pi$ is the set of $\binom{k^{\prime}}{2}$ permutations associated with an edge that has both endpoints covered by $Q$ . Observe that $|S|=m^{\prime}-\binom{k^{\prime}}{2}+1=k$ and the sum of distances of each permutation to its closest median is at most $\sum_{\pi\in\Pi_{Q}}\mathrm{dist}_{U}(\pi,\sigma_{Q})$ . Any permutation in $\Pi_{Q}$ can be transformed into $\sigma_{Q}$ by moving the $k^{\prime}-2$ color-symbols that are not yet at the correct position as well as the $q$ symbols of the form $x_{j}^{i}$ with $i\in[q]$ . Thus, the total sum of distances is at most $\binom{k^{\prime}}{2}(q+(k^{\prime}-2))=d$ . $\hfill\blacktriangleleft$

Lemma 18.

The stated reduction from MultiColoredClique to Ulam Metric $k$ -Median preserves NO-instances.

Proof.

We prove by showing that the existence of a solution to the constructed Ulam Metric $k$ -Median instance implies the existence of a solution to the MultiColoredClique instance.

Assume the Ulam Metric $k$ -Median instance is solved by a set $S$ of permutation medians which minimize the sum of distances. Consider the clustering of $\Pi$ described by $S$ , where we have one cluster per median permutation in $S$ and each permutation in $\Pi$ is assigned to the cluster of the closest median under Ulam metric (breaking ties arbitrarily). For ease of presentation, we partition the alphabet $\Sigma$ into two parts: $\Sigma^{\prime}$ is the set of $x$ - and $y$ -symbols; and $\Sigma^{\prime\prime}$ is the set of $v$ -, $z$ -, and color-symbols. By construction, any permutation $\pi_{e}$ in $\Pi$ is a concatenation of two substrings $\pi^{\prime}_{e}\in{{\cal S}}_{2m^{\prime}q}(\Sigma^{\prime})$ and $\pi^{\prime\prime}_{e}\in{{\cal S}}_{k^{\prime}+n^{\prime}q+m^{\prime}q}(% \Sigma^{\prime\prime})$ . It is easy to see that $\mathrm{dist}_{U}(\pi_{e_{1}},\pi_{e_{2}})=\mathrm{dist}_{U}(\pi^{\prime}_{e_{% 1}},\pi^{\prime}_{e_{2}})+\mathrm{dist}_{U}(\pi^{\prime\prime}_{e_{1}},\pi^{% \prime\prime}_{e_{2}})$ for any pair of permutations $\pi_{e_{1}},\pi_{e_{2}}\in\Pi$ . We further define $C^{\prime}=\{\pi^{\prime}_{e}:\pi_{e}\in C\}$ and $C^{\prime\prime}=\{\pi^{\prime\prime}_{e}:\pi_{e}\in C\}$ for any cluster $C$ in the clustering.

Clearly, there exists a cluster of size at least two as $k<m^{\prime}$ . Consider a cluster $C$ of size $|C|\geq 2$ . We first argue that $C$ is the unique cluster of size more than one. Let $\sigma$ be its median with optimal total distance to the permutations in $C$ . By the optimality of $\sigma$ , the center $\sigma$ starts with a substring $\sigma^{\prime}\in{{\cal S}}_{2m^{\prime}q}(\Sigma^{\prime})$ and end with a substring $\sigma^{\prime\prime}\in{{\cal S}}_{k^{\prime}+n^{\prime}q+m^{\prime}q}(\Sigma% ^{\prime\prime})$ . It is easy to see that $\mathrm{dist}_{U}(\pi_{e},\sigma)=\mathrm{dist}_{U}(\pi^{\prime}_{e},\sigma^{% \prime})+\mathrm{dist}_{U}(\pi^{\prime\prime}_{e},\sigma^{\prime\prime})$ for any permutation $\pi_{e}\in C$ . This means that we can optimize $\sigma^{\prime}$ and $\sigma^{\prime\prime}$ independently to minimize the total distance. First, restrict our attention to the $x$ - and $y$ -symbols. For any pair of permutations $\pi^{\prime}_{e_{1}},\pi^{\prime}_{e_{2}}\in C^{\prime}$ , we have $\mathrm{dist}_{U}(\pi^{\prime}_{e_{1}},\pi^{\prime}_{e_{2}})\geq 2q$ as they have swapped the $x$ - and $y$ -symbols for distinct edges. Thus, we can derive that

	$\displaystyle\sum_{\pi^{\prime}_{e}\in C^{\prime}}\mathrm{dist}_{U}(\pi^{% \prime}_{e},\sigma^{\prime})={}$	$\displaystyle\frac{1}{\|C^{\prime}\|-1}\sum_{\{\pi^{\prime}_{e_{1}},\pi^{\prime}% _{e_{2}}\}\subseteq C^{\prime}}(\mathrm{dist}_{U}(\pi^{\prime}_{e_{1}},\sigma^% {\prime})+\mathrm{dist}_{U}(\pi^{\prime}_{e_{2}},\sigma^{\prime}))$
	$\displaystyle\geq{}$	$\displaystyle\frac{1}{\|C^{\prime}\|-1}\sum_{\{\pi^{\prime}_{e_{1}},\pi^{\prime}% _{e_{2}}\}\subseteq C^{\prime}}\mathrm{dist}_{U}(\pi^{\prime}_{e_{1}},\pi^{% \prime}_{e_{2}})$
	$\displaystyle\geq{}$	$\displaystyle\frac{1}{\|C^{\prime}\|-1}\cdot\binom{\|C^{\prime}\|}{2}\cdot 2q=\|C^{% \prime}\|q=\|C\|q.$

Suppose for the contraction that there were $r$ clusters $C_{1},C_{2},\ldots,C_{r}$ ( $r\geq 2$ ) of size at least two with respective medians $\sigma_{1}^{\prime},\sigma_{2}^{\prime},\ldots\sigma_{r}^{\prime}$ . Summing over all these clusters yields

(|C^{\prime}_{1}|+|C^{\prime}_{2}|+\cdots+|C^{\prime}_{r}|)q\leq\sum_{i\in[r]}% \sum_{\pi^{\prime}_{e}\in C^{\prime}_{i}}\mathrm{dist}_{U}(\pi^{\prime}_{e},% \sigma_{i}^{\prime})\leq d=\binom{k^{\prime}}{2}\big(q+(k^{\prime}-2)\big)<% \Big(\binom{k^{\prime}}{2}+1\Big)q,

which implies that $|C_{1}|+|C_{2}|+\cdots+|C_{r}|\leq\binom{k^{\prime}}{2}$ . By the definition of $k$ we have

\displaystyle m^{\prime}+r-(|C_{1}|+|C_{2}|+\cdots+|C_{r}|)\leq k=m^{\prime}-% \binom{k^{\prime}}{2}+1,

leading to $r\leq 1$ , a contradiction. Hence, we conclude that $C$ is the unique cluster of size more than one, which indicates $|C|\geq m^{\prime}-k^{\prime}+1=\binom{k^{\prime}}{2}$ .

Since $(\Pi,k,d)$ is a YES-instance, we have $d$ is at least

\sum_{\pi_{e}\in C}\mathrm{dist}_{U}(\pi_{e},\sigma)=\sum_{\pi^{\prime}_{e}\in C% ^{\prime}}\mathrm{dist}_{U}(\pi^{\prime}_{e},\sigma^{\prime})+\sum_{\pi^{% \prime\prime}_{e}\in C^{\prime\prime}}\mathrm{dist}_{U}(\pi^{\prime\prime}_{e}% ,\sigma^{\prime\prime})\geq|C^{\prime}|q+\sum_{\pi^{\prime\prime}_{e}\in C^{% \prime\prime}}\mathrm{dist}_{U}(\pi^{\prime\prime}_{e},\sigma^{\prime\prime}).

Since $d=\binom{k^{\prime}}{2}(q+(k^{\prime}-2))$ and $|C^{\prime}|=|C|\geq\binom{k^{\prime}}{2}$ , we derive that

\sum_{\pi^{\prime\prime}_{e}\in C^{\prime\prime}}\mathrm{dist}_{U}(\pi^{\prime% \prime}_{e},\sigma^{\prime\prime})\leq\binom{k^{\prime}}{2}(k^{\prime}-2)=q-1.

This implies that only color-symbols can be moved from $\sigma^{\prime\prime}$ to each permutation $\pi^{\prime\prime}_{e}$ in $C^{\prime\prime}$ : there are $q$ copies of each $v$ - and $z$ -symbol in $\Sigma^{\prime\prime}$ and they are ordered the same way in all permutations. Suppose $\bar{{\cal C}}\subseteq{\cal C}$ is the set of colors located before $z_{1}^{1}$ in $\sigma^{\prime\prime}$ , and let $\bar{k}=|\bar{{\cal C}}|$ . Recall that each permutation $\pi_{e}$ has two of the $k^{\prime}\geq 4$ color-symbols placed before $z_{1}^{1}$ ; one each after the symbols for its incident vertices. Thus, for at most $\binom{\bar{k}}{2}$ of the permutations in $C^{\prime\prime}$ , both of these color-symbols are in $\bar{{\cal C}}$ . All other permutations have to move at least one of the two symbols, which requires a total of at least $\binom{k^{\prime}}{2}-\binom{\bar{k}}{2}$ units of the budget. Additionally, for each permutation in $C^{\prime\prime}$ , all $k^{\prime}-2$ color-symbols after $z_{1}^{1}$ have to be moved, except a total of at most $k^{\prime}-\bar{k}$ symbols across all permutations. As a result, the total number of required move operations is at least

	$\displaystyle\sum_{\pi^{\prime\prime}_{e}\in C^{\prime\prime}}\mathrm{dist}_{U% }(\pi^{\prime\prime}_{e},\sigma^{\prime\prime})\geq{}$	$\displaystyle\binom{k^{\prime}}{2}-\binom{\bar{k}}{2}+\binom{k^{\prime}}{2}(k^% {\prime}-2)-\big(k^{\prime}-\bar{k}\big)$
	$\displaystyle={}$	$\displaystyle\binom{k^{\prime}}{2}(k^{\prime}-2)+\frac{1}{2}\Big(k^{\prime}(k^% {\prime}-3)-\bar{k}\big(\bar{k}-3\big)\Big)\geq\binom{k^{\prime}}{2}(k^{\prime% }-2).$

Combine this with the bound on $\sum_{\pi^{\prime}_{e}\in C^{\prime}}\mathrm{dist}_{U}(\pi^{\prime}_{e},\sigma% ^{\prime})$ , and we finally have

	$\displaystyle\sum_{\pi_{e}\in C}\mathrm{dist}_{U}(\pi_{e},\sigma)={}$	$\displaystyle\sum_{\pi^{\prime}_{e}\in C^{\prime}}\mathrm{dist}_{U}(\pi^{% \prime}_{e},\sigma^{\prime})+\sum_{\pi^{\prime\prime}_{e}\in C^{\prime\prime}}% \mathrm{dist}_{U}(\pi^{\prime\prime}_{e},\sigma^{\prime\prime})$
	$\displaystyle\geq{}$	$\displaystyle\binom{k^{\prime}}{2}q+\binom{k^{\prime}}{2}(k^{\prime}-2)=d.$

Hence, all inequalities above are in fact equalities, which yields $|C^{\prime}|=k^{\prime}$ and $\bar{k}=k^{\prime}$ . In other words, all color-symbols are placed somewhere before $z_{1}^{1}$ in $\sigma$ . Note further that the budget $d$ is only sufficient if for every permutation $\pi_{e}\in C$ both color-symbols “incident” to $e$ are located between the same substrings of $v$ -symbols as in $\sigma$ . Hence, the union of all endpoints of the $\binom{k^{\prime}}{2}$ distinct edges described by $C$ has size $|C^{\prime}|=k^{\prime}$ , implying that these edges form a $k^{\prime}$ -clique in $G$ . $\hfill\blacktriangleleft$

The ${\mathsf{W}}[1]$ -hardness of Ulam Metric $k$ -Median immediately follows from Lemmas 17 and 18 and the facts that the described reduction can be computed in polynomial time and determines $d$ by a computable function of $k^{\prime}$ . See 5

We contrast this lower bound by designing a simple ${\mathsf{XP}}$ -algorithm for Ulam Metric $k$ -Median.

Theorem 4 ( $\star$ ). [Restated, see original statement.]

Ulam Metric $k$ -Median can be solved in ${{\cal O}}((mn)^{2d})$ time, where $m\coloneqq|\Pi|$ and $n\coloneqq|\Sigma|$ .

Last, we find a polynomial-sized kernel with respect to $k+d$ , which also establishes the fixed-parameter tractability Ulam Metric $k$ -Median by $k+d$ . See 6

5 Conclusion

We initiated the study of the parameterized complexity of the Ulam Metric $k$ -Center and Ulam Metric $k$ -Median problems. Prior to our work, even the parameterized complexity for the case $k=1$ with parameter $d$ was unknown for these problems.

It is known [18] that Closest String cannot be solved in $2^{o(d\log d)}\cdot(nm)^{{{\cal O}}(1)}$ time unless the Exponential Time Hypothesis (ETH) fails (we refer to [18] for the formal definition of ETH). Then the Polynomial Parameter Transformation from Theorem 3 implies the same computational lower bound for Ulam Metric $1$ -Center. Is it possible to solve Ulam Metric $1$ -Center for $k=1$ in $d^{{{\cal O}}(d)}\cdot(nm)^{{{\cal O}}(1)}$ time similarly to Closest String?

For Ulam Metric $k$ -Median, it is shown that the problem is ${\mathsf{W}}[1]$ -hard when parameterized by $d$ but is in $\mathsf{XP}$ under the same parameterization. Furthermore, the problem admits a polynomial kernel for the parameterization by both $k$ and $d$ . The latter result together with an $\mathsf{XP}$ -algorithm implies that Ulam Metric $k$ -Median can be solved in $(kd)^{{{\cal O}}(d)}\cdot(mn)^{{{\cal O}}(1)}$ time. Is it possible to improve this running time? Similarly to Ulam Metric $k$ -Center, we find that this question is interesting even for $k=1$ . Is there a single-exponential (or even subexponential) in $d$ algorithm?

References

[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] Alexandr Andoni and Huy L. Nguyen. Near-optimal sublinear time algorithms for ulam distance. In Proceedings of the ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 76–86. SIAM, 2010. doi:10.1137/1.9781611973075.8.
[4] Kenneth J. Arrow. Social Choice and Individual Values. Wiley, 1951. 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 kernelization complexity of string problems. Theoretical Computer Science, 730:21–31, 2018. doi:10.1016/j.tcs.2018.03.024.
[7] Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, and Frances A. Rosamond. Fixed-parameter algorithms for kemeny rankings. Theoretical Computer Science, 410(45):4554–4570, 2009. Algorithmic Aspects in Information and Management. 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, 2010. 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 crossings in permutations. Discrete Mathematics, 309(7):1813–1823, 2009. doi:10.1016/j.disc.2007.12.088.
[11] Leizhen Cai, Siu Man Chan, and Siu On Chan. Random separation: A new method for solving fixed-cardinality optimization problems. In Second International Workshop on Parameterized and Exact Computation (IWPEC), volume 4169 of Lecture Notes in Computer Science, pages 239–250. Springer, 2006. doi:10.1007/11847250_22.
[12] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Approximating the median under the Ulam metric. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 761–775. SIAM, 2021. doi:10.1137/1.9781611976465.48.
[13] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Clustering permutations: New techniques with streaming applications. In Innovations in Theoretical Computer Science Conference (ITCS), 2023. doi:10.4230/LIPIcs.ITCS.2023.31.
[14] Diptarka Chakraborty, Syamantak Das, Arindam Khan, and Aditya Subramanian. Fair rank aggregation. In NeurIPS, 2022. 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. In Foundations of Software Technology and Theoretical Computer Science, 2021. doi:10.4230/LIPIcs.FSTTCS.2021.12.
[16] Ronald Christian, Michael R. Fellows, Frances Rosamond, and Arkadii Slinko. On complexity of lobbying in multiple referenda. Review of Economic Design, 11:217–224, 2007. doi:10.1007/s10058-007-0028-1.
[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, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[19] Debarati Das and Amit Kumar. Breaking the two approximation barrier for various consensus clustering problems. In Proceedings 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. Spearman’s footrule as a measure of disarray. Journal of the Royal Statistical Society. Series B (Methodological), 39(2):262–268, 1977. URL: http://www.jstor.org/stable/2984804.
[21] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proceedings 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 classification via rank aggregation. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 301–312. ACM, 2003. doi:10.1145/872757.872795.
[23] Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, and Saket Saurabh. Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems. Tsinghua Science and Technology, 19(4):374–386, 2014. doi:10.1109/TST.2014.6867519.
[24] Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S. Hardness of Median and Center in the Ulam Metric. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors, 33rd Annual European Symposium on Algorithms (ESA 2025), volume 351 of Leibniz International Proceedings in Informatics (LIPIcs), pages 111:1–111:17, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2025.111.
[25] Jens Gramm, Rolf Niedermeier, and Peter Rossmanith. Fixed-parameter algorithms for CLOSEST STRING and related problems. Algorithmica, 37(1):25–42, 2003. doi:10.1007/s00453-003-1028-3.
[26] Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. Robust-Sorting and Applications to Ulam-Median. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 100:1–100:19, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.100.
[27] Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 95–103. ACM, 2007. doi:10.1145/1250790.1250806.
[28] Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In Foundations of Computer Science (FOCS), pages 182–191. IEEE Computer Society, 1995. doi:10.1109/SFCS.1995.492475.
[29] Timothy Naumovitz, Michael E. Saks, and C. Seshadhri. Accurate and nearly optimal sublinear approximations to ulam distance. In Proceedings of the ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 2012–2031. SIAM, 2017. doi:10.1137/1.9781611974782.131.
[30] Pavel A. Pevzner. Computational molecular biology: An algorithmic approach. MIT Press, 2000.
[31] 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.
[32] Svatopluk Poljak. A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae, 015(2):307–309, 1974. URL: http://eudml.org/doc/16622.
[33] Anke van Zuylen and David P. Williamson. Deterministic algorithms for rank aggregation and other ranking and clustering problems. In Approximation and Online Algorithms, pages 260–273. Springer, 2007. doi:10.1007/978-3-540-77918-6_21.

[bib.bib1] [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.

[bib.bib2] [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.

[bib.bib3] [3] Alexandr Andoni and Huy L. Nguyen. Near-optimal sublinear time algorithms for ulam distance. In Proceedings of the ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 76–86. SIAM, 2010. doi:10.1137/1.9781611973075.8.

[bib.bib4] [4] Kenneth J. Arrow. Social Choice and Individual Values. Wiley, 1951. URL: http://www.jstor.org/stable/j.ctt1nqb90.

[bib.bib5] [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.

[bib.bib6] [6] Manu Basavaraju, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan, and Saket Saurabh. On the kernelization complexity of string problems. Theoretical Computer Science, 730:21–31, 2018. doi:10.1016/j.tcs.2018.03.024.

[bib.bib7] [7] Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, and Frances A. Rosamond. Fixed-parameter algorithms for kemeny rankings. Theoretical Computer Science, 410(45):4554–4570, 2009. Algorithmic Aspects in Information and Management. doi:10.1016/j.tcs.2009.08.033.

[bib.bib8] [8] Nadja Betzler, Jiong Guo, and Rolf Niedermeier. Parameterized computational complexity of Dodgson and Young elections. Information and Computation, 208(2):165–177, 2010. doi:10.1016/j.ic.2009.10.001.

[bib.bib9] [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.

[bib.bib10] [10] Therese Biedl, Franz-Josef Brandenburg, and Xiaotie Deng. On the complexity of crossings in permutations. Discrete Mathematics, 309(7):1813–1823, 2009. doi:10.1016/j.disc.2007.12.088.

[bib.bib11] [11] Leizhen Cai, Siu Man Chan, and Siu On Chan. Random separation: A new method for solving fixed-cardinality optimization problems. In Second International Workshop on Parameterized and Exact Computation (IWPEC), volume 4169 of Lecture Notes in Computer Science, pages 239–250. Springer, 2006. doi:10.1007/11847250_22.

[bib.bib12] [12] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Approximating the median under the Ulam metric. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 761–775. SIAM, 2021. doi:10.1137/1.9781611976465.48.

[bib.bib13] [13] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Clustering permutations: New techniques with streaming applications. In Innovations in Theoretical Computer Science Conference (ITCS), 2023. doi:10.4230/LIPIcs.ITCS.2023.31.

[bib.bib14] [14] Diptarka Chakraborty, Syamantak Das, Arindam Khan, and Aditya Subramanian. Fair rank aggregation. In NeurIPS, 2022. URL: http://papers.nips.cc/paper_files/paper/2022/hash/974309ef51ebd89034adc64a57e304f2-Abstract-Conference.html.

[bib.bib15] [15] Diptarka Chakraborty, Kshitij Gajjar, and Agastya Vibhuti Jha. Approximating the center ranking under ulam. In Foundations of Software Technology and Theoretical Computer Science, 2021. doi:10.4230/LIPIcs.FSTTCS.2021.12.

[bib.bib16] [16] Ronald Christian, Michael R. Fellows, Frances Rosamond, and Arkadii Slinko. On complexity of lobbying in multiple referenda. Review of Economic Design, 11:217–224, 2007. doi:10.1007/s10058-007-0028-1.

[bib.bib17] [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.

[bib.bib18] [18] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib19] [19] Debarati Das and Amit Kumar. Breaking the two approximation barrier for various consensus clustering problems. In Proceedings of the ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 323–372. SIAM, 2025. doi:10.1137/1.9781611978322.10.

[bib.bib20] [20] Persi Diaconis and R. L. Graham. Spearman’s footrule as a measure of disarray. Journal of the Royal Statistical Society. Series B (Methodological), 39(2):262–268, 1977. URL: http://www.jstor.org/stable/2984804.

[bib.bib21] [21] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th International Conference on World Wide Web (WWW), pages 613–622. ACM, 2001. doi:10.1145/371920.372165.

[bib.bib22] [22] Ronald Fagin, Ravi Kumar, and D. Sivakumar. Efficient similarity search and classification via rank aggregation. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 301–312. ACM, 2003. doi:10.1145/872757.872795.

[bib.bib23] [23] Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, and Saket Saurabh. Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems. Tsinghua Science and Technology, 19(4):374–386, 2014. doi:10.1109/TST.2014.6867519.

[bib.bib24] [24] Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S. Hardness of Median and Center in the Ulam Metric. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors, 33rd Annual European Symposium on Algorithms (ESA 2025), volume 351 of Leibniz International Proceedings in Informatics (LIPIcs), pages 111:1–111:17, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2025.111.

[bib.bib25] [25] Jens Gramm, Rolf Niedermeier, and Peter Rossmanith. Fixed-parameter algorithms for CLOSEST STRING and related problems. Algorithmica, 37(1):25–42, 2003. doi:10.1007/s00453-003-1028-3.

[bib.bib26] [26] Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. Robust-Sorting and Applications to Ulam-Median. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 100:1–100:19, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.100.

[bib.bib27] [27] Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 95–103. ACM, 2007. doi:10.1145/1250790.1250806.

[bib.bib28] [28] Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In Foundations of Computer Science (FOCS), pages 182–191. IEEE Computer Society, 1995. doi:10.1109/SFCS.1995.492475.

[bib.bib29] [29] Timothy Naumovitz, Michael E. Saks, and C. Seshadhri. Accurate and nearly optimal sublinear approximations to ulam distance. In Proceedings of the ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 2012–2031. SIAM, 2017. doi:10.1137/1.9781611974782.131.

[bib.bib30] [30] Pavel A. Pevzner. Computational molecular biology: An algorithmic approach. MIT Press, 2000.

[bib.bib31] [31] 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.

[bib.bib32] [32] Svatopluk Poljak. A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae, 015(2):307–309, 1974. URL: http://eudml.org/doc/16622.

[bib.bib33] [33] Anke van Zuylen and David P. Williamson. Deterministic algorithms for rank aggregation and other ranking and clustering problems. In Approximation and Online Algorithms, pages 260–273. Springer, 2007. doi:10.1007/978-3-540-77918-6_21.

Clustering Permutations Under the Ulam Metric: A Parameterized Complexity Study

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Clustering Under the Ulam Metric: Definitions and Main Results

1.2 Contributions and Techniques for Ulam Metric k-Center

Theorem 1 (⋆).

Theorem 2.

Theorem 3 (⋆).

1.3 Contributions and Techniques for Ulam Metric k-Median

Theorem 4 (⋆).

Theorem 5.

Theorem 6 (⋆).

Corollary 7.

2 Preliminaries

Basic notation.

Ulam distance.

Graphs.

Parameterized Complexity.

3 The Complexity of Ulam Metric k-Center

3.1 Lower Bound for Constant Radius 𝒅

Theorem 1 (⋆). [Restated, see original statement.]

3.2 Fixed-Parameter Tractability by 𝒌+𝒅

Definition 8 (d-fitting coloring and witness).

Definition 9 (Blocks).

Observation 10.

Lemma 11.

Proof.

Definition 12 (Consistent d-fitting colorings).

Lemma 13.

Proof.

Lemma 14.

Proof.

Lemma 15.

Proof.

Lemma 16.

Proof.

Theorem 2. [Restated, see original statement.]

Proof.

Theorem 3 (⋆). [Restated, see original statement.]

4 The Complexity of Ulam Metric 𝒌-Median

Lemma 17.

Proof.

Lemma 18.

Proof.

Theorem 4 (⋆). [Restated, see original statement.]

5 Conclusion

References

Clustering Permutations Under the Ulam Metric:
A Parameterized Complexity Study

1.2 Contributions and Techniques for Ulam Metric $k$ -Center

Theorem 1 ( $\star$ ).

Theorem 3 ( $\star$ ).

1.3 Contributions and Techniques for Ulam Metric $k$ -Median

Theorem 4 ( $\star$ ).

Theorem 6 ( $\star$ ).

3 The Complexity of Ulam Metric $k$ -Center

3.1 Lower Bound for Constant Radius $𝒅$

Theorem 1 ( $\star$ ). [Restated, see original statement.]

3.2 Fixed-Parameter Tractability by $k+d$

Definition 8 ( $d$ -fitting coloring and witness).

Definition 12 (Consistent $d$ -fitting colorings).

Theorem 3 ( $\star$ ). [Restated, see original statement.]

4 The Complexity of Ulam Metric $𝒌$ -Median

Theorem 4 ( $\star$ ). [Restated, see original statement.]