Department of Computer Science, Royal Holloway, University of London, Egham,
UKeduard.eiben@gmail.comhttps://orcid.org/0000-0003-2628-3435 Algorithms and
Complexity Group, TU Wien, Vienna,
Austriarganian@gmail.comhttps://orcid.org/0000-0002-7762-8045Project No. Y1329
of the Austrian Science Fund (FWF) School of Computing, DePaul University,
Chicago<EMAIL_ADDRESS>University of Leeds, School of Computing,
Leeds, UKsordyniak@gmail.comhttps://orcid.org/0000-0003-1935-651XProject
EP/V00252X/1 of the Engineering and Physical Sciences Research Council (EPSRC)
Algorithms and Complexity Group, TU Wien, Vienna,
Austriasz@ac.tuwien.ac.athttps://orcid.org/0000-0001-8994-1656Project No.
P32441 of the Austrian Science Fund (FWF) and Project No. ICT19-065 of the
Vienna Science and Technology Fund (WWTF) Eduard Eiben, Robert Ganian, Iyad
Kanj, Sebastian Ordyniak, Stefan Szeider [300]Theory of computation
Parameterized complexity and exact algorithms

# Finding a Cluster in Incomplete Data

Eduard Eiben  Robert Ganian  Iyad Kanj  Sebastian Ordyniak  Stefan Szeider ==

###### Abstract

We study two variants of the fundamental problem of finding a cluster in
incomplete data. In the problems under consideration, we are given a multiset
of incomplete $d$-dimensional vectors over the binary domain and integers $k$
and $r$, and the goal is to complete the missing vector entries so that the
multiset of complete vectors either contains (i) a cluster of $k$ vectors of
radius at most $r$, or (ii) a cluster of $k$ vectors of diameter at most $r$.
We give tight characterizations of the parameterized complexity of the
problems under consideration with respect to the parameters $k$, $r$, and a
third parameter that captures the missing vector entries.

###### keywords:

Parameterized complexity, incomplete data, clustering

##  1 Introduction

We consider two formulations of the fundamental problem of finding a
sufficiently large cluster in incomplete data [2, 3, 19, 25]. In the setting
under consideration, the input is a multiset $M$ of $d$-dimensional Boolean
vectors—regarded as the rows of a matrix, some of whose entries might be
missing—and two parameters $k,r\in\mathbb{N}$. In the first problem under
consideration, referred to as Diam-Cluster-Completion, the goal is to decide
whether there is a completion of $M$ that admits a multiset of $k$ vectors
($k$-cluster) of diameter at most $r$; that is, a $k$-cluster such that the
Hamming distance between any two cluster-vectors is at most $r$. In the second
problem, referred to as Rad-Cluster-Completion, the goal is to decide whether
there is a completion of $M$ that admits a $k$-cluster of radius at most $r$;
that is, a $k$-cluster such that there is a _center_ vector
$\vec{s}\in\\{0,1\\}^{d}$ with Hamming distance at most $r$ to each cluster-
vector.

The cluster-diameter and cluster-radius are among the most widely used
measures for intra-cluster similarity [5, 8, 12, 16, 17, 18, 19]. Our interest
in studying these problems stems from the recent relevant research within the
theory community [9, 15, 20, 21, 22], as well as the ubiquitous presence of
incomplete data in relevant areas, such as recommender systems, machine
learning, computer vision, and data science [1, 10, 11, 28].

We study the parameterized complexity of the above problems with respect to
the two parameters $k$, $r$, and a third parameter that captures the
occurrence of missing vector entries. Naturally, parameterizing by the number
of missing entries alone is not desirable since one would expect that number
to be rather large. In their recent related works on clustering problems,
Koana, Froese and Niedermeier [21, 22] restricted the occurrence of missing
entries by using the maximum number of missing entries per row as the
parameter. Another parameter for restricting the occurrence of missing entries
is the minimum number of vectors plus coordinates needed to “cover” all
missing entries, which was proposed and used by Eiben et al. [9] and Ganian et
al. [15], who studied various data completion and clustering problems. In this
paper, we propose and use a parameter that unifies and subsumes both previous
parameterizations: the “ _deletion distance to near-completion_ ”, denoted
$\lambda(M)$, which is the minimum integer $p$ such that at most $p$ vectors
can be removed from $M$ so that every remaining vector contains at most $p$
missing entries. Clearly, the parameter $\lambda(M)$ is computable in
polynomial time and is not larger than any of (and hence subsumes) the two
parameters considered by Koana et al. [21, 22], Eiben et al. [9], and Ganian
et al. [15].

Results and Techniques. We perform an in-depth analysis of the two considered
data completion problems w.r.t. the aforementioned parameterizations. We
obtain results that provide a nearly complete complexity landscape of these
problems. An overview of our results is provided in Table 1. As a byproduct,
our results establish that both problems under consideration are fixed-
parameter tractable parameterized by $k+r$ when the data is complete, which
answers an open question in the literature [2, 3].

| $k$ | $r$ | $k+r$ | $k+\lambda$ | $r+\lambda$ | $k+r+\lambda$
---|---|---|---|---|---|---
Diam-Cluster-C. |  W[1]-h/XP |  paraNP-c |  W[1]-h/XP |  W[1]-h/XP | FPT | FPT
Rad-Cluster-C. |  W[1]-h/XP |  paraNP-c |  W[1]-h/XP | ?/XP | ?/XP | FPT
Table 1: Overview of the results obtained in this paper.

We summarize the new results obtained in this paper below.

(1) We show that Diam-Cluster-Completion is fixed-parameter tractable (FPT)
parameterized by $r+\lambda(M)$ (Theorem 14). The significance of the above
result is in removing the dependency on the cluster size $k$ in the running
time of the algorithm, thus showing that finding a large cluster in incomplete
data can be feasible when both the cluster diameter and the parameter
$\lambda(M)$ are small. This result is the pinnacle of our technical
contributions and relies on two ingredients: a fixed-parameter algorithm for
the same problem parameterized by $k+r+\lambda(M)$ (Theorem 4), which is then
used as a subroutine in the main algorithm, and a new technique that we dub
_iterative sunflower harvesting_. Crucial to this new technique is a general
structural lemma, allowing us to represent a family of sets in a succinct
manner in terms of sunflower cores, which we believe to be interesting in its
own right. We note that the use of sunflowers to obtain a succinct set
representation (leading to a kernel) is not uncommon in such settings. For
instance, a similar set representation was also used in a previous work by
Marx [26] (see also Kratsch, Marx and Wahlström [23]) to obtain FPT and
kernelization results, albeit in the context of weighted CSPs. Koana et al.
[21, 22] also use the Sunflower Lemma in their results. What makes the
sunflower harvesting technique novel is that it allows us to (1) show that
each solution can be covered by a small number of sunflowers, and to (2)
iteratively “harvest” these sunflowers to obtain a solution in boundedly-many
(in the parameter) branching steps.

(2) We give an XP-algorithm for Diam-Cluster-Completion parameterized by $k$
alone (Theorem 15). Together with Theorem 17 (showing the W[1]-hardness of
Diam-Cluster w.r.t. $k$) and Theorem 18 (showing the W[1]-hardness for Diam-
Cluster-Completion w.r.t. $k$ even for $r=0$), this gives a complete
complexity landscape for Diam-Cluster-Completion parameterized by any
combination of the parameters $k$, $r$, and $\lambda(M)$.

(3) We show that Rad-Cluster-Completion is FPT parameterized by
$k+r+\lambda(M)$ (Theorem 21); this result answers open questions in the
literature [2, 3], which asked about the fixed-parameter tractability of the
easier complete version of the problem (i.e., when $\lambda(M)=0$).

(4) We provide an XP-algorithm for Rad-Cluster-Completion parameterized by
$r+\lambda(M)$ in which the degree of the polynomial in the runtime has only a
logarithmic dependence on $r$ (Theorem 22). We remark that the problem is in
XP parameterized by $k$ alone (Observation 19).

(5) We provide an accompanying W[1]-hardness result for Rad-Cluster-Completion
that rules out its fixed-parameter tractability when parameterized by $k+r$
(Theorem 18). Since the problem is NP-hard for fixed $r$ (as also follows from
Theorem 18), this leaves only two questions open for the considered
parameterizations: whether Rad-Cluster-Completion is FPT when parameterized by
either $k+\lambda(M)$ or by $r+\lambda(M)$.

(6) We give an FPT-approximation scheme for the optimization version (w.r.t.
the cluster size) of Rad-Cluster-Completion.

Related Work. The Rad-Cluster problem (i.e., Rad-Cluster-Completion for
complete data) and variants of it were studied as early as the 1980’s, albeit
under different names. Dyer and Frieze presented a heuristic algorithm for
approximating a variant of Rad-Cluster, referred to as the $p$-Center problem,
where the goal is to compute $p\in\mathbb{N}$ clusters, each of radius at most
$r$, that contain all vectors of $M$; hence, Rad-Cluster corresponds to the
case of $p$-Center where $p=1$ and $k=|M|$ (i.e., when the cluster contains
all vectors in $M$). Cabello et al. [4] studied the parameterized complexity
of the geometric $p$-Center Problem in $\mathbb{R}^{d}$.

Frances and Litman [14] studied the complexity of Rad-Cluster with $k=|M|$, in
the context of computing the radius of a binary code; they referred to it as
the Covering Radius problem and showed it to be NP-hard. Ga̧sieniec et al.
[16, 17] studied (the optimization versions of) Rad-Cluster and Diam-Cluster
with $k=|M|$ and obtained polynomial-time algorithms as well as lower bounds
for a number of cases. They also obtained $2$-approximation algorithms for
these problems by extending an earlier algorithm by Gonzalez [18].

The Rad-Cluster problem restricted to the subcase of $k=|M|$ was also
extensively studied under the nomenclature Closest String. Li et al. [25]
showed that the problem admits a polynomial time approximation scheme if the
goal is to minimize $r$. Gramm et al. [19] studied Closest String from the
parameterized complexity perspective and showed it to be fixed-parameter
tractable parameterized by $r$. Following this naming convention, Boucher and
Ma [2], and Bulteau and Schmid [3] studied the parameterized complexity of
Rad-Cluster under the nomenclature Closest String with Outliers. They
considered several parameters, including some of the parameters under
consideration in this paper. Notably, the restriction of our fixed-parameter
algorithm for Rad-Cluster parameterized by $k+r+\lambda$ to the subcase where
$\lambda=0$ answers an open question in [2, see, e.g., Table 1]. Moreover, our
XP algorithm for Rad-Cluster-Completion provided in Theorem 22 that has a run-
time in which the degree of the polynomial has only a logarithmic dependence
on $r$, immediately implies an algorithm of the same running time for Closest
String with Outliers, as a special case.

For incomplete data, Hermelin and Rozenberg [20] studied the parameterized
complexity of Rad-Cluster-Completion for $k=|M|$ under the nomenclature
Closest String with Wildcards problem, with respect to several
parameterizations. Very recently, Koana et al. [21] revisited the earlier work
of Hermelin and Rozenberg [20] and obtained, among other results, a fixed-
parameter algorithm for the problem parameterized by $r$ plus the maximum
number of missing entries per row. Even more recently, the same group [22]
also studied a problem related to Diam-Cluster-Completion for $k=|M|$. They
obtain a classical-complexity classification w.r.t. constant lower and upper
bounds on the diameter and the maximum number of missing entries per row.

##  2 Preliminaries

Vector Terminology. Let $\vec{a}$ and $\vec{b}$ be two vectors in
$\\{0,1,{\small\square}\\}^{d}$, where ${\small\square}$ is used to represent
coordinates whose value is unknown (i.e., missing entries). We denote by
$\Delta(\vec{a},\vec{b})$ the set of coordinates in which $\vec{a}$ and
$\vec{b}$ are guaranteed to differ, i.e.,
$\Delta(\vec{a},\vec{b})=\\{\,i\;{|}\;(\vec{a}[i]=1\wedge\vec{b}[i]=0)\vee(\vec{a}[i]=0\wedge\vec{b}[i]=1)\,\\}$,
and we denote by $\delta(\vec{a},\vec{b})$ the _Hamming distance_ between
$\vec{a}$ and $\vec{b}$ measured only between known entries, i.e.,
$|\Delta(\vec{a},\vec{b})|$. Moreover, for a subset $D^{\prime}\subseteq[d]$
of coordinates, where $[d]=\\{1,\dots,d\\}$, we denote by
$\vec{a}[D^{\prime}]$ the vector $\vec{a}$ restricted to the coordinates in
$D^{\prime}$.

There is a one-to-one correspondence between vectors in $\\{0,1\\}^{d}$ and
subsets of coordinates, i.e., for every vector, we can associate the unique
subset of coordinates containing all its one-coordinates and vice-versa. It
will be useful to represent a vector by the set of coordinates where the
vector has the value $1$. We introduce the following notation for vectors to
switch between their set-representation and vector-representation. We denote
by $\Delta(\vec{a})$ the set $\Delta(\vec{0},\vec{a})$. We extend this
notation to sets of vectors as follows: for a set $N$ of vectors in
$\\{0,1,{\small\square}\\}^{d}$, we denote by $\Delta(N)$ the set
$\\{\,\Delta(\vec{v})\;{|}\;\vec{v}\in N\,\\}$. We say that a vector
$\vec{a}\in\\{0,1,{\small\square}\\}^{d}$ is a _$t$ -vector_ if
$|\Delta(\vec{a})|=t$ and we say that $\vec{a}$ _contains_ a subset $S$ of
coordinates if $S\subseteq\Delta(\vec{a})$.

We say that a multiset111We remark that, in the interest of brevity and when
clear from context, we will sometimes use standard set notation such as
$A\subseteq B$ in conjunction with multisets. $M^{*}\subseteq\\{0,1\\}^{d}$ is
a _completion_ of a multiset $M\subseteq\\{0,1,{\small\square}\\}^{d}$ if
there is a bijection $\alpha:M\rightarrow M^{*}$ such that for all $\vec{a}\in
M$ and all $i\in[d]$ it holds that either $\vec{a}[i]={\small\square}$ or
$\alpha(\vec{a})[i]=\vec{a}[i]$. For a multiset $M$ of vectors over
$\\{0,1,{\small\square}\\}^{d}$, we let _the deletion distance to near-
completion_ , $\lambda(M)$, denote the minimum integer such that there exists
a subset $D_{M}\subseteq M$ with the following properties: (a)
$|D_{M}|\leq\lambda(M)$, and (b) every vector in $M\setminus D_{M}$ contains
at most $\lambda(M)$ missing entries. We call $D_{M}$ the _deletion
(multi-)set_ , and observe that $\lambda(M)$ along with a corresponding
deletion set can be trivially computed from $M$ in linear time.

A _sunflower_ in a set family $\mathcal{F}$ is a subset
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ such that all pairs of elements in
$\mathcal{F}^{\prime}$ have the same intersection. The following lemma
captures a useful observation that is used in several of our proofs.

######  Lemma 1 ([9]).

Let $t,r\in\mathbb{N}$. Let $N\subseteq\\{0,1\\}^{d}$ be a set of $t$-vectors
such that $\mathcal{F}:=\Delta(N)$ is a sunflower with core $C$. If $|N|>r$,
then for every vector $\vec{a}\in\\{0,1\\}^{d}$ with $|\Delta(\vec{a})|\leq
r$, $N$ contains a vector that has maximum distance to $\vec{a}$ among all
$t$-vectors that contain $C$.

We will say that a multiset $P$ is a _DIAM-Cluster_ (or $|P|$-_DIAM-Cluster_)
if $\delta(\vec{p},\vec{q})\leq r$ for every pair $\vec{p},\vec{q}\in P$.
Similarly, $P$ is a _RAD-Cluster_ (or $|P|$-_RAD-Cluster_) if there exists a
vector $\vec{c}\in\\{0,1\\}^{d}$ such that $\delta(\vec{c},\vec{p})\leq r$ for
every $\vec{p}\in P$.

Parameterized Complexity. In parameterized complexity [13, 7, 6], the
complexity of a problem is studied not only with respect to the input size,
but also with respect to some problem parameter(s). The core idea behind
parameterized complexity is that the combinatorial explosion resulting from
the NP-hardness of a problem can sometimes be confined to certain structural
parameters that are small in practical settings. We now proceed to the formal
definitions.

A parameterized problem $Q$ is a subset of $\Omega^{*}\times\mathbb{N}$, where
$\Omega$ is a fixed alphabet. Each instance of $Q$ is a pair $(I,\kappa)$,
where $\kappa\in\mathbb{N}$ is called the parameter. A parameterized problem
$Q$ is fixed-parameter tractable (FPT) [13, 7, 6], if there is an algorithm,
called an FPT-algorithm, that decides whether an input $(I,\kappa)$ is a
member of $Q$ in time $f(\kappa)\cdot|I|^{\mathcal{O}(1)}$, where $f$ is a
computable function and $|I|$ is the input instance size. The class FPT
denotes the class of all fixed-parameter tractable parameterized problems.

