\documentclass[11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[a4paper,margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{enumitem}
\usepackage{microtype}
\usepackage{hyperref}
\hypersetup{
  hidelinks,
  pdftitle={Ulam Metric k-Center in Parameterized Linear Time},
  pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},
  pdfsubject={Parameterized algorithms and radius lower bounds for continuous Ulam Metric k-Center},
  pdfkeywords={Ulam distance, rank aggregation, parameterized algorithms, closest string}
}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}


\newcommand{\distU}{\operatorname{dist}_{\mathrm U}}
\newcommand{\pos}{\operatorname{pos}}
\newcommand{\vc}{\tau}
\newcommand{\lcs}{\operatorname{LCS}}
\newcommand{\restr}[2]{#1|_{#2}}

\title{Ulam Metric \(k\)-Center in Parameterized Linear Time\thanks{This work was produced within the Bolzano project (\url{https://bolzano.app}), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking.}}
\author{Mat\v{e}j Kripner \qquad V\'{a}clav Rozho\v{n} \qquad Robert \v{S}\'{a}mal\\[0.4em]
Martin \v{S}indel\'{a}\v{r} \qquad Adri\'{a}n Z\'{a}me\v{c}n\'{i}k}
\date{}


\usepackage{xcolor}

% Collection typography.
\geometry{a4paper,hmargin=23mm,vmargin=25mm}
\definecolor{BolzanoInk}{HTML}{24445C}
\hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk,
  urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}}
\urlstyle{same}
\setlength{\emergencystretch}{1em}
\let\BolzanoBibliography\thebibliography
\renewcommand{\thebibliography}[1]{\BolzanoBibliography{#1}\raggedright}
\begin{document}
\maketitle

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

\section{Introduction}
\subsection{Background and the source problem}

A consensus ranking should remain close to the rankings it summarizes.
Data with several distinct groups may require several centers. Ulam distance measures
how many symbols must be moved while the other symbols retain their
relative order. The radius is a useful parameter when each ranking disagrees with its
group's consensus on only a few items. For example, moving the symbol \(3\) in
\(12345\) gives \(13245\), so these rankings have Ulam distance one.

Let \(m,n\ge1\) and let \(\Sigma\) be an \(n\)-symbol alphabet. For permutations \(\pi,\sigma\) of
\(\Sigma\), define
\[
 \distU(\pi,\sigma)=n-\lcs(\pi,\sigma),
\]
where \(\lcs\) denotes longest common subsequence length. Given
\(m\) input permutations \(\pi_1,\ldots,\pi_m\) and integers \(k\ge1\),
\(d\ge0\), continuous \textsc{Ulam Metric \(k\)-Center} asks for at most
\(k\) permutations \(\sigma_1,\ldots,\sigma_k\) such that
\[
 \max_{1\le i\le m}\min_{1\le j\le k}\distU(\pi_i,\sigma_j)\le d.
\]
The centers may be arbitrary permutations; they need not be inputs.
This is the convention of Bai, Fomin, Golovach, More, and
Wietheger~\cite[Section~1.1]{BaiFominGolovachMoreWietheger2026}.

Bai et al. prove NP-hardness even for \(d=1\) when \(k\) is part of the
input, and give an exact algorithm in time
\[
 2^{O(d^2k(d+k))}mn^{1+o(1)}
\]
\cite[Theorems~1 and~2]{BaiFominGolovachMoreWietheger2026}.
For one center, the parameter dependence is \(2^{O(d^3)}\).
By comparison, the Hamming-distance consensus problem \textsc{Closest
String} has \(d^{O(d)}\) dependence over arbitrary alphabets, by the
bounded-search-tree algorithm of Gramm, Niedermeier, and
Rossmanith~\cite[Theorem~1]{GrammNiedermeierRossmanith2003}.
Bai et al. ask whether the Ulam problem has the same dependence
\cite[Section~5, p.~19:21]{BaiFominGolovachMoreWietheger2026}.

\begin{question}[Bai--Fomin--Golovach--More--Wietheger]\label{question:source}
Can continuous \textsc{Ulam Metric 1-Center} be solved in time
\(d^{O(d)}(mn)^{O(1)}\)?
\end{question}

\subsection{Contribution}

\begin{theorem}\label{thm:main}
For \(k,d\ge1\), continuous \textup{\textsc{Ulam Metric \(k\)-Center}} can
be decided deterministically in
\begin{equation}\label{eq:main-time}
 2^{O(kd\log(k+d+2))}mn
\end{equation}
word operations, and a set of centers can be returned on every yes-instance.
The permutations are given explicitly as arrays of symbols in \([n]\);
a word holds an input address or a symbol.
\end{theorem}

For \(k=1\), this is \(2^{O(d\log(d+2))}mn\), answering
Question~\ref{question:source} while retaining linear dependence on the
explicit input size. The boundary case \(d=0\) amounts to counting distinct
input permutations and can be solved by direct comparisons to at most
\(k+1\) representatives in \(O(kmn)\) time.

The radius dependence for one center is also optimal in the following
standard conditional sense.
\begin{theorem}\label{thm:lower}
Unless the Exponential Time Hypothesis fails, continuous
\textup{\textsc{Ulam Metric 1-Center}} has no algorithm with running time
\(2^{o(d\log d)}(mn)^{O(1)}\).
\end{theorem}
Theorem~\ref{thm:lower} does not assert optimal dependence on \(k\).
The lower-bound statement was already made in the conclusion of
Bai et al.; Section~\ref{sec:lower} supplies an arbitrary-alphabet reduction
that justifies its use of the \textsc{Closest String} lower bound.

The main obstacle to the algorithm is that a radius-\(d\) ball can contain
\(n^{\Omega(d)}\) permutations. Guessing the moved symbols and their new
positions would put the parameter in the exponent of the input size.
Three ingredients avoid that enumeration.
\begin{enumerate}[label=\arabic*.,leftmargin=2.2em]
\item A failed candidate has an obstruction on at most \(2d+2\) symbols.
Stopping patience sorting after \(d+1\) replacements produces this
obstruction within \(O(n+(d+1)\log(n+1))\) operations
(Lemma~\ref{lem:threshold}).
\item Relative to a fixed reference ranking, a symbol has at most \(4d+2\)
relevant insertion cuts. Canonical cuts ensure that partial placements
continue to agree with one fixed solution outside the still unguessed
moved symbols (Lemmas~\ref{lem:small-cut-lists}--\ref{lem:reconstruction}).
\item Each center keeps its own permanent reference. An uncovered input
either supplies a reference for a new cluster or exposes a new moved
symbol for an existing center. At most \(k\) references and \(kd\) moved
symbols are introduced (Section~\ref{sec:search-tree}).
\end{enumerate}

The source already uses a search that creates candidate centers from
uncovered inputs. Its local steps use permutation graphs, short lists of
one-symbol moves, and suitable two-colorings; the full version constructs
a coloring family of size \(2^{O(d^2)}\log n\)
\cite[Lemmas~11, 13, 16 and Algorithm~1]{BaiFominGolovachMoreWietheger2026Full}.
Here the references remain fixed while partial placements accumulate.
A small obstruction selects a new symbol directly, avoiding the coloring
family. The compatibility argument preserves the association of each
reference with a distinct true cluster, so the input partition need not be
guessed. Intermediate candidates need not cover the same inputs at every
stage; the final coverage test certifies the solution.

The linear input factor uses only a threshold version of the classical
patience-sorting algorithm, not a faster unrestricted longest-increasing-
subsequence algorithm. Almost all scanned symbols extend the list of pile
tops in constant time; only \(d+1\) operations can require binary search
before either success or an obstruction is known.

\subsection{Related work}
Bachmaier, Brandenburg, Glei\ss ner, and Hofmeier proved NP-completeness of
maximum rank aggregation under Ulam distance, among other metrics
\cite[Theorem~3]{BachmaierBrandenburgGleissnerHofmeier2015}. Their
bounded-modification-set framework also gives fixed-parameter algorithms
for Kendall tau, Hamming, and Minkowski distances; Ulam distance is not
among those algorithmic instantiations
\cite[Section~6]{BachmaierBrandenburgGleissnerHofmeier2015}. Choosing an
input permutation gives the familiar factor-\(2\) metric approximation.
For \(m\) input rankings, Chakraborty, Gajjar, and Jha obtain a deterministic
\((3/2-1/(3m))\)-approximation in time \(n^{O(m^2\log m)}\)
\cite[Theorem~1]{ChakrabortyGajjarJha2021}. More recently, Azgor,
Chakraborty, Cuong, Das, Habib, and Nguyen prove that, for each
\(0<\varepsilon<1/34\), approximating the continuous center within
\(35/34-\varepsilon\) is NP-hard even for four rankings
\cite[Theorem~1.3]{AzgorEtAl2026}. This rules out polynomial-time exact
optimization for fixed \(m=4\), unless P equals NP; it is compatible with
an exact algorithm parameterized by the radius.

The \emph{discrete} center problem restricts the center to an input
permutation. Abboud, Bateni, Cohen-Addad, Karthik C.~S., and Seddighin
study its fine-grained complexity and give a \((1+\varepsilon)\)-approximation
\cite[Theorems~1 and~3]{AbboudEtAl2023}. Fischer, Goldenberg, Habib, and
Karthik C.~S. subsequently establish conditional optimality, up to
subpolynomial factors, of the pairwise-distance algorithm when the
permutation length is polynomially related to the number of inputs
\cite[Theorem~2]{FischerEtAl2025}. Those results concern a different
solution space and polynomial input-size dependence, rather than the
radius dependence of the continuous problem considered here.


The lower-bound comparison requires attention to the alphabet.
Lokshtanov, Marx, and Saurabh exclude \(2^{o(d\log d)}\) dependence for
\textsc{Closest String} over unrestricted alphabets
\cite[Theorem~3.1]{LokshtanovMarxSaurabh2018}. The proof of Lemma~18 in
Bai et al.'s full version uses a binary pair encoding
\cite[Section~3.3]{BaiFominGolovachMoreWietheger2026Full}. Fixed-alphabet
\textsc{Closest String} has single-exponential algorithms
\cite[Section~3]{LokshtanovMarxSaurabh2018}; for the binary case, Fischer
and Habib give a randomized \(O^*(4^d)\)-time algorithm
\cite[Theorem~1]{FischerHabib2026}. Thus the binary encoding alone does not
transfer the unrestricted-alphabet lower bound. The marker construction
in Section~\ref{sec:lower} handles any alphabet size and projects arbitrary
permutation centers back to strings without increasing distances. It
therefore completes the lower-bound argument anticipated in the source.

\section{Deletion witnesses and small obstructions}

For \(S\subseteq\Sigma\), write \(\pi|_S\) for the subsequence induced by
\(S\). A \emph{deletion witness} between \(\alpha\) and \(\beta\) is a set
\(D\subseteq\Sigma\) such that
\[
 \alpha|_{\Sigma\setminus D}=\beta|_{\Sigma\setminus D}.
\]
Equivalently, \(\distU(\alpha,\beta)\le d\) if and only if such a witness
of size at most \(d\) exists. In particular, a reference ranking \(\rho\)
within distance \(d\) of a center \(\sigma^\star\) agrees with that center
outside some set \(X\) of at most \(d\) symbols. No uniqueness of \(X\) is
assumed.

The following algorithm gives both the distance test and the obstruction
needed for branching. The elementary patience-sorting principle is
classical; see Aldous and Diaconis~\cite{AldousDiaconis1999}.

\begin{lemma}[Threshold test and obstruction]\label{lem:threshold}
Given permutations \(\alpha,\beta\), the inverse-position array of \(\beta\),
and \(d\ge0\), one can either certify \(\distU(\alpha,\beta)\le d\) or find
\(H\subseteq\Sigma\) such that
\begin{equation}\label{eq:obstruction}
 |H|\le2d+2,
 \qquad
 \distU(\alpha|_H,\beta|_H)>d.
\end{equation}
This takes \(O(n+(d+1)\log(n+1))\) operations and \(O(n)\) memory.
\end{lemma}

\begin{proof}
Read the symbols of \(\alpha\) and replace each by its position in \(\beta\).
A common subsequence of the permutations is exactly an increasing
subsequence of this sequence of distinct ranks. Maintain piles whose
tops \(t_1<\cdots<t_\ell\) are increasing. A new rank \(r>t_\ell\)
starts a new pile on the right; otherwise place \(r\) on the leftmost pile
whose top exceeds \(r\). Call the latter operation a replacement.
For an empty list, the first rank starts the first pile.

After any prefix, \(t_j\) is the smallest possible final rank of an
increasing subsequence of length \(j\). To verify the invariant, suppose
\(r\) replaces \(t_j\). If \(j>1\), an increasing subsequence ending at
\(t_{j-1}<r\) extends to one of length \(j\) ending at \(r\); for \(j=1\)
the singleton suffices. There was no subsequence of length \(j\) ending
below \(r\), by the minimality of the old \(t_j\). Nor can \(r\) end a
subsequence of length greater than \(j\), since that would require an old
subsequence of length \(j\) ending below \(r\). The other minima are
unchanged. If \(r\) starts a new rightmost pile, the same extension gives
a subsequence of length \(\ell+1\), and no longer one can be created by
one new rank. This proves the invariant by induction. Thus \(\ell\) is
the longest increasing subsequence length of the scanned prefix.

After \(i\) ranks, the number of replacements is \(i-\ell\), because every
other operation starts one pile. This deficit never decreases. Stop at
the \((d+1)\)-st replacement. If the whole sequence is scanned first,
its deficit is the Ulam distance, so the test succeeds.

On stopping, let \(P_1,\ldots,P_t\) be the non-singleton piles and let \(H\)
contain their symbols. Each pile is decreasing in scan order, so an
increasing subsequence of \(H\) contains at most one symbol from each pile.
Moreover,
\[
 \sum_{j=1}^t(|P_j|-1)=d+1,
 \qquad t\le d+1.
\]
Consequently \(|H|=d+1+t\le2d+2\) and its longest increasing subsequence
has length at most \(t\), proving~\eqref{eq:obstruction}.

Compare each rank first with the rightmost top. Appending costs constant
time, and a replacement uses binary search in \(O(\log(n+1))\) time.
There are at most \(d+1\) replacements. Store the symbols of each pile,
and keep a list of the piles that have become non-singleton; their union
can then be collected in \(O(d+1)\) time. The claimed bounds follow.
\end{proof}

\section{Small cut lists}

Fix an arbitrary reference permutation \(\rho\). A cut of the reference permutation \(\rho\) is an integer \(c\in\{0,1,
\ldots,n\}\); it is the gap after the first \(c\) symbols of \(\rho\). For a symbol \(x\) and a cut \(c\), define
\[
        P_c^x=\{a\in\Sigma\setminus\{x\}: \pos_\rho(a)\le c\}.
\]
For an input permutation \(\pi_i\), define the predecessor set of \(x\) in \(\pi_i\) by
\[
        L_i(x)=\{a\in\Sigma\setminus\{x\}: a \text{ is before } x \text{ in } \pi_i\}.
\]
Define the cut list
\[
        S_i(x)=\{c\in\{0,
\ldots,n\}: |P_c^x\triangle L_i(x)|\le 2d\}.
\]
The key point is that, although there are \(n+1\) possible cuts, only \(O(d)\) of them can be relevant for any fixed input and symbol.

\begin{lemma}[Small cut lists]\label{lem:small-cut-lists}
For every input \(\pi_i\) and every symbol \(x\),
\[
        |S_i(x)|\le 4d+2.
\]
\end{lemma}

\begin{proof}
Put \(\ell=|L_i(x)|\) and \(h(c)=|P_c^x|\). For every listed cut,
\[
 |h(c)-\ell|\le |P_c^x\triangle L_i(x)|\le2d.
\]
Thus \(h(c)\) lies in an interval containing at most \(4d+1\) integers.
As \(c\) ranges from \(0\) to \(n\), the value \(h(c)\) runs through
\(0,\ldots,n-1\). Each value occurs once except
\(\pos_\rho(x)-1\), which occurs twice, immediately before and after
the reference position of \(x\). Consequently
\[
 |S_i(x)|\le4d+2.
\]
For computation, begin with \( |P_0^x\triangle L_i(x)|=|L_i(x)|\)
and scan \(\rho\). Passing a symbol of \(L_i(x)\) decreases the value by
one, passing a symbol outside \(L_i(x)\cup\{x\}\) increases it by one,
and passing \(x\) leaves it unchanged. The inverse-position array of
\(\pi_i\) gives membership in \(L_i(x)\) in constant time. Thus the list
can be computed in \(O(n)\) time, without any assumption on
\(\distU(\rho,\pi_i)\).
\end{proof}

Now fix a permutation \(\sigma^\star\) with \(\distU(\rho,\sigma^\star)\le d\), a deletion witness \(X\) of size at most \(d\) between them, and put \(R=\Sigma\setminus X\). For \(x\in X\), let
\[
        B_x=\{a\in R: a \text{ is before } x \text{ in } \sigma^\star\}.
\]
Because \(\sigma^\star|_R=\rho|_R\), the set \(B_x\) is a prefix of \(\rho|_R\). Define the \emph{canonical cut} of \(x\) by
\begin{equation}\label{eq:canonical-cut}
        c_x=
        \begin{cases}
                0, & B_x=\emptyset,\\[1mm]
                \max\{\pos_\rho(a):a\in B_x\}, & B_x\ne\emptyset.
        \end{cases}
\end{equation}
Then \(P_{c_x}^x\cap R=B_x\). In particular, the exact definition~\eqref{eq:canonical-cut} assigns the same cut to all moved symbols occupying the same gap of the stable order \(R\).

\begin{lemma}[Canonical cuts are listed]\label{lem:canonical-cut-listed}
Let \(\sigma^\star\) and \(X\) be as above, and let \(x\in X\). Let \(D_i\) be a deletion witness of size at most \(d\) between \(\sigma^\star\) and \(\pi_i\). If \(x\notin D_i\), then the canonical cut \(c_x\) belongs to \(S_i(x)\).
\end{lemma}

\begin{proof}
Consider a symbol \(a\in\Sigma\setminus(X\cup D_i)\). Since \(a\in R\), the definition of the canonical cut gives \(a\in P_{c_x}^x\) if and only if \(a\in B_x\), which means that \(a\) precedes \(x\) in \(\sigma^\star\). Also \(a,x\notin D_i\), so \(\sigma^\star\) and \(\pi_i\) order \(a\) and \(x\) in the same way. Therefore
\[
        a\in P_{c_x}^x
        \quad\Longleftrightarrow\quad
        a\in B_x
        \quad\Longleftrightarrow\quad
        a\in L_i(x).
\]
All possible disagreements between \(P_{c_x}^x\) and \(L_i(x)\) are therefore contained in \(X\cup D_i\). Neither predecessor set contains \(x\), so the disagreements are in \((X\setminus\{x\})\cup D_i\), a set of size at most \(2d\). Hence \(|P_{c_x}^x\triangle L_i(x)|\le 2d\), so \(c_x\in S_i(x)\).
\end{proof}

\paragraph{Example.}
Let \(\rho=12345\), let \(\pi_i=13245\), and take \(d=1\). For the symbol \(x=3\), the predecessor set in \(\pi_i\) is \(L_i(3)=\{1\}\). Direct inspection gives
\[
        S_i(3)=\{0,1,2,3,4\};
\]
cut \(5\) is excluded because its predecessor set \(\{1,2,4,5\}\) differs from \(L_i(3)\) in three symbols. The permutation \(\sigma^\star=13245\) has reference-deletion set \(X=\{3\}\), and the canonical cut of \(3\) is cut \(1\), immediately after the symbol \(1\). Thus the cut needed by this permutation is indeed present in the local list, as Lemma~\ref{lem:canonical-cut-listed} guarantees in general.

We next formalize partial placements. A state consists of
\[
        (A,\gamma,\lambda),
\]
where \(A\subseteq\Sigma\), \(|A|\le d\), is a set of symbols guessed to be moved relative to \(\rho\), \(\gamma:A\to\{0,\ldots,n\}\) assigns a full-reference cut to every guessed symbol, and \(\lambda\) is a total order of \(A\). The candidate permutation \(\sigma_A\) is obtained by deleting every symbol of \(A\) from \(\rho\) and reinserting each \(x\in A\) at cut \(\gamma(x)\): smaller numerical cuts come first, and equal cuts are ordered according to \(\lambda\). Formally, write \(\lambda(x)\) for the rank of \(x\) in \(\lambda\), note that \(\pos_\rho(z)\in\{1,\ldots,n\}\), and sort all symbols lexicographically by
\[
        \kappa_A(z)=
        \begin{cases}
                (\pos_\rho(z),0,0), & z\notin A,\\
                (\gamma(z),1,\lambda(z)), & z\in A.
        \end{cases}
\]
This lexicographic definition remains unambiguous when a cut endpoint is itself a symbol of \(A\) deleted from the reference.

\begin{lemma}[Reconstruction of compatible states]\label{lem:reconstruction}
Let \(\lambda^\star\) be the order induced by \(\sigma^\star\) on \(X\). Suppose that \(A\subseteq X\), that \(\gamma(x)=c_x\) for every \(x\in A\), and that \(\lambda=\lambda^\star|_A\). Put \(U=X\setminus A\). Then
\begin{equation}\label{eq:compat-invariant}
        \sigma_A|_{\Sigma\setminus U}
        =
        \sigma^\star|_{\Sigma\setminus U}.
\end{equation}
\end{lemma}

\begin{proof}
Set \(R=\Sigma\setminus X\), so that \(\Sigma\setminus U=R\cup A\). Both permutations induce the order \(\rho|_R\) on \(R\).

Let \(x\in A\) and \(r\in R\). In \(\sigma_A\), the symbol \(r\) precedes \(x\) if and only if \(\pos_\rho(r)\le c_x\), equivalently \(r\in B_x\). By the definition of \(B_x\), this is also equivalent to \(r\) preceding \(x\) in \(\sigma^\star\).

It remains to compare two symbols \(x,y\in A\). The sets \(B_x\) and \(B_y\) are prefixes of the same order. If \(B_x\subsetneq B_y\), then the definition~\eqref{eq:canonical-cut} gives \(c_x<c_y\), so \(x\) precedes \(y\) in \(\sigma_A\). Choosing \(r\in B_y\setminus B_x\) also gives \(x<r<y\) in \(\sigma^\star\). The case \(B_y\subsetneq B_x\) is symmetric. Finally, if \(B_x=B_y\), then \(c_x=c_y\), and both permutations order \(x,y\) according to \(\lambda^\star|_A=\lambda\). Thus every pair in \(R\cup A\) has the same relative order in the two permutations, proving~\eqref{eq:compat-invariant}.
\end{proof}


The reconstruction can be implemented without sorting all \(n\) symbols.
Sort the at most \(d\) moved symbols by \((\gamma(x),\lambda(x))\), then
scan the cuts \(0,\ldots,n\). At a positive cut \(c\), first output the
reference symbol in position \(c\) if it is not moved; next output the
moved symbols assigned to cut \(c\) in their prescribed order. At cut zero
only the moved symbols are output. This realizes the lexicographic keys
above in \(O(n+d\log(d+1))\) time.

\section{The search over several centers}\label{sec:search-tree}

A search node contains \(s\le k\) records
\[
 (\rho_j,A_j,\gamma_j,\lambda_j),\qquad 1\le j\le s.
\]
Each reference \(\rho_j\) is an input permutation and remains fixed for the
lifetime of its record. The other data are a partial placement relative to
that reference, with \(|A_j|\le d\); denote its reconstructed candidate by
\(\sigma_j\). Initially there is one record with \(\rho_1=\pi_1\) and
\(A_1=\emptyset\).

At a node, perform the following steps.
\begin{enumerate}[leftmargin=2.2em]
\item Construct the candidates. If every input is within distance \(d\)
of some candidate, return these candidates and accept.
\item Otherwise choose an uncovered input \(\pi_i\). If \(s<k\), create
one child that adds the record \((\pi_i,\emptyset,\emptyset,\emptyset)\).
\item For each existing record \(j\) with \(|A_j|<d\), use
Lemma~\ref{lem:threshold} to find an obstruction \(H_j\) between
\(\sigma_j\) and \(\pi_i\). For each \(x\in H_j\setminus A_j\), each
\(c\in S_i^{(j)}(x)\), and each of the \(|A_j|+1\) insertion positions in
\(\lambda_j\), create a child that adds \(x\) with this cut and order
position to record \(j\). Here \(S_i^{(j)}\) is the cut list computed
relative to \(\rho_j\). Keep all other records and all earlier placements
unchanged.
\item Reject if every child rejects.
\end{enumerate}
The algorithm does not reject an instance merely because two inputs are
farther than \(2d\) apart: they may be covered by different centers.

\begin{proof}[Proof of Theorem~\ref{thm:main}]
If \(k\ge m\), the inputs themselves are a solution. If \(d\ge n-1\), any
input is a center. Hence assume \(1\le k<m\) and \(1\le d<n-1\).
Soundness follows from the coverage test at every accepting node.

For completeness, fix a feasible set of at most \(k\) true centers and
assign each input to one true center that covers it. Empty clusters can
be omitted. A compatible node associates its records injectively with
true centers, with each reference belonging to its associated cluster.
Write \(\sigma_j^\star\) for the center associated with record \(j\).
When a record is created, fix a deletion witness \(X_j\), \(|X_j|\le d\),
between \(\rho_j\) and \(\sigma_j^\star\). Compatibility further requires
\[
 A_j\subseteq X_j,\qquad
 \gamma_j(x)=c_x^{(j)}\quad(x\in A_j),\qquad
 \lambda_j=\sigma_j^\star|_{A_j},
\]
where \(c_x^{(j)}\) is the canonical cut defined using \(\rho_j,X_j\), and
the last equality identifies a total order with its ordered sequence.
Lemma~\ref{lem:reconstruction} gives, with \(U_j=X_j\setminus A_j\),
\begin{equation}\label{eq:multi-invariant}
 \sigma_j|_{\Sigma\setminus U_j}
 =\sigma_j^\star|_{\Sigma\setminus U_j}.
\end{equation}
The initial node is compatible by associating its sole record with the
true center assigned to \(\pi_1\).

Consider an uncovered input \(\pi_i\) at a compatible node. If its assigned
true center is not represented by a record, there are fewer records than
true centers and hence \(s<k\). The new-record child is compatible: associate
it with that true center and choose its witness \(X_{s+1}\). Its moved set
is empty, so every placement condition is satisfied.

Otherwise let \(j\) be the record associated with the assigned true center.
Choose a deletion witness \(D\), \(|D|\le d\), between \(\pi_i\) and
\(\sigma_j^\star\). Since \(\pi_i\) is uncovered, the obstruction \(H_j\)
satisfies~\eqref{eq:obstruction}. It contains a symbol in \(U_j\setminus D\).
Indeed, if it contained no such symbol, then \(H_j\setminus D\) would be
disjoint from \(U_j\). Equation~\eqref{eq:multi-invariant} and the witness
property of \(D\) would give
\[
 \sigma_j|_{H_j\setminus D}
 =\sigma_j^\star|_{H_j\setminus D}
 =\pi_i|_{H_j\setminus D}.
\]
Deleting \(H_j\cap D\), at most \(d\) symbols, would therefore make the
restricted permutations equal, contradicting~\eqref{eq:obstruction}.

Choose \(x\in H_j\cap(U_j\setminus D)\). In particular,
\(|A_j|<|X_j|\le d\), so this record is eligible for extension. The symbol
is moved relative to its reference and is kept by the witness \(D\).
Lemma~\ref{lem:canonical-cut-listed} places its canonical cut in
\(S_i^{(j)}(x)\). The algorithm includes the child selecting this cut and
the insertion position that extends the current order to
\(\sigma_j^\star|_{A_j\cup\{x\}}\). This child is compatible.

Thus every compatible nonaccepting node has a compatible child. Each
transition either adds a record or increases one moved set. There are at
most \(k-1\) record additions and \(kd\) moved-symbol additions, so no
path has more than \(k(d+1)-1\) transitions. A compatible path must
therefore accept. This proves completeness without any assumption that
coverage is monotone along the path.

There is at most one new-record child, and the extension of each record
has at most \((2d+2)(4d+2)(d+1)\) choices. The branching factor is at most
\[
 b=1+k(2d+2)(4d+2)(d+1).
\]
The depth bound gives \(1+b+\cdots+b^{k(d+1)}\) nodes. Since \(d\ge1\),
this is \(2^{O(kd\log(k+d+2))}\).

Precompute the inverse-position arrays of all inputs in \(O(mn)\) time.
At a node, reconstructing all candidates costs
\(O(k(n+d\log(d+1)))\). Coverage testing uses at most \(km\) applications
of Lemma~\ref{lem:threshold}. For the uncovered input, the same routine
provides each required obstruction. There are \(O(k(d+1))\) relevant
symbols, and each cut list takes \(O(n)\) time. These costs are bounded by
a polynomial in \(k,d\) times \(mn\), using
\(\log(n+1)=O(n)\). Creating or copying a child record adds only a
polynomial factor in \(k,d\), already absorbed in the search bound.
This proves~\eqref{eq:main-time} in the stated word model.
\end{proof}

\section{Hamming retractions and the radius lower bound}\label{sec:lower}

An isometric encoding alone would not suffice for the lower bound:
a permutation center outside the encoded strings could conceivably have
a smaller radius. The following construction provides a simultaneous
projection for all inputs.
Write \(d_{\mathrm H}\) for Hamming distance.

\begin{lemma}[Arbitrary-alphabet retraction]\label{lem:retract}
For every \(q\ge2\) and \(L\ge1\), there are maps
\[
 E:\{0,\ldots,q-1\}^L\longrightarrow S_{Lq},
 \qquad
 r:S_{Lq}\longrightarrow\{0,\ldots,q-1\}^L
\]
computable in polynomial time such that \(r\circ E\) is the identity and
\begin{align}
 \distU(E(s),E(t))&=d_{\mathrm H}(s,t),\label{eq:isometry}\\
 d_{\mathrm H}(r(\alpha),r(\beta))&\le\distU(\alpha,\beta)
 \qquad(\alpha,\beta\in S_{Lq}).\label{eq:retract}
\end{align}
Consequently, replacing each input string by its encoding preserves the
optimal radius with any prescribed number of arbitrary centers.
\end{lemma}

\begin{proof}
For coordinate \(i\), use a disjoint block of symbols
\(B_i=\{z_i,a_{i,1},\ldots,a_{i,q-1}\}\). Define
\[
 C_i(b)=a_{i,1}\cdots a_{i,b}\,z_i\,
         a_{i,b+1}\cdots a_{i,q-1}
 \qquad(0\le b<q),
\]
with an empty initial or final anchor string at the endpoints. Distinct
values of \(b\) give distinct block permutations that share all \(q-1\)
anchors in order. Thus their Ulam distance is one. Set
\[
 E(s)=C_1(s_1)C_2(s_2)\cdots C_L(s_L).
\]
Both encodings place the disjoint blocks in the same order, so their
longest common subsequence lengths add over the blocks. This proves
\eqref{eq:isometry}.

For an arbitrary permutation \(\alpha\), restrict it to each block \(B_i\).
If \(\alpha|_{B_i}=C_i(b)\) for some \(b\), put \(r(\alpha)_i=b\);
otherwise put \(r(\alpha)_i=0\). The canonical block permutations are
distinct, so this is well-defined and \(r(E(s))=s\).
If \(r(\alpha)_i\ne r(\beta)_i\), then the two block restrictions differ,
since equal restrictions receive equal decoded letters. Their Ulam
distance, being a nonnegative integer, is at least one. Therefore
\[
 d_{\mathrm H}(r(\alpha),r(\beta))
 \le \sum_{i=1}^L
 \distU(\alpha|_{B_i},\beta|_{B_i}).
\]
Any common subsequence of \(\alpha,\beta\), restricted to \(B_i\), is a
common subsequence of their block restrictions. Summing these upper
bounds on the subsequence length and subtracting from \(Lq\) gives
\[
 \sum_{i=1}^L\distU(\alpha|_{B_i},\beta|_{B_i})
 \le \distU(\alpha,\beta),
\]
which proves~\eqref{eq:retract}.

An encoded family of string centers achieves the same radius by
\eqref{eq:isometry}. Conversely, decode each arbitrary permutation
center. For every input string \(t\), applying~\eqref{eq:retract} with
\(\beta=E(t)\) shows that its distance to the decoded center is no greater
than its encoded distance to the original center. This works for every
input and every center simultaneously, proving equality of optimal radii.
\end{proof}

For example, when \(q=3\) the three letters are represented by
\(z_i a_{i,1}a_{i,2}\), \(a_{i,1}z_i a_{i,2}\), and
\(a_{i,1}a_{i,2}z_i\). The marker moves while the two anchors retain their
order. A noncanonical order such as \(a_{i,2}z_i a_{i,1}\) may be decoded
as zero: it differs from every canonical order, so the possible unit
Hamming cost is always paid for by its Ulam distance.

\begin{proof}[Proof of Theorem~\ref{thm:lower}]
Lokshtanov, Marx, and Saurabh prove that \textsc{Closest String} has no
\(2^{o(d\log d)}|I|^{O(1)}\)-time algorithm under ETH
\cite[Theorem~3.1]{LokshtanovMarxSaurabh2018}. In their construction from
\(h\times h\) \textsc{Hitting Set}, the strings have length \(L=h\),
alphabet size \(q=2h+1\), and radius \(d=h-1\). Applying
Lemma~\ref{lem:retract} yields permutations of
\[
 n=Lq=(d+1)(2d+3)
\]
symbols, with the same number of inputs and the same radius. The expansion
is polynomial, and the lemma gives equivalence even when the permutation
center is unrestricted. A Ulam algorithm in the excluded time would
therefore solve these \textsc{Closest String} instances in the time
excluded by the cited theorem.
\end{proof}

\section{Concluding remarks}

For one center, the upper and lower bounds determine the radius dependence
up to constant factors in the exponent under ETH, with a linear factor in
the explicit input size for the upper bound. For several centers, the
remaining question is the best joint dependence on \(k\) and \(d\).
The present argument bounds the number of introduced references and
moved symbols separately; the one-center lower bound alone does not
settle the cost of coordinating many clusters.

{\small
\begin{thebibliography}{99}

\bibitem{BaiFominGolovachMoreWietheger2026}
Tian Bai, Fedor V.~Fomin, Petr A.~Golovach, Yash Hiren More, and Simon Wietheger.
\newblock Clustering permutations under the Ulam metric: A parameterized complexity study.
\newblock In Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis, editors, \emph{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)}, volume 374 of \emph{Leibniz International Proceedings in Informatics (LIPIcs)}, Article~19, pages 19:1--19:23. Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik, 2026.
\newblock \url{https://doi.org/10.4230/LIPIcs.ICALP.2026.19}.

\bibitem{BaiFominGolovachMoreWietheger2026Full}
Tian Bai, Fedor V.~Fomin, Petr A.~Golovach, Yash Hiren More, and Simon Wietheger.
\newblock Clustering permutations under the Ulam metric: A parameterized complexity study.
\newblock Full version of the ICALP 2026 paper, \emph{arXiv:2604.25734v1 [cs.DS]}, 2026.
\newblock \url{https://arxiv.org/abs/2604.25734}.

\bibitem{BachmaierBrandenburgGleissnerHofmeier2015}
Christian Bachmaier, Franz J.~Brandenburg, Andreas Glei{\ss}ner, and Andreas Hofmeier.
\newblock On the hardness of maximum rank aggregation problems.
\newblock \emph{Journal of Discrete Algorithms}, 31:2--13, 2015.
\newblock \url{https://doi.org/10.1016/j.jda.2014.10.002}.

\bibitem{ChakrabortyGajjarJha2021}
Diptarka Chakraborty, Kshitij Gajjar, and Agastya Vibhuti Jha.
\newblock Approximating the center ranking under Ulam.
\newblock In \emph{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, volume 213 of \emph{LIPIcs}, Article~12, pages 12:1--12:21, 2021.
\newblock \url{https://doi.org/10.4230/LIPIcs.FSTTCS.2021.12}.

\bibitem{AldousDiaconis1999}
David Aldous and Persi Diaconis.
\newblock Longest increasing subsequences: From patience sorting to the Baik--Deift--Johansson theorem.
\newblock \emph{Bulletin of the American Mathematical Society}, 36(4):413--432, 1999.
\newblock \url{https://doi.org/10.1090/S0273-0979-99-00796-X}.

\bibitem{FischerHabib2026}
Nick Fischer and Mursalin Habib.
\newblock An optimal algorithm for binary closest string.
\newblock \emph{arXiv:2605.31417v1 [cs.DS]}, 2026.
\newblock \url{https://arxiv.org/abs/2605.31417}.

\bibitem{GrammNiedermeierRossmanith2003}
Jens Gramm, Rolf Niedermeier, and Peter Rossmanith.
\newblock Fixed-parameter algorithms for \textsc{Closest String} and related problems.
\newblock \emph{Algorithmica}, 37(1):25--42, 2003.
\newblock \url{https://doi.org/10.1007/s00453-003-1028-3}.

\bibitem{LokshtanovMarxSaurabh2018}
Daniel Lokshtanov, D{\'a}niel Marx, and Saket Saurabh.
\newblock Slightly superexponential parameterized problems.
\newblock \emph{SIAM Journal on Computing}, 47(3):675--702, 2018.
\newblock \url{https://doi.org/10.1137/16M1104834}.

\bibitem{AbboudEtAl2023}
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C.~S., and Saeed Seddighin.
\newblock On complexity of 1-center in various metrics.
\newblock In \emph{APPROX/RANDOM 2023}, volume 275 of \emph{LIPIcs}, Article~1, 2023.
\newblock \url{https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.1}.

\bibitem{FischerEtAl2025}
Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C.~S.
\newblock Hardness of median and center in the Ulam metric.
\newblock In \emph{ESA 2025}, volume 351 of \emph{LIPIcs}, pages 111:1--111:17, 2025.
\newblock \url{https://doi.org/10.4230/LIPIcs.ESA.2025.111}.

\bibitem{AzgorEtAl2026}
Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong, Debarati Das, Mursalin Habib, and Tien Long Nguyen.
\newblock Ulam rank aggregation is hard to approximate for four rankings.
\newblock \emph{arXiv:2609.05874v1 [cs.CC]}, September 2026.
\newblock \url{https://arxiv.org/abs/2609.05874v1}.

\end{thebibliography}
}

\end{document}