A parameterized problem $Q$ is FPT-reducible to a parameterized problem
$Q^{\prime}$ if there is an algorithm, called an _FPT -reduction_, that
transforms each instance $(I,\kappa)$ of $Q$ into an instance
$(I^{\prime},\kappa^{\prime})$ of $Q^{\prime}$ in time
$f(\kappa)\cdot|I|^{\mathcal{O}(1)}$, such that $\kappa^{\prime}\leq
g(\kappa)$ and $(I,\kappa)\in Q$ if and only if
$(I^{\prime},\kappa^{\prime})\in Q^{\prime}$, where $f$ and $g$ are computable
functions. By _FPT -time_, we denote time of the form
$f(\kappa)\cdot|I|^{\mathcal{O}(1)}$, where $f$ is a computable function.
Based on the notion of FPT-reducibility, a hierarchy of parameterized
complexity, the W-hierarchy $=\bigcup_{t\geq 0}{{{\mbox{{{W}}}}}}{{{[t]}}}$,
where ${{{\mbox{{{W}}}}}}{{{[t]}}}\subseteq{{{\mbox{{{W}}}}}}{{{[t+1]}}}$ for
all $t\geq 0$, has been introduced, in which the $0$-th level W[0] is the
class FPT. The notions of hardness and completeness have been defined for each
level W[$i$] of the W-hierarchy for $i\geq 1$ [7, 6]. It is commonly believed
that ${{{\mbox{{{W}}}}}}{{{[1]}}}\neq{\mbox{{{FPT}}}}$ (see [7, 6]). The
W[1]-hardness has served as the main working hypothesis of fixed-parameter
intractability. The class XP contains parameterized problems that can be
solved in time $\mathcal{O}(|I|^{f(\kappa)})$, where $f$ is a computable
function; it contains the class W[t], for $t\geq 0$, and every problem in XP
is polynomial-time solvable when the parameters are bounded by a constant. The
class paraNP is the class of parameterized problems that can be solved by non-
deterministic algorithms in time $f(\kappa)\cdot|I|^{\mathcal{O}(1)}$, where
$f$ is a computable function. A problem is _paraNP -hard_ if it is NP-hard for
a constant value of the parameter [13].

A parameterized problem is kernelizable if there exists a polynomial-time
reduction that maps an instance $(I,\kappa)$ of the problem to another
instance $(I^{\prime},\kappa^{\prime})$ such that (1) $|I^{\prime}|\leq
f(\kappa)$ and $\kappa^{\prime}\leq f(\kappa)$, where $f$ is a computable
function, and (2) $(I,\kappa)$ is a Yes-instance of the problem if and only if
$(I^{\prime},\kappa^{\prime})$ is. The instance $(I^{\prime},\kappa^{\prime})$
is called the kernel of $I$. It is well known that a decidable problem is FPT
if and only if it is kernelizable [7]. A _polynomial kernel_ is a kernel whose
size can be bounded by a polynomial in the parameter.

A _Turing kernelization_ for a parameterized problem $Q$ is an algorithm that,
provided with access to an oracle for $Q$, decides in polynomial time whether
or not an input $(I,\kappa)$ is a YES-instance of $Q$. During its computation,
the algorithm can produce polynomially-many oracle queries on input of size
$f(\kappa)$, for some computable function $f$. The function $f$ is referred to
as the _kernel size_. An _FPT approximation scheme_ for a parameterized
maximization problem is an algorithm that takes as input an instance
$(I,\kappa)$ of $Q$ and $0<\epsilon\leq 1$, and produces in FPT-time in
$\kappa+1/\epsilon$ a solution to $I$ that is an $(1-\epsilon)$-approximation
for the instance.

##  3 Finding a DIAM-Cluster in Incomplete Data

In this section, we present our results for Diam-Cluster-Completion. Our main
algorithmic results are that Diam-Cluster-Completion is FPT parameterized by
$r+\lambda(M)$ and is in XP parameterized by $k$ alone. Together with Theorem
17 (showing the W[1]-hardness of Diam-Cluster parameterized by $k$) and
Theorem 18 (showing the W[1]-hardness of Diam-Cluster-Completion parameterized
by $k$ even for $r=0$), this gives a complete complexity landscape for Diam-
Cluster-Completion parameterized by any combination of the parameters $k$,
$r$, and $\lambda(M)$.

###  3.1 Diam-Cluster-Completion Parameterized by $k+r+\lambda(M)$

We start by showing that Diam-Cluster-Completion parameterized by
$k+r+\lambda(M)$ is FPT. We will later show a stronger result, namely that the
same result already holds if we only parameterize by $r+\lambda(M)$. Showing
the weaker result here is important for the following reasons: (1) we use the
algorithm presented here as a subroutine in our result for the
parameterization $r+\lambda(M)$, (2) the techniques developed here can also be
employed for Rad-Cluster-Completion, and (3) we obtain a Turing kernel of size
polynomial in $k$.

The following lemma shows how this can be used to pre-process the instance (by
identifying vectors that cannot be in a cluster with the two vectors of
maximum distance). Note that this idea and the following lemma only deal with
the case that the solution cluster uses at least two vectors from $M\setminus
D_{M}$, where $D_{M}$ is a deletion set such that every vector in $M\setminus
D_{M}$ has at most $\lambda(M)$ missing entries. For a vector $\vec{v}$, we
denote by $\textup{ME}(\vec{v})$ the set of all missing coordinates of
$\vec{v}$.

######  Lemma 2.

Let $\vec{v}$ and $\vec{u}$ be two vectors in $M\setminus D_{M}$ and let $t$
be an integer with $\delta(\vec{v},\vec{u})\leq
t\leq\delta(\vec{v},\vec{u})+2|D_{M}|$. Then any vector $\vec{m}$ satisfying
$|\Delta(\vec{v},\vec{m})|>t$, $|\Delta(\vec{u},\vec{m})|>t$, or
$|\Delta(\vec{v},\vec{m})\cap\Delta(\vec{u},\vec{m})|>t/2$ cannot be contained
in a DIAM-Cluster/RAD-Cluster containing $\vec{v}$ and $\vec{u}$, and in which
$\vec{v}$ and $\vec{u}$ are two vectors of maximum distance $t$.

###### Proof.

Clearly, the lemma holds for any vector $\vec{m}$ satisfying either
$|\Delta(\vec{v},\vec{m})|>t$ or $|\Delta(\vec{v},\vec{m})|>t$, since we are
only looking for clusters where $\vec{v}$ and $\vec{u}$ are of distance $t$ to
one another and have maximum distance within the cluster. Now let $\vec{m}$ be
a vector satisfying
$|\Delta(\vec{v},\vec{m})\cap\Delta(\vec{u},\vec{m})|>t/2$. Since the
completions of $\vec{v}$ and $\vec{u}$ in a solution differ in exactly $t$
coordinates in
$\Delta(\vec{v},\vec{u})\cup\textup{ME}(\vec{v})\cup\textup{ME}(\vec{u})$, it
follows that $\vec{m}$ differs in at least $t/2$ of those coordinates from
either $\vec{v}$ or $\vec{u}$. It follows that $\vec{m}$ differs in more than
$t$ coordinates from either $\vec{u}$ or $\vec{v}$, and hence cannot be part
of a cluster with $\vec{v}$ and $\vec{u}$ of cluster diameter at most $t$. ∎

The following lemma shows that the instance obtained after identifying two
vectors of maximum distance and removing the vectors identified by the
previous lemma, cannot contain too many vectors since otherwise, it would be a
Yes-instance.

######  Lemma 3.

Let $\vec{v}$ and $\vec{u}$ be two vectors in $M\setminus D_{M}$ and let $t$
be an integer with $\delta(\vec{v},\vec{u})\leq
t\leq\delta(\vec{v},\vec{u})+2|D_{M}|$. Let $M^{\prime}$ be the set of all
vectors in $M\setminus(D_{M}\cup\\{\vec{v},\vec{u}\\})$ obtained after
removing all vectors $\vec{m}$ for which either
$|\Delta(\vec{v},\vec{m})|)>t$, $|\Delta(\vec{u},\vec{m})|)>t$, or
$|\Delta(\vec{v},\vec{m})\cap\Delta(\vec{u},\vec{m})|>t/2$. If
$|M^{\prime}|>k3^{2|D_{M}|+t}$, then $M^{\prime}$ contains a DIAM-Cluster of
size at least $k$ and diameter $t$, which is also a RAD-Cluster of radius
$t/2$.

###### Proof.

Assume that there are at least $k3^{2|D_{M}|+t}$ vectors $\vec{m}$ in
$M^{\prime}$. Then there is a set $S\subseteq M^{\prime}$ of size at least $k$
that agrees on all the coordinates in
$\Delta(\vec{v},\vec{u})\cup\textup{ME}(\vec{v})\cup\textup{ME}(\vec{u})$;
this is true since
$|\Delta(\vec{v},\vec{u})\cup\textup{ME}(\vec{v})\cup\textup{ME}(\vec{u})|\leq
t+2|D_{M}|$ and there are at most $3^{2|D_{M}|+t}$ possible assignments to
these coordinates. Since $\vec{v}$ and $\vec{u}$ are equal on all other
coordinates, i.e., the coordinates in
$[d]\setminus(\Delta(\vec{v},\vec{u})\cup\textup{ME}(\vec{v})\cup\textup{ME}(\vec{u}))$,
we obtain that any such vector $\vec{m}$ disagrees with $\vec{v}$ (or
$\vec{u}$) on at most $t/2$ of these coordinates; since otherwise
$|\Delta(\vec{v},\vec{m})\cap\Delta(\vec{u},\vec{m})|>t/2$ and we would have
removed $\vec{m}$ from $M\setminus(D_{M}\cup\\{\vec{v},\vec{u}\\})$. Since the
vectors in $S$ agree on all coordinates in
$\Delta(\vec{v},\vec{u})\cup\textup{ME}(\vec{v})\cup\textup{ME}(\vec{u})$, we
can complete all of them in the same manner on these coordinates. Moreover, on
all other coordinates, $\vec{v}$ is equal to $\vec{u}$ and we can complete all
vectors in $S$ by setting them equal to $\vec{v}$ (or equivalently $\vec{u}$)
on all other coordinates. Let $S^{\prime}$ be the set of vectors obtained from
$S$ after completing the vectors in this manner. Then
$\Delta(\vec{m},\vec{m}^{\prime})\subseteq[d]\setminus(\Delta(\vec{v},\vec{u})\cup\textup{ME}(\vec{v})\cup\textup{ME}(\vec{u}))$;
moreover,
$|\Delta(\vec{m},\vec{m}^{\prime})|\leq|(\Delta(\vec{v},\vec{m})\cap\Delta(\vec{u},\vec{m}))\cup(\Delta(\vec{v},\vec{m}^{\prime})\cap\Delta(\vec{u},\vec{m}^{\prime}))|\leq
2t/2=t$ for every two vectors $\vec{m}$ and $\vec{m}^{\prime}$ in
$S^{\prime}$. Therefore, the vectors in $S^{\prime}$ form a DIAM-Cluster with
diameter at most $t$. Moreover, the vectors in $S^{\prime}$ also form a RAD-
Cluster with radius at most $t/2$, as witnessed by a center equal to $\vec{v}$
(or equivalently $\vec{u}$) on all coordinates in
$[d]\setminus(\Delta(\vec{v},\vec{u})\cup\textup{ME}(\vec{v})\cup\textup{ME}(\vec{u}))$,
and equal to any vector in $S^{\prime}$ on all other coordinates. ∎

We will now introduce notions required to reduce the number of coordinates.
Let $|Z(M)|$, for $M\subseteq\\{0,1,{\small\square}\\}^{d}$, be the set of all
coordinates $i$ such that at least two vectors in $M$ disagree on their $i$-th
coordinate, i.e., there are two vectors $\vec{y},\vec{y}^{\prime}\in M$ such
that $\\{\vec{y}[i],\vec{y}^{\prime}[i]\\}=\\{0,1\\}$. Intuitively, $Z(M)$ is
the set of _important coordinates_ , since all other coordinates can be safely
removed from the instance; this is because they can always be completed to the
same value. We are now ready to show that Diam-Cluster-Completion has a Turing
kernel parameterized by $k+r+\lambda(M)$.

######  Theorem 4.

Diam-Cluster-Completion parameterized by $k+r+\lambda(M)$ has a Turing-kernel
containing at most $n=k3^{2\lambda(M)+r}+\lambda(M)+2$ vectors, each having at
most $\max\\{r(n-1)+\lambda(M),\binom{\lambda(M)}{2}(r+1)\\}$ coordinates.

###### Proof.

We distinguish three cases: (1) the solution cluster contains at least two
vectors in $M\setminus D_{M}$, (2) the solution cluster contains exactly one
vector in $M\setminus D_{M}$, and (3) the solution cluster does not contain
any vector in $M\setminus D_{M}$.

We start by showing the result for case (1). Our first goal is to reduce the
number of vectors in $M\setminus D_{M}$. As a first step, we guess two vectors
$\vec{v}$ and $\vec{u}$ in $M\setminus D_{M}$ that are farthest apart in the
solution cluster w.r.t. to all vectors in $M\setminus D_{M}$; this is possible
since we assume that the cluster contains at least two vectors in $M\setminus
D_{M}$. We then guess the exact distance, $t$, between $\vec{v}$ and $\vec{u}$
in a completion leading to the cluster. Note that $t$ can be any value between
$\delta(\vec{v},\vec{u})$ and $\delta(\vec{v},\vec{u})+2|D_{M}|$, but is at
most $r$. We now remove all vectors $\vec{m}$ from $M$ for which either
$\delta(\vec{v},\vec{m})>t$, $\delta(\vec{u},\vec{m})>t$, or
$|\Delta(\vec{v},\vec{m})\cap\Delta(\vec{u},\vec{m})|>t/2$. Note that this is
safe by of Lemma 2. It now follows from Lemma 3 that if
$M\setminus(D_{M}\cup\\{\vec{v},\vec{u}\\})$ contains more than
$k3^{2|D_{M}|+t}$ vectors, then we can return a trivial Yes-instance of Diam-
Cluster-Completion. Otherwise, we obtain that $|M\setminus D_{M}|\leq
k3^{2|D_{M}|+t}+2$. We now add back the vectors in $D_{M}$. Clearly, if a
vector in $D_{M}$ differs in more than $t$ coordinates from $\vec{v}$, then it
cannot be part of a DIAM-Cluster containing $\vec{v}$, and we can safely
remove it from $D_{M}$. Hence every vector in $M$ now differs from $\vec{v}$
in at most $t$ coordinates, which implies that $Z(M)\leq t(|M|-1)+|D_{M}|$. We
now remove all coordinates outside of $Z(M)$ from $M$, since they can always
be completed in the same manner for all the vectors. Now the remaining
instance is a kernel containing at most $m=k3^{2|D_{M}|+t}+2+|D_{M}|$ vectors,
each having at most $t(m-1)+|D_{M}|$ coordinates. This completes the proof for
the case where the solution cluster contains at least two vectors in
$M\setminus D_{M}$.

In the following let $t=r$. For the second case, i.e., the case that the
solution cluster contains exactly one vector in $M\setminus D_{M}$, we first
guess the vector say $\vec{m}$ in $M\setminus D_{M}$ that will be included in
the solution cluster and remove all other vectors from $M\setminus D_{M}$.
This leaves us with at most $|D_{M}|+1$ vectors, and it only remains to reduce
the number of relevant coordinates. Since we guessed that $\vec{m}$ will be in
the solution cluster, we can now safely remove all vectors
$\vec{m}^{\prime}\in M$, with $\delta(\vec{m},\vec{m}^{\prime})>t$. Every
remaining vector differs from $\vec{m}$ in at most $t$ coordinates, and hence
$Z(M)\leq t|D_{M}|+|D_{M}|$, which gives us the desired kernel.

For the third case, i.e., the case that the solution cluster contains no
vectors in $M\setminus D_{M}$, we first remove all vectors in $M\setminus
D_{M}$. This leaves us with $|D_{M}|$ vectors, and it only remains to reduce
the number of coordinates. To achieve this, we compute a set of coordinates
that preserves the distance up to $t$ between any pair of vectors. Namely, we
compute a set $D$ of relevant coordinates, starting from $D=\emptyset$, by
adding the following coordinates to $D$ for every two distinct vectors
$\vec{m}$ and $\vec{m}^{\prime}$ in $M$:

  * •

if $|\Delta(\vec{m},\vec{m}^{\prime})|\leq t$, we add
$\Delta(\vec{m},\vec{m}^{\prime})$ to $D$ and otherwise

  * •

we add an arbitrary subset of exactly $t+1$ coordinates in
$\Delta(\vec{m},\vec{m}^{\prime})$ to $D$.

Let $M_{D}$ be the matrix obtained from $M$ after removing all
coordinates/columns not in $D$. We claim that $(M,k,r)$ and $(M_{D},k,r)$ are
equivalent instances of Diam-Cluster-Completion. This follows because the
vectors in any DIAM-Cluster for $(M_{D},k,r)$ can be completed in the same
manner on all coordinates not in $D$. Since $|D|\leq\binom{|D_{M}|}{2}(t+1)$,
the remaining instance has at most $|D_{M}|$ vectors each having at most
$\binom{|D_{M}|}{2}(t+1)$ coordinates. ∎

###  3.2 Diam-Cluster-Completion Parameterized by $r+\lambda(M)$

With Theorem 4 in hand, we can move on to establishing the fixed-parameter
tractability of Diam-Cluster-Completion parameterized by $r+\lambda(M)$. At
the heart of our approach lies a new technique for analyzing the structure of
vectors through sunflowers in their set representations, which we dub
_iterative sunflower harvesting_. We first preprocess the instance to
establish some basic properties. We then show a general result about
sunflowers that allows us to derive a succinct representation of the solution
cluster—in particular, this guarantees that the hypothetical solution can be
described by a bounded number of sunflower cores. Finally, we proceed to
“harvesting” these sunflowers cores using a branching procedure, thus
computing the solution cluster.

####  3.2.1 Preprocessing the Instance

Let $(M,k,r)$ be an instance of Diam-Cluster-Completion, let $M^{*}$ be a
completion of $M$ that contains a maximum size DIAM-Cluster, and fix $P^{*}$
to be such a maximum size DIAM-Cluster in $M^{*}$. We also fix $D_{M}$ to be a
$\lambda(M)$-deletion set. The goal of the algorithm is to find $M^{*}$ and
$P^{*}$.

If $k<\lambda(M)+2$, then we can use the algorithm in Theorem 4 to obtain a
Turing kernel whose size is a function of $r+\lambda(M)$, which, in turn,
would imply that Diam-Cluster-Completion if FPT parameterized by
$r+\lambda(M)$, thus giving the desired result. We assume henceforth that
$P^{*}$ contains the completion of at least two vectors in $M\setminus D_{M}$.
We can guess the subset $P_{R}$ of $D_{M}$ that will be completed to vectors
in $P^{*}$, and restrict our attention to finding a DIAM-Cluster in
$M\setminus D_{M}$ of size $|P^{*}\setminus D_{M}|$. We will do so by
enumerating all such DIAM-Cluster’s in $M\setminus D_{M}$ and at the end check
whether one of them, together with $P_{R}$, can be extended into a DIAM-
Cluster.

Therefore, we will focus on what follows on finding a cluster in $M\setminus
D_{M}$. We first guess two vectors $\vec{v}$ and $\vec{u}$ in $M\setminus
D_{M}$, together with their completions $\vec{v}^{*}$ and $\vec{u}^{*}$,
respectively, such that $\vec{v}^{*}$ and $\vec{u}^{*}$ are both in $P^{*}$
and are the farthest vectors apart in $P^{*}\setminus D_{M}$; fix
$r_{\max}=\delta(\vec{v}^{*},\vec{u}^{*})$. We remove all other vectors that
can be completed into $\vec{v}^{*}$ or $\vec{u}^{*}$, and reduce $k$
accordingly; hence, we do not keep duplicates of the two vectors that we
already know to be in $P^{*}$. We then normalize all vectors in $M$ so that
$\vec{v}^{*}$ becomes the all-zero vector, i.e., we replace $\vec{v}^{*}$ by
the all-zero vector, and for every other vector $\vec{w}\neq\vec{v}$, we
replace it with the vector $\vec{w}^{\prime}$ such that
$\vec{w}^{\prime}[i]=0$ if $\vec{v}^{*}[i]=\vec{w}[i]$,
$\vec{w}^{\prime}[i]={\small\square}$ if $\vec{w}[i]={\small\square}$, and
$\vec{w}^{\prime}[i]=1$, otherwise. Finally, for each vector $\vec{w}\in
M\setminus D_{M}$, we compute the set $\Lambda(\vec{w})$ of all completions of
$\vec{w}$ at distance at most $r_{\max}$ from both $\vec{v}^{*}$ and
$\vec{u}^{*}$. Note that $\Lambda(\vec{w})$ can be computed in
$\mathcal{O}(2^{\lambda(M)}\cdot d)$ time for each vector in $M\setminus
D_{M}$, where $d$ is the dimension of the vectors in $M$. We then remove all
vectors $\vec{w}$ with $\Lambda(\vec{w})=\emptyset$ from $M\setminus D_{M}$.

We will extend the notation $\Lambda(\vec{w})$ to $\Lambda_{C}(\vec{w})$, for
a multiset $C$ of vectors in $\\{0,1\\}^{d}$, such that $\Lambda_{C}(\vec{w})$
is the set of all completions of a vector $\vec{w}$ at distance at most
$r_{\max}$ to all vectors in $C$. We are now ready to show that after
normalizing the vectors in $P^{*}$, the multiset $P^{*}\setminus D_{M}$
satisfies certain structural properties that we refer to as an $r$-saturated
subset (of $M^{*}$); these structural properties allow for a succinct
representation of $P^{*}$.

####  3.2.2 Sunflower Fields or Representing Sets by Cores of Sunflowers

In this subsection, we provide the central component for our algorithm based
on the iterative sunflower harvesting technique. Crucial to this component is
a general structural lemma that allows us to represent a family of sets in a
succinct manner in terms of sunflower cores, which we believe to be
interesting in its own right. We first state the result in its most general
form (for sets), and then show how to adapt it to our setting.

######  Definition 3.1.

Let $U$ be a universe, $\mathcal{B}$ a family of subsets of $U$ and
$\mathcal{A}\subseteq\mathcal{B}$. We say that $\mathcal{A}$ is an _$r$
-saturated_ subfamily of $\mathcal{B}$ (for $r\in\mathbb{N}$) if the following
holds for every $t\in\mathbb{N}$ and every sunflower $S\subseteq\mathcal{A}$
containing at least $r+1$ sets of cardinality $t$ with core $C$: $\mathcal{A}$
contains every set $B\in\mathcal{B}$ of cardinality $t$ such that $C\subseteq
B$.

Intuitively, this property states that $\mathcal{A}$ contains all sets in
$\mathcal{B}$ which are super-sets of cores of every sufficiently-large
sunflower in $\mathcal{A}$ (with sets of the same cardinality).

The connection of this set property to clusters is as follows. We will show
that every maximal cluster is an $r$-saturated subset of $M^{*}$. Since
$P^{*}$ contains the all-zero vector $\vec{v}^{*}$, any vector in $P^{*}$
contains at most $r$ ones. Fix $t\in[r]$, and consider the set of all vectors
in $P^{*}$ containing exactly $t$ ones. The above notion will allow to draw
the following assumption: if the aforementioned set of vectors is large, then
it must contain a large sunflower and all the vectors in $M$ whose completions
share the core of this sunflower _must be_ in $P$. This property will
subsequently allow us to represent every hypothetical solution using a bounded
number of sunflowers, as we show next.

The crucial insight now is that every $r$-saturated subfamily containing only
sets of bounded size admits a succinct representation, where we can completely
describe the set via a bounded number of sunflower cores. This is made precise
in the following lemma.

######  Lemma 5.

Let $\mathcal{A}$ and $\mathcal{B}$ be two families of sets of cardinality at
most $r^{\prime}$ over universe $U$ such that
$\mathcal{A}\subseteq\mathcal{B}$. If $\mathcal{A}$ is an $r$-saturated subset
of $\mathcal{B}$, then there is a set $\mathcal{S}$ of at most
$(rr^{\prime})^{r^{\prime}}$ subsets of $U$ such that $\mathcal{A}$ is equal
to the set of all sets $B$ in $\mathcal{B}$ satisfying that $S\subseteq B$ for
some $S\in\mathcal{S}$. Moreover, for each set $S\in\mathcal{S}$, $S$ is
either the core of a sunflower in $\mathcal{A}$ with at least $r+1$ petals, or
$|S|=r^{\prime}$.

######  Proof 3.2.

We show the claim by giving a bounded-depth search tree algorithm that
computes a rooted (search) tree $T$, where each node $t$ of $T$ is associated
with a subset $X_{t}$ of $U$, and in which each leaf node is marked as either
successful or unsuccessful. Note that the algorithm is not necessarily
efficient, and all the steps can be brute-forced. The set $\mathcal{S}$ then
contains all sets associated with a successful leaf node of $T$. Initially,
$T$ only consists of the root node $r$ for which we set $X_{r}:=\emptyset$.
The algorithm then proceeds as follows as long as $T$ contains a leaf that is
not yet marked as either successful or unsuccessful. Let $t$ be a leaf node of
$T$ (that has not yet been marked). We first check whether
$|X_{t}|=r^{\prime}$ and $X_{t}\in\mathcal{A}$, or whether $\mathcal{A}$
contains a sunflower with at least $r+1$ petals and core $X_{t}$; if this is
the case, we mark $t$ as a successful leaf node. Note that, since
$\mathcal{A}$ is an $r$-saturated subset of $\mathcal{B}$, $\mathcal{A}$
contains all sets $B\in\mathcal{B}$ such that $X_{t}\subseteq B$. Otherwise,
let $\mathcal{A}_{X}$ be the subset of $\mathcal{A}$ containing all sets
$A\in\mathcal{A}$ with $X_{t}\subseteq A$. If $\mathcal{A}_{X}=\emptyset$, we
mark $t$ as an unsuccessful leaf node. Otherwise, let
$\mathcal{A}_{X}^{\prime}$ be a maximal sunflower in $\mathcal{A}_{X}$ with
core $X_{t}$. Note that $\mathcal{A}_{X}^{\prime}\neq\emptyset$ because
$\mathcal{A}_{X}\neq\emptyset$ (and we can choose the core of a sunflower
containing only one set/petal arbitrarily). Moreover,
$|\mathcal{A}_{X}^{\prime}|\leq r$, since otherwise $\mathcal{A}$ contains a
sunflower with at least $r+1$ petals and core $X_{t}$. We now claim that the
set $H:=(\bigcup_{A\in\mathcal{A}_{X}^{\prime}}A)\setminus X_{t}$ is a hitting
set for the sets in $\mathcal{A}_{X}$. Assume, for a contradiction, that this
is not the case and let $A\in\mathcal{A}_{X}$ be such that $H\cap
A=\emptyset$. Then we can extend $\mathcal{A}_{X}^{\prime}$ by $A$
contradicting our assumption that $\mathcal{A}_{X}^{\prime}$ is inclusion-wise
maximal. Now, for every $h\in H$, we add a new child node $t_{h}$ to $t$ and
set $X_{t_{h}}:=X_{t}\cup\\{h\\}$. Note that we add at most $|H|\leq
r(r^{\prime}-|X_{t}|)$ children to $t$.

Let $\mathcal{S}$ be the set computed by the above algorithm. Note that $T$
has height at most $r^{\prime}$. This is because $|X_{t}|=l$ for any node $t$
of $T$ at level $l$ and we stop when there is at most one set in $\mathcal{A}$
containing $X_{t}$, which implies that $t$ is marked either as successful or
unsuccessful leaf node. Moreover, since every node of $T$ has at most
$rr^{\prime}$ children, we obtain that $T$ has at most
$(rr^{\prime})^{r^{\prime}}$ (leaf) nodes and hence
$|\mathcal{S}|\leq(rr^{\prime})^{r^{\prime}}$, as required. It remains to show
that, for every set $A$ in $\mathcal{A}$, there is a $S\in\mathcal{S}$ such
that $S\subseteq A$. Let $A$ be an arbitrary set in $\mathcal{A}$. We first
show that there is a leaf node $l$ such that $X_{l}$ is contained in $A$.
Towards showing this, first note that $X_{r}=\emptyset$ is clearly contained
in $A$ for the root node $r$ of $T$. Furthermore, if $t$ is an inner node of
$T$ such that $X_{t}$ is contained in $A$, then there is a child $t^{\prime}$
of $t$ in $T$ with $X_{t^{\prime}}$ contained in $A$. This follows from the
construction of $T$ since $t$ has a child $t^{\prime\prime}$ for every $h\in
H$ with $X_{t^{\prime\prime}}:=X_{t}\cup\\{h\\}$, where $H$ is a hitting set
of $\mathcal{A}_{X_{t}}$ and hence also hits $A$. Starting with the root $r$
of $T$ and going down the tree $T$ by always choosing a child $t$ such that
$X_{t}$ is contained in $A$, we will eventually end up at the leaf node $l$
such that $X_{l}$ is contained in $A$. Finally, because $\mathcal{A}_{X_{l}}$
contains $A$, $l$ is marked as a successful leaf node meaning that
$X_{l}\in\mathcal{S}$ is contained in $A$.

We will now show how Lemma 5 can be employed in our setting. Let
$M,M^{\prime}\subseteq\\{0,1\\}^{d}$ with $M^{\prime}\subseteq M$. Then
$M^{\prime}$ is an _$r$ -saturated subset_ of $M$ if $\Delta(M^{\prime})$ is
an $r$-saturated subset of $\Delta(M)$. Herein, one can think of $M$ as being
(a part of) the input matrix and $M^{\prime}$ as being an inclusion-wise
maximal cluster; we will later show that this property guarantees that
$M^{\prime}$ is an $r$-saturated subset of $M$. Using this definition, the
following corollary now follows immediately from Lemma 5.

######  Corollary 6.

Let $r^{\prime},r\in\mathbb{N}$ and $M,M^{\prime}\subseteq\\{0,1\\}^{d}$ be
sets of $r^{\prime}$-vectors such that $M^{\prime}$ is an $r$-saturated subset
of $M$. There is a set $\mathcal{S}$ of at most $(rr^{\prime})^{r^{\prime}}$
subsets of $[d]$ such that $M^{\prime}$ is equal to the set of all vectors
$\vec{m}$ in $M$ satisfying $S\subseteq\Delta(\vec{m})$ for some
$S\in\mathcal{S}$. Moreover, for each set $S\in\mathcal{S}$, $S$ is either a
core of a sunflower in $\Delta(M^{\prime})$ with at least $r+1$ petals, or
$|S|=r^{\prime}$.

We now can show that after normalizing the vectors in $P^{*}$, the multiset
$P^{*}\setminus D_{M}$ is an $r$-saturated subset of $M^{*}$.

######  Lemma 7.

Let $(M,k,r)$ be an instance of Diam-Cluster-Completion, let $M^{*}$ be a
completion of $M$ and let $P^{*}$ be a DIAM-Cluster in $M^{*}$ of maximum size
such that $\vec{0}\in P^{*}$. Then for every $N\subseteq M^{*}$,
$P^{*}\setminus N$ is an $r$-saturated subset of $M^{*}\setminus N$.

######  Proof 3.3.

Let $t\in\mathbb{N}$ and $S\subseteq(P^{*}\setminus N)$ such that

  * •

$|S|>r$,

  * •

for all $\vec{w}\in S$ it holds that $|\Delta(\vec{w})|=t$, and

  * •

$\mathcal{F}=\Delta(S)$ is a sunflower with core $X$.

Let $\vec{m}$ be an arbitrary $t$-vector in $M^{*}\setminus(N\cup P^{*})$
containing $X$, and let $\vec{c}$ be an arbitrary vector in $P^{*}$. Then
$|\Delta(\vec{c})|=\delta(\vec{0},\vec{c})\leq r$, and it follows from Lemma 1
that $S$ contains a vector $\vec{n}$ that has maximum distance to $\vec{c}$
among all $t$-vectors in $M^{*}$ containing $X$. Hence, the distance between
$\vec{m}$ and $\vec{c}$ is at most that between $\vec{n}$ and $\vec{c}$,
which, since both $\vec{n}$ and $\vec{c}$ are in $P^{*}$, is at most $r$.
Consequently, the distance between $\vec{m}$ and any vector in $P^{*}$ is at
most $r$, contradicting the maximality of $P^{*}$.

Since $P^{*}\setminus N$ is an $r$-saturated subset of $M^{*}\setminus N$, by
Corollary 6, applied separately for each $r^{\prime}\in[r]$, there exists a
set $\mathcal{S}=\\{(S_{1},r_{1}),\ldots,(S_{\ell},r_{\ell})\\}$, with
$\ell\leq\sum_{r^{\prime}\in[r]}(rr^{\prime})^{r^{\prime}}\leq r^{2r+1}$, such
that $P^{*}\setminus N$ contains precisely all the vectors $\vec{w}$ in
$M^{*}$, such that for some $(S_{i},r_{i})$, $i\in[\ell]$,
$S_{i}\in\Delta(\vec{w})$ and $|\Delta(\vec{w})|=r_{i}$.

We call the pair $(S_{i},r_{i})$ an _$r_{i}$ -center_ (of $P^{*}\setminus N$
in $M^{*}\setminus N$). We say that a vector
$\vec{w}\in\\{0,1,{\small\square}\\}^{d}$ is _compatible_ with $r_{i}$-center
$(S_{i},r_{i})$ if there is a completion $\vec{w}^{*}\in\\{0,1\\}^{d}$ of
$\vec{w}$, called _witness of compatibility_ , such that
$S_{i}\subseteq\Delta(\vec{w}^{*})$ and $|\Delta(\vec{w}^{*})|=r_{i}$. We say
that $\vec{w}\in\\{0,1,{\small\square}\\}^{d}$ is _compatible_ with
$\mathcal{S}$ if it is compatible with some $(S_{i},r_{i})\in\mathcal{S}$.

The _size_ of an $r_{i}$-center is the number of vectors that are compatible
with it in $M$. Moreover, for a set
$\mathcal{S}=\\{(S_{1},r_{1}),\ldots,(S_{\ell},r_{\ell})\\}$ and a multiset
$C$ of vectors from $\\{0,1\\}^{d}$, we say that $\mathcal{S}$ _defines_ $C$,
if every vector $\vec{c}\in C$ is compatible with $\mathcal{S}$ and for every
$(S_{i},r_{i})\in\mathcal{S}$ there is a vector in $C$ compatible with
$(S_{i},r_{i})$. We say that $\mathcal{S}$ _properly_ defines $C$, if
$|\mathcal{S}|\leq r^{2r+1}$, $\mathcal{S}$ defines $C$, and for every
$(S_{i},r_{i})\in\mathcal{S}$ either:

  * •

$|S_{i}|=r_{i}$ and the unique vector that is compatible with $(S_{i},r_{i})$
is in $C$; or

  * •

$|S_{i}|<r_{i}$ and $C$ contains a set $N$ of $r+1$ $r_{i}$-vectors such that
$\Delta(N)$ forms a sunflower with core $S_{i}$.

Note that if every vector in $C$ has at most $r_{\max}$ $1$’s, then since $C$
is an $r$-saturated subset of $C$, it follows from Corollary 6 that there
always exists a set $\mathcal{S}$ that properly defines $C$.

######  Observation 8.

Let $C$ be a multiset of vectors from $\\{0,1\\}^{d}$, with $\max_{\vec{c}\in
C}|\Delta(\vec{c})|\leq r$. Then there exists a set $\mathcal{S}$ of at most
$r^{2r+1}$ $r_{i}$-centers that properly defines $C$.

Suppose that we have a correct guess for $\mathcal{S}$, then we can already
solve the problem as follows. For each $(S_{i},r_{i})\in\mathcal{S}$ such that
$|S_{i}|=r_{i}$, there is only one possible $r_{i}$-vector that contains
$S_{i}$. If our guess is correct, then $P^{*}$ contains at least one vector
that can be completed to this particular $r_{i}$-vector, and by maximality of
$P^{*}$, $P^{*}$ has to contain all such vectors. If
$(S_{i},r_{i})\in\mathcal{S}$ such that $|S_{i}|<r_{i}$, then $P^{*}$ contains
a sunflower containing $r_{i}$-vectors of size at least $r+1$ whose core is
$S_{i}$. Clearly, $P^{*}$ contains all the vectors that can be completed to an
$r_{i}$-vector containing $S_{i}$, since Lemma 7 holds for any completion
$M^{*}$ of $M$ that contains $P^{*}$ as a subset. The following lemma shows
that all such vectors can be completed arbitrarily since all that matters is
that their completion is compatible with $\mathcal{S}$.

######  Lemma 9.

Let $(M,k,r)$ be an instance of Diam-Cluster-Completion, $M^{*}$ a completion
of $M$, $P^{*}$ a DIAM-Cluster in $M^{*}$ of maximum size with $\vec{0}\in
P^{*}$, and $N\subseteq M^{*}$. If $\mathcal{S}$ properly defines
$P^{*}\setminus N$, then for every pair of vectors
$\vec{w}_{1},\vec{w}_{2}\in\\{0,1\\}^{d}$ compatible with $\mathcal{S}$ it
holds that $\delta(\vec{w}_{1},\vec{w}_{2})\leq r$.

######  Proof 3.4.

Let $\vec{w}_{i}$, $i\in\\{1,2\\}$, be compatible with the $r_{i}$-center
$(S_{i},r_{i})$. If $|S_{i}|<r_{i}$, $i\in\\{1,2\\}$, then let $N_{i}\subseteq
P^{*}\setminus N$ be the set of $r_{i}$-vectors such that
$\mathcal{F}_{i}=\Delta(N_{i})$ is a sunflower with core $S_{i}$. Note that
such a set $N_{i}$ always exists by the definition of $\mathcal{S}$. Moreover,
if $|S_{i}|=r_{i}$, then $\vec{w}_{i}$ is uniquely defined and already in
$P^{*}\setminus N$. Hence, if both $|S_{1}|=r_{1}$ and $|S_{2}|=r_{2}$, then
the lemma holds.

If $|S_{1}|=r_{1}$ and $|S_{2}|<r_{2}$, then $P^{*}\setminus N$ contains a
vector identical to $\vec{w}_{1}$, $\Delta(\vec{w}_{1})=r_{1}\leq r$ and by
Lemma 1 there is a vector $\vec{v}_{2}$ in $N_{2}$ that has the maximum
distance to $\vec{w}_{1}$ among all $r_{2}$-vectors that contain $C_{2}$ and
$\delta(\vec{w}_{1},\vec{w}_{2})\leq r$. The case where $|S_{1}|<r_{1}$ and
$|S_{2}|=r_{2}$ is symmetric.

Finally, if both $|S_{1}|<r_{1}$ and $|S_{2}|<r_{2}$, then for every
$\vec{v}_{1}\in N_{1}$ is $\Delta(\vec{v}_{1})=r_{1}\leq r$ and by Lemma 1
there is a vector $\vec{v}_{2}$ in $N_{2}$ that has the maximum distance to
$\vec{v}_{1}$ among all $r_{2}$-vectors that contain $C_{2}$. Hence,
$\vec{w}_{2}$ has distance at most $r$ to all vectors in $N_{1}$. Now
$\Delta(\vec{w}_{2})=r_{2}\leq r$ and by Lemma 1 there is a vector
$\vec{v}_{1}$ in $N_{1}$ that has the maximum distance to $\vec{w}_{2}$ among
all $r_{1}$-vectors that contain $C_{1}$. Since
$\delta(\vec{w}_{2},\vec{v}_{1})\leq r$, it follows that
$\delta(\vec{w}_{1},\vec{w}_{2})\leq r$.

It is easy to see that there are at most $d^{r+1}$ choices for a pair
$(S_{i},r_{i})$ (i.e., a $r_{i}$-center), and hence we have at most
$(d^{r+1})^{r^{2r+1}}=d^{\mathcal{O}(r^{2r+2})}$ possible choices for the set
$\mathcal{S}$ that properly defines $P^{*}$. This bound already implies an XP-
algorithm. To obtain a fixed-parameter algorithm, it suffices to find the
correct guess for $\mathcal{S}$ in FPT-time, which is our next goal.

####  3.2.3 Iterative Sunflower Harvesting

We are now ready to describe the iterative sunflower harvesting procedure,
which allows us to obtain the desired FPT-algorithm. Namely, we show that
instead of enumerating all $d^{r^{2r+2}}$ possible sets $\mathcal{S}$ of
$r_{i}$-centers to find the one that properly defines $P^{*}\setminus D_{M}$,
it suffices to enumerate only $f(r,\lambda(M))$-many “important”
$r_{i}$-centers for each choice of $\vec{v}^{*}$ and $\vec{u}^{*}$ (recall
that $\vec{v}^{*}$ and $\vec{u}^{*}$ are the two fixed vectors in
$P^{*}\setminus D_{M}$ that were guessed), where $f$ is some function that
depends only on $r$ and $\lambda(M)$. Moreover, we can enumerate these
possibilities in FPT-time.

The idea is to enumerate possible sets $\mathcal{S}$ such that we compute
pairs $(S_{i},r_{i})$ in $\mathcal{S}$ ordered by size from largest to
smallest, give a lower bound on the size of the next largest $r_{i}$-center,
and show that only $g(r,\lambda(M))$ such large $r_{i}$-center exist, for some
function $g$. Note that if we guess an $r_{i}$-center $(S_{i},r_{i})$ with
$|S_{i}|<r_{i}$, then if our guess is correct, we can, by Lemma 9, already
complete the vectors that can be completed to $r_{i}$-vector containing
$S_{i}$ and include all of them in the DIAM-Cluster. The following lemma shows
that if we have some partial DIAM-Cluster $C$ computed, then we can pre-
process the remaining instance such that it contains a DIAM-Cluster compatible
with $C$ of size at least a $2^{r}$-fraction of the remaining instance. This
gives us that the intersection of $P^{*}$ and the remaining instance has to be
large, and in turn, implies that one of the remaining $r_{i}$-centers of
$P^{*}$ has size roughly at least ($2^{r}r^{2r+1}-|D_{M}|$)-fraction of the
remaining instance. Recall that, for a vector
$\vec{w}\in\\{0,1,{\small\square}\\}^{d}$ and multiset $C$ of vectors from
$\\{0,1\\}^{d}$, $\Lambda_{C}(\vec{w})$ denotes the set of all completions of
vector $\vec{w}$ at distance at most $r_{\max}$ to all vectors in $C$, i.e.,
$\max_{\vec{c}\in C}\\{\delta(\vec{c},\vec{c}_{w})\\}\leq r_{\max}$.

######  Lemma 10.

Let $C$ be a DIAM-Cluster of vectors in $\\{0,1\\}^{d}$ such that
$\\{\vec{0},\vec{u}\\}\subseteq C$ for some $r_{\max}$-vector
$\vec{u}\in\\{0,1\\}^{d}$, where $r_{\max}\in[r]$. Suppose further that
$\delta(\vec{a},\vec{b})\leq r_{\max}$ for every distinct $\vec{a},\vec{b}\in
C$, and let $M^{\prime}$ be a multiset of vectors $\vec{w}$ with
$\Lambda_{C}(\vec{w})\neq\emptyset$. Then there exists $P\subseteq M^{\prime}$
and a completion $P^{*}$ of $P$ such that $|P|\geq|M^{\prime}|/2^{r_{\max}}$
and $P^{*}\cup C$ is a DIAM-Cluster of diameter $r_{\max}$.

######  Proof 3.5.

Fix a completion $M^{*}$ of $M^{\prime}$ such that each vector $\vec{w}\in
M^{\prime}$ is completed to $\vec{c}_{w}\in\Lambda_{C}(\vec{w})$. Let
$S\subseteq\Delta(\vec{u})$, and let $M^{*}_{S}$ be the subset of $M^{*}$
containing precisely all the vectors $\vec{w}$ such that
$\Delta(\vec{w})\cap\Delta(\vec{u})=S$. We claim that $C\cup M^{*}_{S}$ is a
DIAM-Cluster. First, note that $\delta(\vec{a},\vec{b})\leq r_{\max}$ for
every distinct $\vec{a},\vec{b}\in C$ and also for every distinct $\vec{a}\in
C$ and $\vec{b}\in M^{*}_{S}$. It remains to show that
$\delta(\vec{a},\vec{b})\leq r_{\max}$ for every distinct $\vec{a},\vec{b}\in
M^{*}_{S}$. Clearly,
$\delta(\vec{a},\vec{b})\leq|\Delta(\vec{a})|+|\Delta(\vec{b})|-2|S|$. Now
$|\Delta(\vec{a})|\leq r_{\max}$ and $|\Delta(\vec{b})|\leq r_{\max}$ because
$\vec{0}\in C$ and hence $|\Delta(\vec{a})|-|S|\leq r_{\max}-|S|$ and
$|\Delta(\vec{b})|-|S|\leq r_{\max}-|S|$. Moreover
$\delta(\vec{a},\vec{u})=r_{\max}-|S|+|\Delta(\vec{a})|-|S|\leq r_{\max}$.
Therefore, $|\Delta(\vec{a})|-|S|\leq|S|$ and similarly
$|\Delta(\vec{b})|-|S|\leq|S|$. Hence
$\delta(\vec{a},\vec{b})\leq|\Delta(\vec{a})|+|\Delta(\vec{b})|-2|S|\leq\min(2|S|,2r_{\max}-2|S|)$.
It follows that either $|S|\leq r_{\max}/2$ and $\delta(\vec{a},\vec{b})\leq
r_{\max}$ or $|S|\geq r_{\max}/2$ and $\delta(\vec{a},\vec{b})\leq
2r_{\max}-2|S|\leq r$. Since there are $2^{r_{\max}}$ possibilities for the
set $S$, and each vector in $M^{*}$ is in one of sets $M^{*}_{S}$, the lemma
follows.

As a corollary, we obtain the following lemma. Before we state the lemma, we
introduce some additional notations that will be useful. Let
$\mathcal{S}=\\{(S_{1},r_{1}),\ldots,(S_{\ell},r_{\ell})\\}$ and let
$\vec{w}\in\\{0,1,{\small\square}\\}$. We say that $\vec{w}$ is _compatible_
with $\mathcal{S}$ if there exists a completion $\vec{w}^{*}\in\\{0,1\\}^{d}$
of $\vec{w}$, called _witness of compatibility_ , and a pair
$(S_{i},r_{i})\in\mathcal{S}$ such that $S_{i}\subseteq\Delta(\vec{w}^{*})$
and $|\Delta(\vec{w}^{*})|=r_{i}$. If $\vec{w}$ is compatible with
$\mathcal{S}$, we will denote by $\zeta^{\mathcal{S}}(\vec{w})$ the set of
witnesses of compatibility for $\vec{w}$ and $\mathcal{S}$. If $\vec{w}$ is
compatible with $\\{(S^{\prime},r^{\prime})\\}$, we simple say $\vec{w}$ is
compatible with $(S^{\prime},r^{\prime})$.

######  Lemma 11.

Let $P^{*}$ be a maximum DIAM-Cluster in $(M,k,r)$, $\mathcal{S}$ the set of
$r_{i}$-centers that properly define $P^{*}\setminus D_{M}$,
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$, let $C^{\prime}$ be the multiset
of vectors $\vec{w}$ in $M\setminus D_{M}$ with
$\zeta^{\mathcal{S}^{\prime}}(\vec{w})\neq\emptyset$ and $C$ the multiset
containing a vector $\vec{w}_{c}\in\zeta^{\mathcal{S}^{\prime}}(\vec{w})$ for
every $\vec{w}\in C^{\prime}$. Let $M^{\prime}$ be the multiset consisting of
all the vectors $\vec{w}\in M\setminus(C\cup D_{M})$ with
$\Lambda_{C}(\vec{w})\neq\emptyset$. Then there exists
$(S_{i},r_{i})\subseteq\mathcal{S}\setminus\mathcal{S}^{\prime}$ such that at
least $(|M^{\prime}|/2^{r_{\max}}-|D_{M}|)/r^{2r+1}$ vectors in $M^{\prime}$
are compatible with $(S_{i},r_{i})$.

######  Proof 3.6.

By Lemma 10, $M^{\prime}$ contains a DIAM-Cluster $P^{\prime}$ of size at
least $|M^{\prime}|/2^{r_{\max}}$ such that $C\cup P^{\prime}$ can be
completed to a DIAM-Cluster. From Lemma 9, it follows that every vector in
$P^{*}\setminus(D_{M}\cup C^{\prime})$222With a slight abuse of notation, we
will allow set operations between sets of completed and uncompleted vectors
assuming the natural bijection between completed and uncompleted vectors. is
at distance at most $r_{\max}$ to every vector in $C$ and hence it is in
$M^{\prime}$. Hence $C\cup(P^{*}\setminus(D_{M}\cup C^{\prime}))$ is a DIAM-
Cluster of size $|P^{*}\setminus D_{M}|$. Because $C\cup P^{\prime}$ can be
completed to a DIAM-Cluster, it follows from maximality of $P^{*}$ that
$|P^{*}\setminus(D_{M}\cup
C^{\prime})|\geq|P^{\prime}|-|D_{M}|\geq|M^{\prime}|/2^{r}-|D_{M}|$. But every
vector in $P^{*}\setminus(D_{M}\cup C^{\prime})$ is compatible with some
$(S_{i},r_{i})\in\mathcal{S}\setminus\mathcal{S}^{\prime}$ and
$|\mathcal{S}\setminus\mathcal{S}^{\prime}|\leq|\mathcal{S}|\leq r^{2r+1}$ and
the lemma follows.

The algorithm now enumerates all “important” sets of $r_{i}$-centers by
calling procedure FindClusters$(\\{\vec{0},\vec{u}^{*}\\},M,\emptyset)$
described in Algorithm 1.

Data: a multiset $C$ of vectors from $\\{0,1\\}^{d}$, a multiset $M$ of
vectors from $\\{0,1,{\small\square}\\}^{d}$ with at most $r_{\max}$ ones, and
a set $\mathcal{S}=\\{(S_{1},r_{1}),(S_{2},r_{2}),\ldots,(S_{q},r_{q})\\}$.
Moreover, each vector $\vec{c}\in C$ is associated with a distinct vector
$\vec{w}_{c}\in M$ such that $c$ is a completion of $\vec{w}_{c}$.

Result: A set
$\mathcal{C}=\\{(C_{1},\mathcal{S}_{1}),\ldots,(C_{\ell},\mathcal{S}_{\ell})\\}$

1 if  _$|\mathcal{S}| >r^{2r+1}$_ then

2 return $\emptyset$;

3 end if

4$\mathcal{C}=\emptyset$;

5 Let $M^{\prime}$ be the set of vectors $\vec{w}$ in $M\setminus C$ with
$\Lambda_{C}(\vec{w})\neq\emptyset$;

6 if  _$|M^{\prime}|\leq 2^{r}\cdot|D_{M}|+1$_ then

7 Add $\\{(C,\mathcal{S})\\}$ to $\mathcal{C}$;

8 end if

9foreach  _$S$ such that there exists $\vec{w}\in M^{\prime}$ with
$S\subseteq\\{i\mid\vec{w}[i]=1\vee\vec{w}[i]={\small\square}\\}$_ do

10 foreach  _$r^{\prime}\in\\{|S|,\ldots,r\\}$_ do

11 Let $V$ be the multiset of vectors $\vec{a}$ in $M^{\prime}$ with
$\zeta^{\\{(S,r^{\prime})\\}}(\vec{a})\cap\Lambda_{C}(\vec{a})\neq\emptyset$;

12 Let $V^{\prime}$ be the multiset that contains for each $\vec{a}\in V$
arbitrary one vector
$\vec{a}^{\prime}\in\zeta^{(S,r^{\prime})}(\vec{a})\cap\Lambda_{C}(\vec{a})$;

13 if  _$|V^{\prime}|\geq({|M^{\prime}|}/2^{r}-|D_{M}|)/r^{2r+1}$_ then

14 Let $\mathcal{C}=\mathcal{C}\cup\textbf{FindClusters}(C\cup
V^{\prime},M,\mathcal{S}\cup(S,r^{\prime}))$;

15 end if

16

17 end foreach

18

19 end foreach

20return $\mathcal{C}$;

21

ALGORITHM 1 The procedure FindClusters($C$, $M$, $\mathcal{S}$).

######  Lemma 12.

Let $(M,k,r)$ be an instance of Diam-Cluster-Completion. Then the procedure
FindClusters($\\{\vec{0},\vec{u}\\}$, $M\setminus D_{M}$, $\emptyset$) runs in
FPT-time parameterized by $r+\lambda(M)$.

######  Proof 3.7.

We will prove by induction on $r^{2r+1}+1-|\mathcal{S}|$ that the algorithm
FindClusters$(C\cup\\{\vec{0},\vec{u}\\},M\setminus D_{M},\mathcal{S})$ runs
in time $(r^{2r+1}\cdot
2^{4r+\lambda(M)}\cdot|D_{M}|)^{r^{2r+1}+1-|\mathcal{S}|}\cdot|M|^{3}\cdot d$.

Clearly, if $r^{2r+1}+1-|\mathcal{S}|\leq 0$ then the algorithm outputs
$\emptyset$ in constant time. Otherwise, the algorithm proceeds to computing
the set $M^{\prime}$. Note that $\vec{w}\in M\setminus D_{M}$ has at most
$\lambda(M)$ ${\small\square}$’s and at most $2^{\lambda(M)}$ completions. For
each, we can in time $\mathcal{O}(d\cdot|C|)$ verify if it is at distance at
most $r_{\max}$ to all vectors in $C$. The algorithm then continues to go over
all pairs $(S,r^{\prime})$ such that $r^{\prime}\in[r]$ and there exists
$\vec{w}\in M^{\prime}$ with
$S\subseteq\\{i\mid\vec{w}[i]=1\vee\vec{w}[i]={\small\square}\\}$. Since
$\vec{w}$ has at most $r_{\max}\leq r$ ones and at most $\lambda(M)$
${\small\square}$’s, there are at most $2^{r+\lambda(M)}\cdot|M^{\prime}|\cdot
r$ pairs $(S,r^{\prime})$. For each, we can compute sets $V$ and $V^{\prime}$
in time $\mathcal{O}(2^{\lambda(M)}\cdot|M^{\prime}|\cdot|C|)$. If
$|V^{\prime}|<(|M^{\prime}|/2^{r}-D_{M})/r^{2r+1}$, the algorithm continues to
a different choice of $(S,r^{\prime})$; otherwise, it calls the subroutine
FindClusters$(C\cup\\{\vec{0},\vec{u}\\}\cup V^{\prime},M\setminus
D_{M},\mathcal{S}\cup\\{(S,r^{\prime})\\})$. It remains to show that the
subroutine FindClusters$(C\cup\\{\vec{0},\vec{u}\\}\cup V^{\prime},M\setminus
D_{M},\mathcal{S}\cup\\{(S,r^{\prime})\\})$ is called in at most
$r^{2r+1}\cdot 2^{4r+\lambda(M)}\cdot|D_{M}|$ branches, because the running
time we get from our inductive hypothesis for
FindClusters$(C^{\prime}\cup\\{\vec{0},\vec{u}\\},M\setminus
D_{M},\mathcal{S}^{\prime})$, with $|\mathcal{S}^{\prime}|=|\mathcal{S}|+1$
dominates the running time so far.

To do so, let us fix a vector $\vec{w}\in M^{\prime}$ and let us compute in
how many sets $V$ it can appear. Vector $\vec{w}$ can appear in $V$ for some
pair $(S,r^{\prime})$ only if $\zeta^{(S,r^{\prime})}(\vec{w})\neq\emptyset$.
That can only happen if
$S\subseteq\\{i\mid\vec{w}[i]=1\vee\vec{w}[i]={\small\square}\\}$. As
$|\\{i\mid\vec{w}[i]=1\vee\vec{w}[i]={\small\square}\\}|\leq
r_{\max}+\lambda(M)$, it follows that $\vec{w}$ can appear in at most
$2^{r+\lambda(M)}$ multisets. Hence, the sum of sizes of multisets $V$ for all
pairs $(S,r^{\prime})$ is at most $2^{r+\lambda(M)}|M^{\prime}|$ and the lemma
follows by distinguishing between two cases depending on whether
$|M^{\prime}|\leq 2^{2r}|D_{M}|$ or $|M^{\prime}|>2^{2r}|D_{M}|$.

######  Lemma 13.

Let $(M,k,r)$ be an instance of Diam-Cluster-Completion and let $P^{*}$ be a
DIAM-Cluster of maximum size with $\\{\vec{0},\vec{u}\\}\subseteq P^{*}$ for
some $r$-vector $\vec{u}\in\\{0,1\\}^{d}$. Then
FindClusters($\\{\vec{0},\vec{u}\\}$, $M\setminus D_{M}$, $\emptyset$)
contains a pair $(C\cup\\{\vec{0},\vec{u}\\},\mathcal{S})$ such that
$P^{*}\setminus(D_{M}\cup\\{\vec{0},\vec{u}\\})$ is properly defined by some
superset of $\mathcal{S}$ and $C$ is a DIAM-Cluster defined by $\mathcal{S}$
of size $|P^{*}\setminus(D_{M}\cup\\{\vec{u},\vec{w}\\})|$.

######  Proof 3.8.

Let $P\subseteq M\setminus(D_{M}\cup\\{\vec{u},\vec{v}\\})$ be the multiset of
vectors that are completed to vectors in $P^{*}$, and let $\mathcal{S}$
properly define $P^{*}\setminus(D_{M}\cup\\{\vec{u},\vec{v}\\})$, and
$\mathcal{S}^{\prime}\subsetneq\mathcal{S}$. Let $C^{\prime}$ be the set of
vectors $\vec{w}$ in $P$ with
$\zeta^{\mathcal{S}^{\prime}}(\vec{w})\neq\emptyset$. We will show the
following claim that holds whenever $P\setminus C^{\prime}\neq\emptyset$.

######  Claim 1.

FindClusters($C^{*}\cup\\{\vec{u},\vec{v}\\}$, $M\setminus D_{M}$,
$\mathcal{S}^{\prime}$) for some multiset $C^{*}$ containing a vector
$\vec{w}_{c}\in\zeta^{\mathcal{S}^{\prime}}(\vec{w})$ for every $\vec{w}\in
C^{\prime}$ calls as a subroutine
FindClusters($C^{**}\cup\\{\vec{u},\vec{v}\\}$, $M\setminus D_{M}$,
$\mathcal{S}^{\prime}\cup(S_{i},r_{i})$), where
$(S_{i},r_{i})\in\mathcal{S}\setminus\mathcal{S}^{\prime}$ and $C^{**}$
contains a vector
$\vec{w}_{c}\in\zeta^{\mathcal{S}^{\prime}\cup\\{(S_{i},r_{i})\\}}(\vec{w})$
for every vector $\vec{w}\in P$ with
$\zeta^{\mathcal{S}^{\prime}\cup\\{(S_{i},r_{i})\\}}(\vec{w})\neq\emptyset$.

######  Proof 3.9 (Proof of Claim).

Let $M^{\prime}$ be the set of vectors computed on line 1. Note that every
vector in $P^{\prime}\setminus C^{\prime}$ is compatible with
$\mathcal{S}\setminus\mathcal{S}^{\prime}$ and hence by Lemma 9 it is in
$M^{\prime}$. Therefore, we will enumerate over all $r_{i}$-centers in
$\mathcal{S}\setminus\mathcal{S}^{\prime}$ on lines 1 and 1. Let $V$ and
$V^{\prime}$ be the multisets computed on lines 1 and 1, respectively. Then
$C^{\prime}\cup V$ contains all vectors $\vec{w}$ in $P$ with
$\zeta^{\mathcal{S}^{\prime}\cup\\{(S_{i},r_{i})\\}}(\vec{w})\neq\emptyset$.
Moreover, $C^{*}\cup V^{\prime}$ contains a vector
$\vec{w}_{c}\in\zeta^{\mathcal{S}^{\prime}\cup\\{(S_{i},r_{i})\\}}(\vec{w})$
for every vector $\vec{w}\in P$ with
$\zeta^{\mathcal{S}^{\prime}\cup\\{(S_{i},r_{i})\\}}(\vec{w})\neq\emptyset$.
By Lemma 11, for some
$(S_{i},r_{i})\in\mathcal{S}\setminus\mathcal{S}^{\prime}$ is
$|V^{\prime}|\geq(|M^{\prime}|/2^{r}-|D_{M}|)/r^{2r+1}$.

It follows from inductive application of Claim 1 that
FindClusters($\\{\vec{0},\vec{u}\\}$, $M\setminus D_{M}$, $\emptyset$) calls
as a subroutine FindClusters($C\cup\\{\vec{0},\vec{u}\\}$, $M\setminus D_{M}$,
$\mathcal{S}^{\prime}$), where $C$ contains a vector
$\vec{w}_{c}\in\zeta^{\mathcal{S}^{\prime}}(\vec{w})$ for every vector
$\vec{w}\in P$. It follows that
$|C|=|P|=|P^{*}\setminus(D_{M}\cup\\{\vec{0},\vec{u}\\})|$ and $C$ is by its
definition defined by $\mathcal{S}^{\prime}\subseteq\mathcal{S}$. Since
$P^{*}\setminus(D_{M}\cup\\{\vec{0},\vec{u}\\})$ is properly defined by
$\mathcal{S}$, it follows from Lemma 9 that $C$ is a DIAM-Cluster. It remains
to show that FindClusters($C\cup\\{\vec{0},\vec{u}\\}$, $M\setminus D_{M}$,
$\mathcal{S}^{\prime}$) actually adds the pair
$(C\cup\\{\vec{0},\vec{u}\\},\mathcal{S}^{\prime})$ to the output
$\mathcal{C}$ on line 1.

Let $M^{\prime}$ be the set of vectors computed on line 1. If
$|M^{\prime}|\geq 2^{r}\cdot|D_{M}|+1$, then by Lemma 10 there is a DIAM-
Cluster of size $|C\cup\\{\vec{0},\vec{u}\\}|+|D_{M}|+1>|P^{*}|$, which
contradicts the choice of $P^{*}$. Hence the condition on line 1 is satisfied
and the pair $(C,\mathcal{S})$ is added to $\mathcal{C}$.

######  Theorem 14.

Diam-Cluster-Completion is fixed-parameter tractable parameterized by
$r+\lambda(M)$.

######  Proof 3.10.

Let $(M,k,r)$ be an instance of Diam-Cluster-Completion. If
$k\leq\lambda(M)+2$, we run the algorithm from Theorem 4. Otherwise, every
maximum size DIAM-Cluster contains at least two vectors in $M\setminus D_{M}$.
Let us fix some maximum cluster $P$ in $(M,k,r)$ together with its completion
$P^{*}$. We branch over all pairs of vectors in $\vec{v},\vec{u}\in M\setminus
D_{M}$ as the two vectors completed to two vectors that are farthest apart in
$P^{*}$. We branch over all completions $\vec{u}^{*}$ and $\vec{v}^{*}$ of
vectors $\vec{u}$ and $\vec{v}$ and we normalize the instance so that
$\vec{v}^{*}=\vec{0}$. In the correct branch, it holds after normalization
that $\vec{u}^{*},\vec{0}\subseteq P^{*}$. We fix
$r_{\max}=|\Delta(\vec{u}^{*})|$. Let $\mathcal{S}$ be the set that properly
defines $P^{*}\setminus(D_{M}\cup\\{\vec{0},\vec{u}^{*}\\})$. By Lemmas 12 and
13 the procedure FindClusters($\\{\vec{0},\vec{u}\\}$, $M\setminus D_{M}$,
$\emptyset$) computes in FPT-time a set $\mathcal{C}$ of pairs of form
$(C_{i},\mathcal{S}_{i})$ such that there exists
$(C_{i},\mathcal{S}_{i})\in\mathcal{C}$ such that $|C_{i}|=|P^{*}\setminus
D_{M}|$ and some subset $\mathcal{S}^{\prime}\subseteq\mathcal{S}$ defines
$C_{i}\setminus\\{\vec{0},\vec{u}^{*}\\}$. It follows from Lemma 9 that
$C_{i}\cup(P^{*}\cap D_{M})$ is DIAM-Cluster. For each
$(C_{i},\mathcal{S}_{i})\in\mathcal{C}$, we enumerate all $2^{|D_{M}|}$
subsets of $D_{M}$. It remains to show that if $P^{*}\cap D_{M}$ is a
completion of a multiset $P_{R}\subseteq D_{M}$, we can find a completion
$P_{R}^{*}$ or $P_{R}$ such that $C_{i}\cup P_{R}^{*}$ is a DIAM-Cluster in
FPT-time. Since all sets $S^{\prime}$ with
$(S^{\prime},r^{\prime})\in\mathcal{S}_{i}$ have size at most $r$ and
$|\mathcal{S}_{i}|\leq r^{2r+1}$, it suffices to show the following claim:

######  Claim 2.

For every $\vec{w}\in P_{R}$, if coordinate $j\in[d]$ is not in
$\Delta(\vec{u})\cup\bigcup_{(S^{\prime},r^{\prime})\in\mathcal{S}_{i}}S^{\prime}$,
then we can safely set $\vec{w}[j]=0$.

######  Proof 3.11 (Proof of Claim).

Let $\vec{w}^{*}$ be the completion of $\vec{w}$ in $P^{*}$ and let
$\vec{w}^{\prime}$ be the completion of $\vec{w}$ where we set all
${\small\square}$’s in $\vec{w}$ at coordinates not in $\Delta(\vec{u})$ or
any set $S^{\prime}$ such that $(S^{\prime},r^{\prime})\in\mathcal{S}_{i}$ to
zero and set all remaining ${\small\square}$’s as in $\vec{w}^{*}$.

Let $\vec{c}\in C_{i}$ be compatible with
$(S^{\prime},r^{\prime})\in\mathcal{S}_{i}$. If $\vec{c}=\vec{u}$ or
$r^{\prime}=|S^{\prime}|$, then $\vec{w}^{*}$ and $\vec{w}^{\prime}$ are the
same on coordinates in $\Delta(\vec{c})$ and
$|\Delta(\vec{w})^{\prime}|\leq|\Delta(\vec{w})^{*}|$. Moreover, $\vec{c}$ is
also in $P^{*}$ (or some copy of $\vec{c}$) as it is the unique vector that is
compatible with $(S^{\prime},r^{\prime})\in\mathcal{S}_{i}$ and
$\mathcal{S}_{i}\subseteq\mathcal{S}$. Hence
$\delta(\vec{c},\vec{w}^{\prime})\leq r$. If $|S^{\prime}|<r^{\prime}$, then
$P^{*}$ contains a set $N$ of $r^{\prime}$-vectors of size $r+1$ such that
$\mathcal{F}=\Delta(N)$ is a sunflower with core $S^{\prime}$. Hence, by Lemma
1 there is a vector $\vec{n}\in N$ with maximum distance to $\vec{w}^{*}$
among all vectors in $\\{0,1\\}^{d}$ that contain $S^{\prime}$. It is rather
straightforward to see that
$\delta(\vec{c},\vec{w}^{\prime})\leq\delta(\vec{n},\vec{w}^{*})\leq r$.

It follows from the above claim that it suffices to branch over all
completions of $P_{R}$ that set all ${\small\square}$’s not in
$\Delta(\vec{u})\cup\bigcup_{(S^{\prime},r^{\prime})\in\mathcal{S}_{i}}S^{\prime}$
to $0$. There are at most $r^{\mathcal{O}(r^{2}|P_{R}|)}$ such completions and
the theorem follows.

###  3.3 Diam-Cluster-Completion Parameterized by $k$

In this subsection, we show that Diam-Cluster-Completion parameterized by $k$
is in XP. Moreover, we also observe in Theorem 17 that, unless W[1]=FPT, this
cannot be improved to an FPT-algorithm even for complete data.

######  Theorem 15.

Diam-Cluster-Completion is in XP parameterized by $k$.

######  Proof 3.12.

Let $(M,k,r)$ be an instance of Diam-Cluster-Completion. The algorithm works
by enumerating all potential clusters $C$ of size exactly $k$, and then uses a
reduction to an ILP instance with $f(k)$ variables to check whether $C$ can be
completed into a cluster. Since there are at most $|M|^{k}$ many potential
clusters of size exactly $k$, it only remains to show how to decide whether a
given set $C$ of exactly $k$ vectors in $M$ can be completed into a DIAM-
Cluster. Let $M_{C}$ be the submatrix of $M$ containing only the vectors in
$C$. Then $M_{C}$ has at most $3^{k}$ distinct columns, and moreover, each of
those columns can be completed in at most $2^{k}$ possible ways. Let $T$ be
the set of all columns occurring in $M_{C}$ and for a column $\vec{t}\in T$,
let $F(\vec{t})$ be the set of all possible completions of $\vec{t}$, and let
$\\#(\vec{t}\ )$ denote the number of columns in $M_{c}$ equal to $\vec{t}$.
For a vector $\vec{f}\in\\{0,1\\}^{k}$ (representing the completion of a
column), let $T(\vec{f})$ denote the subset of $T$ containing all columns
$\vec{t}$ with $\vec{f}\in F(\vec{t})$. Moreover, for every $i$ and $j$ with
$1\leq i<j\leq k$ (representing the $i$-th and the $j$-th vectors in $C$), we
denote by $FD(i,j)$ the set of all vectors (completions of columns)
$\vec{f}\in\\{0,1\\}^{k}$ such that $\vec{f}[i]\neq\vec{f}[j]$.

We are now ready to construct an ILP instance $\mathcal{I}$ with at most
$3^{k}2^{k}$ variables that is feasible if and only if $C$ can be completed
into a DIAM-Cluster. $\mathcal{I}$ has one variable $x_{\vec{t},\vec{f}}$ for
every $\vec{t}\in T$ and every $\vec{f}\in F(\vec{t})$ whose value (in a
feasible assignment) represents how many columns of type $\vec{t}$ in $M_{C}$
will be completed to $\vec{f}$. Moreover, $\mathcal{I}$ has the following
constraints:

  * •

One constraint for every $\vec{t}\in T$ stipulating that every column of type
$\vec{t}$ in $M_{C}$ is completed in some manner:

$\sum_{\vec{f}\in F(\vec{t})}x_{\vec{t},\vec{f}}=\\#(\vec{t}\ ).$

  * •

For every $i$ and $j$ with $1\leq i<j\leq k$ (representing the $i$-th and the
$j$-th vectors in $C$), one constraint stipulating that the Hamming distance
between the $i$-th and the $j$-th vectors in $C$ does not exceed $r$:

$\sum_{\vec{f}\in FD(i,j)\vec{t}\in T(\vec{f})}x_{\vec{t},\vec{f}}\leq r.$

This completes the construction of $\mathcal{I}$ and it is straightforward to
verify that $\mathcal{I}$ has a feasible assignment if and only if $C$ can be
completed to a DIAM-Cluster. Since $\mathcal{I}$ has at most $3^{k}2^{k}$
variables, and since it is well known that ILP can be solved in FPT-time
w.r.t. the number of variables [24], $\mathcal{I}$ can be solved in FPT-time
w.r.t. $k$.

Next we show that, unless FPT = W[1], we cannot get an FPT-algorithm. We start
with a generic construction that is used in several hardness proofs throughout
the paper as well.

Let $G$ be a graph, where $V(G)=\\{v_{1},\ldots,v_{n}\\}$ and $m=|E(G)|$, and
let $deg(v_{i})\leq n-1$ denote the degree of $v_{i}$ in $G$. Fix an arbitrary
ordering ${\cal O}=(e_{1},\ldots,e_{m})$ of the edges in $E(G)$. For each
vertex $v_{i}\in V(G)$, define a vector $\vec{a_{i}}\in\\{0,1\\}^{m}$ to be
the incidence/characteristic vector of $v_{i}$ w.r.t. ${\cal O}$; that is,
$\vec{a_{i}}[j]=1$ if $v_{i}$ is incident to $e_{j}$ and $\vec{a_{i}}[j]=0$
otherwise. Afterwards, expand the set of coordinates of these vectors by
adding to each of them $n(n-1)$ “extra” coordinates, $n-1$ coordinates for
each $v_{i}$, $i\in[n]$; we refer to the $n-1$ (extra) coordinates of $v_{i}$
as the “private” coordinates of $v_{i}$. For each $v_{i}$, $i\in[n]$, we will
choose a number $x_{i}\in\\{0,\ldots,n-1\\}$, where the choice of the number
$x_{i}$ will be problem dependent, and we will set $x_{i}$ many coordinates
among the private coordinates of $v_{i}$ to 1, and all other extra private
coordinates of $v_{i}$ to 0. Let $M=\\{\vec{a_{i}}\mid i\in[n]\\}$ be the set
of expanded vectors, where $\vec{a_{i}}\in\\{0,1\\}^{m+n(n-1)}$ for $i\in[n]$.
We have the following straightforward observation:

######  Observation 16.

For each $v_{i}$, where $i\in[n]$, the number of coordinates in $\vec{a_{i}}$
that are equal to 1 is exactly $deg(v_{i})+x_{i}$, and two distinct vertices
$v_{i},v_{j}$ satisfy
$\delta(\vec{a_{i}},\vec{a_{j}})=deg(v_{i})+x_{i}+deg(v_{j})+x_{j}$ if $v_{i}$
and $v_{j}$ are nonadjacent in $G$ and
$\delta(\vec{a_{i}},\vec{a_{j}})=deg(v_{i})+x_{i}+deg(v_{j})+x_{j}-2$ if
$v_{i}$ and $v_{j}$ are adjacent.

Throughout the paper, we denote by ${\cal R}$ the polynomial-time reduction
that takes as input a graph $G$ and returns the set of vectors $M$ described
above. We now complete the complexity landscape for Diam-Cluster-Completion
with the two missing lower-bounds results.

######  Theorem 17.

Diam-Cluster-Completion is W _[1]_ -hard parameterized by $k$ even if
$\lambda(M)=0$.

######  Proof 3.13.

We prove W[1]-hardness by giving a polynomial-time FPT reduction from Clique,
which is W[1]-hard [7]. Given an instance $(G,k)$ of Clique, where
$V(G)=\\{v_{1},\ldots,v_{n}\\}$, we set $x_{i}=n-1-deg(v_{i})$ for $i\in[n]$,
and apply the polynomial-time reduction ${\cal R}$ to $G$ to produce the set
of vectors $M$. The reduction from Clique to Diam-Cluster-Completion produces
the instance $(M,k,2n-4)$ of Diam-Cluster-Completion with $\lambda(M)=0$;
clearly, this reduction is a polynomial-time FPT-reduction.

By Observation 16, for any two distinct vertices $v_{i},v_{j}\in V(G)$,
$\delta(\vec{a_{i}},\vec{a_{j}})=2n-2$ if $v_{i}$ and $v_{j}$ are nonadjacent
and $\delta(\vec{a_{i}},\vec{a_{j}})=2n-4$ if $v_{i}$ and $v_{j}$ are
adjacent. The proof that $(G,k)$ is a Yes-instance of Clique iff $(M,k,2n-4)$
is a Yes-instance of Diam-Cluster-Completion is now straightforward.

We note that our second result also establishes the W[1]-hardness of Rad-
Cluster-Completion (since both problems coincide when $r=0$).

######  Theorem 18.

Diam-Cluster-Completion and Rad-Cluster-Completion are W[1]-hard parameterized
by $k$ even if $r=0$.

######  Proof 3.14.

We provide a parameterized reduction from Independent Set, which is well known
to be W[1]-complete when parameterized by the size of the sought-after set
[7]. Consider an instance $(G,k)$ of Independent Set where
$E(G)=\\{e_{1},\dotsc,e_{m}\\}$, and let us fix an arbitrary ordering $\prec$
on $V(G)$. Construct the multiset $M$ of vectors as follows: for each $v\in
V(G)$, add a vertex $\vec{v}\in\\{0,1,{\small\square}\\}^{m}$ to $M$ such that

  * •

$\vec{v}[i]={\small\square}$ if $e_{i}$ is not incident with $v$,

  * •

$\vec{v}[i]=0$ if $e_{i}=\\{u,v\\}$ is incident with $v$ and $v\prec u$, and

  * •

$\vec{v}[i]=1$ otherwise.

This completes the construction of $M$; the reduction outputs the instance
$(M,k,0)$ of Rad-Cluster-Completion (or Diam-Cluster-Completion).

For correctness, it is straightforward to verify that if $(G,k)$ is a Yes-
instance, then $M$ admits a completion $M^{*}$ and a subset $S\subseteq M^{*}$
containing at least $k$ identical vectors (indeed, the set of vectors
corresponding to an independent set $X$ in $G$ can only contain at most $1$
non-${\small\square}$ entry on each coordinate). On the other hand, if $M$
admits a completion $M^{*}$ and a subset $S\subseteq M^{*}$ containing at $k$
identical vectors, we observe that the vertices corresponding to the vectors
in $S$ must form an independent set: indeed, any edge between two such
vertices would prevent them to be completed in an identical way.

##  4 Finding a RAD-Cluster in Incomplete Data

In this section, we present our results for Rad-Cluster-Completion. We will
show that Rad-Cluster-Completion is FPT parameterized by $k+r+\lambda(M)$, and
is in XP parameterized by $r+\lambda{}$ alone. Notably, the degree of the
polynomial in the run-time of our XP algorithm grows only logarithmically in
$r$ and the algorithm can be employed to solve the Closest String with
Outliers problem [2, 3].

Before proceeding to the main contributions of this section, we observe that,
by combining the trivial branching procedure, in which we branch over all sets
of $k$ vectors from $M$ (where in each branch we proceed under the assumption
that all vectors outside of the set can be deleted), with a previous result of
Hermelin and Rozenberg [20, Theorem 2], which solves the special case of Rad-
Cluster-Completion for $k=|M|$, we obtain:

######  Observation 19.

Rad-Cluster-Completion parameterized by $k$ is in XP.

Together with the previously-established Theorem 18 (showing the W[1]-hardness
for Rad-Cluster-Completion w.r.t. $k$ even for $r=0$), this gives us an almost
complete picture of the parameterized complexity of Rad-Cluster-Completion for
any combination of the parameters $k$, $r$, $\lambda(M)$. The only two
questions that remain open are whether the XP result for $r+\lambda(M)$ can be
improved to an FPT-result (as this has been the case for Diam-Cluster-
Completion), and whether it is possible to obtain an FPT-algorithm either for
parameter $k$ or $k+\lambda(M)$. As a first step in this direction, we present
an FPT-approximation scheme for parameter $r+\lambda(M)$ in Section 4.3. The
following observation will be useful:

######  Observation 20.

Given a (complete) vector $\vec{s}\in\\{0,1\\}^{d}$, in time
$\mathcal{O}(|M|d)$ we can decide if $\vec{s}$ is the center of a Rad-Cluster
of $k$ vectors in $M$.

Observation 20 is straightforward since we can find all vectors $\vec{w}\in M$
that can be completed to a vector $\vec{w}^{*}$ at distance at most $r$ from
$\vec{s}$ by letting $\vec{w}^{*}[i]=\vec{s}[i]$ wherever
$\vec{w}^{*}[i]={\small\square}$, and then decide whether $\vec{w}^{*}$ is
such a vector by computing $\delta(\vec{w}^{*},\vec{s})$.

###  4.1 Rad-Cluster-Completion Parameterized by $k+r+\lambda(M)$.

We start by showing that, as in the case of Diam-Cluster-Completion, Rad-
Cluster-Completion parameterized by $k+r+\lambda(M)$ has a Turing kernel. The
approach is similar to that in Subsection 3.1and will, in particular, make use
of Lemma 2 and Lemma 3.

######  Theorem 21.

Rad-Cluster-Completion parameterized by $k+r+\lambda(M)$ has a Turing-kernel
containing at most $n=k3^{\lambda(M)+2r}+\lambda(M)+2$ vectors, each having at
most $\max\\{2r(n-1)+\lambda(M),\binom{\lambda(M)}{2}(2r+1)\\}$ coordinates.

######  Proof 4.1.

In the following, let $D_{M}$ be a deletion set for $M$ such that every vector
in $M\setminus D_{M}$ has at most $\lambda(M)$ missing entries. We distinguish
three cases: (1) the solution cluster contains at least two vectors in
$M\setminus D_{M}$, (2) the solution cluster contains exactly one vector in
$M\setminus D_{M}$, and (3) the solution cluster does not contain any vector
in $M\setminus D_{M}$.

We start by showing the result for case (1). Our first goal is to reduce the
number of vectors in $M\setminus D_{M}$. As a first step, we guess two vectors
$\vec{v}$ and $\vec{u}$ of $M\setminus D_{M}$ that are farthest apart in the
cluster w.r.t. to all vectors in $M\setminus D_{M}$; this is possible since we
assume that the cluster contains at least two vectors in $M\setminus D_{M}$.
We then guess the exact distance, say $t$, between $\vec{v}$ and $\vec{u}$ in
a completion leading to the cluster. Note that $t$ can be anywhere between
$\delta(\vec{v},\vec{u})$ and $\min\\{\delta(\vec{v},\vec{u})+2|D_{M}|\\}$,
but also at most $2r$. We now remove all vectors $\vec{m}$ from $M$ for which
either $\delta(\vec{v},\vec{m})>t$, $\delta(\vec{u},\vec{m})>t$, or
$|\Delta(\vec{v},\vec{m})\cap\Delta(\vec{u},\vec{m})|>t/2$. Note that this is
safe because of Lemma 2. It now follows from Lemma 3 that if
$M\setminus(D_{M}\cup\\{\vec{v},\vec{u}\\})$ contains more than
$k3^{|D_{M}|+t}$ vectors, then we can return a trivial Yes-instance of Rad-
Cluster-Completion. Otherwise, we obtain that $|M\setminus D_{M}|\leq
k3^{|D_{M}|+t}+2$. We now also need to add back the vectors in $D_{M}$.
Clearly, if a vector in $D_{M}$ differs in more than $t$ coordinates from
$\vec{v}$, it cannot be part of an RAD-Cluster containing $\vec{v}$, and we
can safely remove it from $D_{M}$. Hence every vector in $M$ now differs from
$\vec{v}$ in at most $t$ coordinates, which implies that $Z(M)\leq
t(|M|-1)+|D_{M}|$. We now remove all coordinates outside of $Z(M)$ from $M$,
since these can always be completed in the same manner for all the vectors.
Now the remaining instance is a kernel containing at most
$m=k3^{|D_{M}|+t}+2+|D_{M}|$ vectors each having at most $t(m-1)+|D_{M}|$
coordinates. This completes the proof for the case that the solution cluster
contains at least two vectors in $M\setminus D_{M}$.

In the following, let $t=2r$.

For the second case, i.e., the case that the solution cluster contains exactly
one vector in $M\setminus D_{M}$, we first guess the vector say $\vec{m}$ in
$M\setminus D_{M}$ that will be included in the solution cluster and then
remove all other vectors from $M\setminus D_{M}$. This already leaves us with
at most $|D_{M}|+1$ vectors and it only remains to reduce the number of
relevant coordinates. Because we guessed that $\vec{m}$ will be in the
solution cluster, we can now safely remove all vectors $\vec{m}^{\prime}\in
M$, with $\delta(\vec{m},\vec{m}^{\prime})>t$. Now every remaining vector
differs from $\vec{m}$ in at most $t$ coordinates and hence $Z(M)\leq
t(|D_{M}|+1)+|D_{M}|$, which gives us the desired kernel.

For the third case, i.e., the case that the solution cluster contains no
vectors in $M\setminus D_{M}$, we first remove all vectors in $M\setminus
D_{M}$. This leaves us with only $|D_{M}|$ vectors and it only remains to
reduce the number of coordinates. To achieve this, we compute a set of
coordinates that preserves the distance up to $t$ between any pair of vectors.
Namely, we compute a set $D$ of relevant coordinates starting from
$D=\emptyset$ by adding the following coordinates to $D$ for every two
distinct vectors $\vec{m}$ and $\vec{m}^{\prime}$ in $M$:

  * •

if $|\Delta(\vec{m},\vec{m}^{\prime})|\leq t$, we add
$\Delta(\vec{m},\vec{m}^{\prime})$ to $D$ and otherwise

  * •

we add an arbitrary subset of at most $t+1$ coordinates in
$\Delta(\vec{m},\vec{m}^{\prime})$ to $D$.

Let $M_{D}$ be the matrix obtained from $D$ after removing all
coordinates/columns in $D$. It is now straightforward to show that $(M,k,r)$
and $(M_{D},k,r)$ are equivalent instances of Rad-Cluster-Completion. Since
$|D|\leq\binom{|D_{M}|}{2}(t+1)$, the remaining instance has at most $|D_{M}|$
vectors each having at most $\binom{|D_{M}|}{2}(t+1)$ coordinates.

###  4.2 Rad-Cluster-Completion Parameterized by $r+\lambda(M)$

While, it is relatively easy to see that Rad-Cluster-Completion parameterized
by $r+\lambda(M)$ can be solved in time $f(\lambda(M),r)n^{\mathcal{O}(r)}$,
here we provide a more efficient algorithm by reducing the degree of the
polynomial in the run-time from $\mathcal{O}(r)$ to $\log r$. Moreover, our
algorithm can be applied to the Closest String with Outliers problem [3].

######  Theorem 22.

Rad-Cluster-Completion can be solved in time
$\mathcal{O}(|M|2^{\lambda(M)}(|M|(2^{2r}+d))^{\log r+1})$ and is therefore in
XP parameterized $r+\lambda(M)$.

######  Proof 4.2.

Note first that, by Observation 20, testing whether a vector
$\vec{c}\in\\{0,1\\}^{d}$ is a center of a solution cluster for $(M,k,r)$ can
be achieved in time $\mathcal{O}(|M|d)$. Therefore, it suffices to focus on
finding a center for the cluster.

Let $(M,k,r)$ be an instance of Rad-Cluster-Completion. If $k\leq\lambda(M)$,
then we can use the FPT-algorithm parameterized by $k+r+\lambda(M)$ implied by
Theorem 21. Otherwise, every RAD-Cluster of size at least $k$ contains at
least one vector in $M\setminus D_{M}$.

Let $F\subseteq[d]$ and let $t$ be an integer, where $0\leq t\leq r$. We say
that a vector $\vec{v}\in\\{0,1\\}^{d}$ is an _$(F,t)$ -seed_ for a center
$\vec{c}\in\\{0,1\\}^{d}$ of a solution for $(M,k,r)$ if it satisfies:

(C1)

$\vec{c}$ agrees with $\vec{v}$ on all coordinates in $F$; and

(C2)

$\vec{c}$ differs from $\vec{v}$ on at most $t$ coordinates outside of $F$.

We will show next that if $\vec{v}$ is an $(F,t)$-seed for $\vec{c}$, then
either $\vec{v}$ is the center of a solution for $(M,k,r)$, or there is a
vector $\vec{m}\in M$ with $r<\delta(\vec{v},\vec{m})\leq 2r$ and a subset
$C\subset D\setminus F$, where $D=\Delta(\vec{v},\vec{m})$, such that the
vector $\vec{v}^{\prime}$ obtained from $\vec{v}$ by complementing all
coordinates in $C$ is an $(F\cup D,t/2)$-seed for $\vec{c}$.

Towards showing the claim, let $\vec{v}$ be an $(F,t)$-seed for some center
$\vec{c}$ of a solution. Note that if $\vec{v}$ is not yet the center of a
solution, then the solution with center $\vec{c}$ must contain a vector
$\vec{m}\in M$ such that $r<\delta(\vec{v},\vec{m})$ and
$\delta(\vec{m},\vec{c})\leq r$, and hence, $\delta(\vec{v},\vec{m})\leq 2r$.
Let $C$ be the subset of coordinates in $D\setminus F$, on which $\vec{c}$ and
$\vec{v}$ differ, and let $\vec{v}^{\prime}$ be the vector obtained from
$\vec{v}$ by complementing the values of the coordinates in $C$. Then
$\vec{c}$ agrees with $\vec{v}^{\prime}$ on all coordinates in $F\cup D$.
Moreover, since $\vec{v}$ differs from $\vec{c}$ in at most $t$ coordinates,
it follows that $\vec{v}^{\prime}$ differs from $\vec{c}$ in at most $t-|C|$
coordinates. In addition, $\vec{v}^{\prime}$ differs from $\vec{c}$ in at most
$r-(|D|-|C|)\leq|C|-1$ coordinates; this is true since $\vec{c}$ differs from
$\vec{m}$ in at least $|D|-|C|$ and at most $r$ coordinates. Therefore,
$\vec{v}^{\prime}$ differs from $\vec{c}$ in at most
$\min\\{t-|C|,|C|-1\\}\leq t/2$ coordinates, implying that $\vec{v}^{\prime}$
is a $(F\cup D,t/2)$-seed for $\vec{c}$.

Now suppose that we are given a vector $\vec{v}\in\\{0,1\\}^{d}$ that is an
$(F,t)$-seed for the center $\vec{c}$ of a solution for $(M,k,r)$, and such
that $\vec{v}$ itself is not the center of a solution for $(M,k,r)$. Then, the
above claim shows us how to compute in time $\mathcal{O}(|M|d2^{2r})$ a set
$V^{\prime}\subseteq\\{0,1\\}^{d}$ of at most $|M|2^{2r}$ vectors, that
contains a vector $\vec{v}^{\prime}$ that is an $(F^{\prime},t/2)$-seed for
$\vec{c}$ for some $F^{\prime}$ satisfying $F\subseteq F^{\prime}$. This
procedure can now be used within a recursive procedure
findCenter$(\vec{v},F,t)$ that given $\vec{v}$, $F$, and $t$ does the
following. It first checks in time $\mathcal{O}(|M|d)$ whether $\vec{v}$ is
already the center of a solution for $(M,k,r)$. If so, it returns $\vec{v}$;
otherwise it branches on the vectors in $V^{\prime}$ and calls itself
recursively using the call findCenter$(\vec{v}^{\prime},F^{\prime},t/2)$ for
every vector $\vec{v}^{\prime}\in V^{\prime}$ and some $F\subseteq
F^{\prime}$, and returns the center of a solution returned by one of those
recursive calls, or rejects if all recursive calls reject. This way
findCenter$(\vec{v},F,t)$ is guaranteed to return the center of a solution as
long as $\vec{v}$ is a $(F,t)$-seed for $\vec{c}$. Moreover, since the
recursion depth of findCenter$(\vec{v},F,t)$ is at most $\log t$, it runs in
time $\mathcal{O}(|M|(2^{2r}+d)(|M|2^{2r})^{\log
t})=\mathcal{O}((|M|(2^{2r}+d))^{\log t+1})$.

Now suppose that $(M,k,r)$ has a solution with center $\vec{c}$. Since the
solution contains at least one vector from $M\setminus D_{M}$, there is a
vector $\vec{v}^{\prime}\in M\setminus D_{M}$ and a completion $\vec{v}$ of
$\vec{v}^{\prime}$ such that $\delta(\vec{v},\vec{c})\leq r$. The vector
$\vec{v}$ is a $(\emptyset,r)$-seed for $\vec{c}$ and calling
findCenter$(\vec{v},\emptyset,r)$ will return a center for a solution in time
$\mathcal{O}((|M|(2^{2r}+d))^{\log t+1})$. Since every center $\vec{c}$ of a
solution is within the $r$-neighborhood of some completed vector in
$M\setminus D_{M}$, we can now decide in time
$\mathcal{O}(|M|2^{\lambda(M)}(|M|(2^{2r}+d))^{\log t+1})$ whether $(M,k,r)$
has a solution (and if so return a center) by calling
findCenter$(\vec{v},\emptyset,r)$ for every completion $\vec{v}$ of every
vector $\vec{v}^{\prime}\in M\setminus D_{M}$.

We note that the algorithm provided by the above theorem generalizes a
previous algorithm of Marx [27, Lemma 3.2] for Closest Substring to strings
that may contain unknown characters. In particular, it lifts the concept of
“generators” to strings with unknown characters by showing that there are
$\log r$ vectors that can be computed efficiently and that define at most
$r\log r$ “important” coordinates for the center of some solution.

###  4.3 FPT Approximation Scheme Parameterized by $r+\lambda(M)$

In this subsection we give an algorithm that, for a given instance $(M,k,r)$
of Rad-Cluster-Completion and $\varepsilon\in\mathbb{R}$, where
$0<\varepsilon<1$, computes in FPT-time parameterized by
$r+\lambda(M)+\frac{1}{\varepsilon}$ a center of a Rad-cluster of size at
least $(1-\varepsilon)k$, or it correctly concludes that no RAD-Cluster of
size $k$ exists.

The algorithm starts by performing a similar branching and pre-processing to
the FPT algorithm for Diam-Cluster-Completion parameterized by $r+\lambda(M)$.
Fix $M^{*}$ to be a completion of $M$ that contains a maximum size RAD-
Cluster, let $P^{*}$ be such a maximum size RAD-Cluster in $M^{*}$, and let
$\vec{s}^{*}$ be a center of $P^{*}$. The goal of the algorithm is to find
$\vec{s}^{*}$, as given $\vec{s}^{*}$, by Observation 20, we can decide the
instance in time $\mathcal{O}(|M|d)$.

If $k<\frac{2\lambda(M)}{\varepsilon}+2$, then we use the algorithm in Theorem
21 to obtain a Turing kernel; since the vectors in the Turing kernel have
their dimension bounded by a function of the parameter, we can enumerate all
possible centers of the RAD-Cluster to solve every sub-instance of the Turing
kernel. Now we can assume that $k\geq\frac{2\lambda(M)}{\varepsilon}+2$. We
first observe that $|P^{*}\setminus D_{M}|$ contains at least two vectors
(recall that $D_{M}$ denotes the $\lambda(M)$-deletion set in $M$). We now
guess two vectors $\vec{u}$ and $\vec{v}$ in $M\setminus D_{M}$, together with
their respective completions $\vec{u}^{*}$ and $\vec{v}^{*}$, such that both
$\vec{u}^{*}$ and $\vec{v}^{*}$ are in $P^{*}$ and are the farthest vectors
apart in $P^{*}\setminus D_{M}$; fix
$r_{\max}=\delta(\vec{v}^{*},\vec{u}^{*})$. Note that $r_{\max}\leq 2r$. Since
there are at most $|M|^{2}$ pairs of vectors in $M\setminus D_{M}$ and each
has at most $\lambda(M)$ missing entries, there are at most
$2^{2\lambda(M)}|M|^{2}$ possible pairs of $\vec{u}^{*}$ and $\vec{v}^{*}$,
and our algorithm enumerates all these pairs. What we describe from now on
assumes that the guess of $\vec{u}^{*}$ and $\vec{v}^{*}$ is correct. We
normalize all the vectors in $M$ so that $\vec{v}^{*}$ becomes the all-zero
vector, i.e., we replace $\vec{v}^{*}$ by the all-zero vector, and for every
other vector $\vec{w}\neq\vec{v}^{*}$, we replace it with the vector
$\vec{w}^{\prime}$ such that $\vec{w}^{\prime}[i]=0$ if
$\vec{v}^{*}[i]=\vec{w}[i]$, $\vec{w}^{\prime}[i]={\small\square}$ if
$\vec{w}[i]={\small\square}$, and $\vec{w}^{\prime}[i]=1$, otherwise. Finally,
for each vector $\vec{w}\in M$, we can in time $r_{\max}\cdot d$, where $d$ is
the dimension of the vectors in $M$, check if there is a completion
$\vec{w}^{*}$ of $\vec{w}$ such that the distance from $\vec{w}^{*}$ to both
$\vec{v}^{*}$ and $\vec{u}^{*}$ is at most $r_{\max}$. This is because we can
always set $\vec{w}^{*}[i]=0$ for all $i\in[d]\setminus\Delta(\vec{u}^{*})$
such that $\vec{w}^{*}[i]={\small\square}$, since in that case
$\vec{v}^{*}[i]=\vec{u}^{*}[i]=0$ and we are looking for a completion that is
close to both $\vec{v}^{*}$ and $\vec{u}^{*}$. Hence, to decide if there is
such completion, we only need to decide how many coordinates of $\vec{w}^{*}$
in $\Delta(\vec{u}^{*})$ we need to set to $0$ and how many we need to set to
$1$. We can now remove all vectors $\vec{w}$ that cannot be completed to a
vector of distance at most $r_{\max}$ from both $\vec{v}^{*}$ and
$\vec{u}^{*}$. Note here that some vectors in $P^{*}\cap D_{M}$ might be
further away from $\vec{v}^{*}$ or $\vec{u}^{*}$ and they could have been
removed from $M$ at this step. However, since
$k\geq\frac{2\lambda(M)}{\varepsilon}+2$, we have
$\lambda(M)\leq\frac{\varepsilon}{2}k$ and, if our guess of $\vec{v}^{*}$ and
$\vec{u}^{*}$ is correct, we did not remove any vector from $P^{*}\setminus
D_{M}$. Hence, after the preprocessing, $M$ contains a RAD-Cluster with center
$\vec{s}^{*}$ and at least $k^{\prime}=(1-\frac{\varepsilon}{2})k$ vectors.
Our goal is to find a center for a RAD-Cluster with at least
$(1-\frac{\varepsilon}{2})k^{\prime}=(1-\frac{\varepsilon}{2})^{2}k\geq(1-\varepsilon)k$
vectors. For ease of exposition, we let
$\varepsilon^{\prime}=\frac{\varepsilon}{2}$ and we let
$k^{\prime}\geq(1-\varepsilon^{\prime})k$ be the number of vectors of $P^{*}$
still in $M$.

######  Lemma 23.

After the above pre-processing, in time $\mathcal{O}(2^{r_{\max}}\cdot|M|)$,
we can find a center for a RAD-Cluster of size $\frac{|M|}{2^{r_{\max}}}$.

######  Proof 4.3.

The lemma follows rather straightforwardly from the following claim.

######  Claim 3.

For every vector $\vec{w}\in M$ it holds that
$|\Delta(\vec{w})\setminus\Delta(\vec{u}^{*})|\leq r$.

######  Proof 4.4 (Proof of Claim).

Let $\vec{w}^{*}$ be a completion of $\vec{w}$ such that $\vec{w}^{*}$ is at
distance at most $r_{\max}$ from both $\vec{u}^{*}$ and $\vec{v}^{*}$. Notice
that
$\Delta(\vec{w})\setminus\Delta(\vec{u}^{*})\subseteq\Delta(\vec{w}^{*})\setminus\Delta(\vec{u}^{*})$;
hence
$|\Delta(\vec{w})\setminus\Delta(\vec{u}^{*})|\leq|\Delta(\vec{w}^{*})\setminus\Delta(\vec{u}^{*})|$,
and it suffices to show that
$|\Delta(\vec{w}^{*})\setminus\Delta(\vec{u}^{*})|\leq r$.

Now $\vec{w}^{*}$ is at distance at most $r_{\max}$ from $\vec{v}^{*}$, and
hence we have $\delta(\vec{w}^{*},\vec{v}^{*})\leq r_{\max}$ and
$\Delta(\vec{v}^{*})=\emptyset$. It follows that
$|\Delta(\vec{w}^{*})\setminus\Delta(\vec{u}^{*})|+|\Delta(\vec{w}^{*})\cap\Delta(\vec{u}^{*})|\leq
r_{\max}.$ Similarly, $\vec{w}^{*}$ is at distance at most $r_{\max}$ from
$\vec{u}^{*}$, i.e., $\delta(\vec{w}^{*},\vec{u}^{*})\leq r_{\max}$, and
$|\Delta(\vec{w}^{*})\setminus\Delta(\vec{u}^{*})|+|\Delta(\vec{u}^{*})\setminus\Delta(\vec{w}^{*})|\leq
r_{\max}.$ Combining the two inequalities, we get
$2|\Delta(\vec{w}^{*})\setminus\Delta(\vec{u}^{*})|+|\Delta(\vec{u}^{*})\cap\Delta(\vec{w}^{*})|+|\Delta(\vec{u}^{*})\setminus\Delta(\vec{w}^{*})|\leq
2r_{\max}.$ Since
$|\Delta(\vec{u}^{*})\cap\Delta(\vec{w}^{*})|+|\Delta(\vec{u}^{*})\setminus\Delta(\vec{w})|=|\delta(\vec{v}^{*},\vec{u}^{*})|=r_{\max},$
we have
$|\Delta(\vec{w}^{*})\setminus\Delta(\vec{u}^{*})|\leq\frac{r_{\max}}{2}\leq
r.$

We can now branch over all possible subsets $T$ of $\Delta(\vec{u}^{*})$, and
for each such subset, try as the center the vector $\vec{s}^{*}_{T}$ such that
$\Delta(\vec{s}^{*}_{T})=T$ and compute the set of all vectors at distance at
most $r$ from $\vec{s}^{*}_{T}$. To prove the lemma, it remains to show that
every vector in $M$ can be completed to a vector at distance at most $r$ from
at least one of $2^{r_{\max}}$ vectors $\vec{s}^{*}_{T}$. Let $\vec{w}$ be a
vector in $M$ that can be completed to a vector $\vec{w}^{*}$ with
$\Delta(\vec{w}^{*})\cap\Delta(\vec{u}^{*})=T$ for some
$T\subseteq\Delta(\vec{u}^{*})$ . Now let $\vec{w}^{*}$ be such completion of
$\vec{w}$ that $\Delta(\vec{w}^{*})\cap\Delta(\vec{u}^{*})=T$ and
$\vec{w}^{*}[i]=0$ for all $i\in[d]\setminus\Delta(\vec{u}^{*})$ such that
$\vec{w}[i]={\small\square}$. It follows from the claim that $\vec{w}^{*}$ is
at distance at most $r$ from $\vec{s}^{*}_{T}$.

Therefore, we can assume henceforth that
$k^{\prime}\geq\frac{|M|}{2^{r_{\max}}}$; otherwise, Lemma 23 computes a RAD-
Cluster of size at least $k^{\prime}$. Now the algorithm sets
$\vec{s}^{*}_{0}=\vec{v}^{*}=\vec{0}$ and the goal is to iteratively compute
$\vec{s}^{*}_{1},\vec{s}^{*}_{2},\vec{s}^{*}_{3},\ldots,\vec{s}^{*}_{r^{\prime}}$,
$r^{\prime}\leq r$, such that:

  1. 1.

for all $i\in[r^{\prime}]$, we have
$\Delta(\vec{s}^{*}_{i})=\Delta(\vec{s}^{*}_{i-1})\cup\\{c_{i}\\}$ for some
coordinate $c_{i}\in\Delta(\vec{s}^{*})\setminus\Delta(\vec{s}^{*}_{i-1})$;

  2. 2.

for all $j\in[r^{\prime}-1]$, the number of vectors at distance at most $r$
from $\vec{s}^{*}_{j}$ is less than $(1-\varepsilon^{\prime})k^{\prime}$; and

  3. 3.

the number of vectors at distance at most $r$ from $\vec{s}^{*}_{r^{\prime}}$
is at least $(1-\varepsilon^{\prime})k^{\prime}$.

Let $\vec{s}^{*}_{i}$ be such that
$\Delta(\vec{s}^{*}_{i})\subseteq\Delta(\vec{s}^{*})$ for some
$i\in[r^{\prime}-1]$. The number of vectors at distance at most $r$ from
$\vec{s}^{*}_{i}$, $i<r^{\prime}$, is less than
$(1-\varepsilon^{\prime})k^{\prime}$. This means that at least
$\varepsilon^{\prime}k^{\prime}\geq\frac{\varepsilon^{\prime}|M|}{2^{r_{\max}}}$
vectors whose completions are in $P^{*}$ are at distance at least $r+1$ from
$\vec{s}^{*}_{i}$. For every such vector $\vec{w}$, it is easy to see that
since $\Delta(\vec{s}^{*}_{i})\subseteq\Delta(\vec{s}^{*})$, it must be the
case that
$(\Delta(\vec{s}^{*})\cap\Delta(\vec{w}))\setminus\Delta(\vec{s}^{*}_{i})$ is
not empty. Note that $|\Delta(\vec{s}^{*})|\leq r$, and hence there exists
$c_{i+1}\in\Delta(\vec{s}^{*})$ such that, for at least
$\frac{\varepsilon^{\prime}|M|}{2^{r_{\max}}\cdot r}$ vectors $\vec{w}$ in $M$
at distance at least $r+1$ from $\vec{s}^{*}_{i}$, it holds that
$c_{i+1}\in\Delta(\vec{w})$. Moreover, for every vector $\vec{w}\in M$, we
have $|\Delta(\vec{w})|\leq r_{\max}$. It follows–by a straightforward
counting argument–that there are at most $\frac{2^{r_{\max}}\cdot
r}{\varepsilon}\cdot r_{\max}$ coordinates $c\in[d]$ such that, for at least
$\frac{\varepsilon^{\prime}|M|}{2^{r_{\max}}\cdot r}$ vectors $\vec{w}$, it
holds that $c\in\Delta(\vec{w})$. Therefore, to obtain $\vec{s}^{*}_{i+1}$
such that $\Delta(\vec{s}^{*}_{i+1})\subseteq\Delta(\vec{s}^{*})$, we only
need to branch on one of at most $\frac{2^{r_{\max}}\cdot r}{\varepsilon}\cdot
r_{\max}$ coordinates. By exhaustively branching on the coordinates that are
set to 1 in at least $\frac{\varepsilon^{\prime}|M|}{2^{r_{\max}}\cdot r}$
many vectors in $M$, until either the number of vectors at distance at most
$r$ from $\vec{s}^{*}_{i}$ is at least $(1-\varepsilon^{\prime})k^{\prime}$ or
$i\geq r$, we get:

######  Theorem 24.

Given an instance $(M,k,r)$ of Rad-Cluster-Completion and
$\varepsilon\in\mathbb{R}$, where $0<\varepsilon<1$, there exists an FPT
algorithm $\mathcal{A}$, parameterized by
$r+\lambda(M)+\frac{1}{\varepsilon}$, such that $\mathcal{A}$ either computes
a RAD-Cluster of size at least $(1-\varepsilon)k$, or correctly concludes that
$M$ does not contain a RAD-Cluster of size $k$.

######  Proof 4.5.

The initial phase of the algorithm either computes a RAD-Cluster of size at
least $k$ if $k<\frac{2\lambda(M)}{\varepsilon}+2$, or branches into at most
$2^{2\lambda(M)}|M|^{2}$ many branches. Afterwards, the algorithm pre-
processes every branch such that in each branch we can either compute a center
for a RAD-Cluster of size at least $k^{\prime}\geq
k-\lambda(M)\geq(1-\frac{\varepsilon}{2})k$ in time
$\mathcal{O}(2^{r_{\max}}|M|)$ by Lemma 23, or we end up in an instance
$(M^{\prime},k^{\prime},r)$ such that $k^{\prime}\geq\frac{|M|}{2^{r_{\max}}}$
and $|\Delta(\vec{w})|\leq r_{\max}$ for all $\vec{w}\in M$. Moreover, we can
assume that there exists a maximum size cluster RAD-Cluster $P^{*}$ in
$M^{\prime}$ with $\vec{0}\in P^{*}$. Note that
$k^{\prime}\geq(1-\frac{\varepsilon}{2})k$ and a center of RAD-Cluster of size
$k^{\prime}$ in $M^{\prime}$ can be straightforwardly transformed to a center
of RAD-Cluster of size $k^{\prime}$ in $M$.

From now on the algorithm is rather simple. It starts with
$s^{*}_{0}=\vec{0}$. Now for each $i\in\\{0,\ldots,r\\}$ it either concludes
that $s^{*}_{i}$ is a good enough center or it branches in at most
$\frac{2^{r_{\max}}\cdot r}{\varepsilon}\cdot r_{\max}$ possibilities for
$s^{*}_{i+1}$ with $|\Delta(s^{*}_{i+1})|=i+1$ as follows.

  1. 1.

It first computes the set $P_{i}$ of all vectors in $M$ at distance at most
$r$ from $\vec{s}^{*}_{i}$. This can be done in $\mathcal{O}(|M|d)$ time,
where $d$ is the dimension of the vectors in $M$.

  2. 2.

If this set has size at least $(1-\varepsilon^{\prime})k^{\prime}$, it outputs
as the center the vector $\vec{s}^{*}_{i}$ and stops.

  3. 3.

Now, if $i=r$ and we did not find a good center, then any center containing
$\vec{s}^{*}_{r}$ would be too far from $\vec{0}$, so the algorithm outputs
Fail and stops.

  4. 4.

Otherwise it branches over all coordinates
$c\in[d]\setminus\Delta(\vec{s}^{*}_{i})$ it computes the set
$W\subseteq(M\setminus P_{i})$ of all vectors $\vec{w}$ with distance at least
$r+1$ from $\vec{s}^{*}_{i}$ and $c\in\Delta(\vec{w})$.

    1. (a)

If $|W|\geq\frac{\varepsilon^{\prime}|M|}{2^{r_{\max}}\cdot r}$, then the
algorithm branches on letting $\vec{s}^{*}_{i+1}$ be the vector such that
$\vec{s}^{*}_{i+1}[c]=1$ and $\vec{s}^{*}_{i+1}[j]=\vec{s}^{*}_{i}[j]$ for all
$j\neq c_{i}$.

    2. (b)

If $|W|<\frac{\varepsilon^{\prime}|M|}{2^{r_{\max}}\cdot r}$, discard the
current choice of $c$.

The above algorithm is a branching algorithm, where the maximum number of
branches at each node is $\frac{2^{r_{\max}}\cdot r}{\varepsilon}\cdot
r_{\max}$ and the branching depth is $r$. Otherwise, the algorithm runs in
polynomial time in every branching node. Hence the total running time of the
algorithm is $(\frac{2^{r_{\max}}\cdot r}{\varepsilon}\cdot
r_{\max})^{r}\cdot|M|^{\mathcal{O}(1)}$. If the algorithm outputs a vector
$\vec{s}^{*}_{i}$, then there are at least
$(1-\varepsilon^{\prime})k^{\prime}$ vectors in $M^{\prime}$ at distance at
most $r$ from $\vec{s}^{*}_{i}$. On the other hand, if there is RAD-Cluster
$P^{*}$ of size at least $k^{\prime}$ with center $\vec{s}^{*}$ such that
$\vec{0}\in P^{*}$, then
$\Delta(\vec{s}^{*}_{0})=\emptyset\subseteq\Delta(\vec{s}^{*})$,
$|\Delta(\vec{s}^{*})|\geq r$, and for every vector $\vec{s}^{*}_{i}$ with
$\Delta(\vec{s}^{*}_{i})\subseteq\Delta(\vec{s}^{*})$ we already argued that
there exists $c_{i+1}\in\Delta(\vec{s}^{*})\setminus\Delta(\vec{s}^{*}_{i})$
such that for at least $\frac{\varepsilon^{\prime}|M|}{2^{r_{\max}}\cdot r}$
vectors $\vec{w}$ in $M$ at distance at least $r+1$ from $\vec{s}^{*}_{i}$ it
holds $c_{i+1}\in\Delta(\vec{w})$. Hence the node with $\vec{s}^{*}_{i}$
contains a branch with center $\vec{s}^{*}_{i+1}$ such that
$\Delta(\vec{s}^{*}_{i+1})\subseteq\Delta(\vec{s}^{*})$. If
$\Delta(\vec{s}^{*}_{i})\subseteq\Delta(\vec{s}^{*})$ and
$i=|\Delta(\vec{s}^{*})|$, then $\vec{s}^{*}_{i}=\vec{s}^{*}$ and there are
$k^{\prime}$ vectors at distance at most $r$ from $\vec{s}^{*}_{i}$. It
follows that if $(M^{\prime},k^{\prime},r)$ is a Yes-instance, then the above
algorithm indeed outputs some vector $\vec{s}^{*}_{i}$ with at least
$(1-\varepsilon^{\prime})k^{\prime}$ vectors from $M^{\prime}$ at distance at
most $r$ from $\vec{s}^{*}_{i}$.

##  5 Concluding Remarks

We studied the parameterized complexity of two fundamental problems pertaining
to incomplete data that have applications in data analytics. In most cases, we
were able to provide a complete landscape of the parameterized complexity of
the problems w.r.t. the parameters under consideration. It is worth noting
that all algorithmic upper bounds obtained in this paper can also be directly
generalized to vectors (i.e., matrices) over a domain whose size is bounded by
the parameter value by using the encoding described by Eiben et al. [9].

Two important open questions ensue from our work, namely determining the
parameterized complexity of Rad-Cluster-Completion w.r.t. each of the two
parameterizations $k+\lambda$ and $r+\lambda$. In particular, the restrictions
of these two problems to complete data (i.e., $\lambda=0$) remain open, and
result in two important questions about the parameterized complexity of Rad-
Cluster parameterized by the cluster size $k$ or by the cluster radius $r$.

## References

  * [1] Laura Balzano, Arthur Szlam, Benjamin Recht, and Robert D. Nowak.  $k$-subspaces with missing data.  2012 IEEE Statistical Signal Processing Workshop (SSP), pages 612–615, 2012.
  * [2] Christina Boucher and Bin Ma.  Closest string with outliers.  BMC Bioinformatics, 12(S-1):S55, 2011.
  * [3] Laurent Bulteau and Markus L. Schmid.  Consensus strings with small maximum distance and small distance sum.  Algorithmica, 82(5):1378–1409, 2020.
  * [4] Sergio Cabello, Panos Giannopoulos, Christian Knauer, Dániel Marx, and Günter Rote.  Geometric clustering: Fixed-parameter tractability and lower bounds with respect to the dimension.  ACM Trans. Algorithms, 7(4):43:1–43:27, 2011.
  * [5] Moses Charikar and Rina Panigrahy.  Clustering to minimize the sum of cluster diameters.  Journal of Computer and System Sciences, 68(2):417 – 441, 2004\.
  * [6] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [7] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.
  * [8] M.E Dyer and A.M Frieze.  A simple heuristic for the $p$-centre problem.  Oper. Res. Lett., 3(6):285–288, 1985.
  * [9] Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider.  The parameterized complexity of clustering incomplete data.  In The Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, pages 7296–7304. AAAI Press, 2021.
  * [10] Ehsan Elhamifar.  High-rank matrix completion and clustering under self-expressive models.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 73–81. Curran Associates, Inc., 2016.
  * [11] Ehsan Elhamifar and René Vidal.  Sparse subspace clustering: Algorithm, theory, and applications.  IEEE Trans. Pattern Anal. Mach. Intell., 35(11):2765–2781, 2013\.
  * [12] Tomás Feder and Daniel Greene.  Optimal algorithms for approximate clustering.  In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, pages 434–444. ACM, 1988.
  * [13] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory, volume XIV of Texts in Theoretical Computer Science. An EATCS Series.  Springer, Berlin, 2006.
  * [14] M. Frances and A. Litman.  On covering problems of codes.  Theory of Computing Systems, 30(2):113–119, 1997.
  * [15] Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider.  Parameterized algorithms for the matrix completion problem.  In ICML, volume 80 of JMLR Workshop and Conference Proceedings, pages 1642–1651, 2018.
  * [16] Leszek Ga̧sieniec, Jesper Jansson, and Andrzej Lingas.  Efficient approximation algorithms for the Hamming center problem.  In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 905–906, 1999.
  * [17] Leszek Ga̧sieniec, Jesper Jansson, and Andrzej Lingas.  Approximation algorithms for Hamming clustering problems.  Journal of Discrete Algorithms, 2(2):289 – 301, 2004.
  * [18] Teofilo F. Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theoretical Computer Science, 38:293 – 306, 1985.
  * [19] Jens Gramm, Rolf Niedermeier, and Peter Rossmanith.  Fixed-parameter algorithms for CLOSEST STRING and related problems.  Algorithmica, 37(1):25–42, 2003.
  * [20] Danny Hermelin and Liat Rozenberg.  Parameterized complexity analysis for the closest string with wildcards problem.  Theoretical Computer Science, 600:11–18, 2015.
  * [21] Tomohiro Koana, Vincent Froese, and Rolf Niedermeier.  Parameterized algorithms for matrix completion with radius constraints.  In Inge Li Gørtz and Oren Weimann, editors, 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark, volume 161 of LIPIcs, pages 20:1–20:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [22] Tomohiro Koana, Vincent Froese, and Rolf Niedermeier.  Binary matrix completion under diameter constraints.  In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 47:1–47:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [23] Stefan Kratsch, Dániel Marx, and Magnus Wahlström.  Parameterized complexity and kernelizability of max ones and exact ones problems.  TOCT, 8(1):1:1–1:28, 2016.
  * [24] H. W. Lenstra and Jr.  Integer programming with a fixed number of variables.  Math. Oper. Res., 8(4):538–548, 1983.
  * [25] Ming Li, Bin Ma, and Lusheng Wang.  On the closest string and substring problems.  J. ACM, 49(2):157–171, 2002.
  * [26] Dániel Marx.  Parameterized complexity of constraint satisfaction problems.  Computational Complexity, 14(2):153–183, 2005.
  * [27] Dániel Marx.  Closest substring problems with small distances.  SIAM J. Comput., 38(4):1382–1410, 2008.
  * [28] J. Yi, T. Yang, R. Jin, A. K. Jain, and M. Mahdavi.  Robust ensemble clustering by matrix completion.  In 2012 IEEE 12th International Conference on Data Mining, pages 1176–1181, 2012.