# Inapproximability of Maximum Diameter Clustering for Few Clusters

Henry Fleischmann
University of Cambridge  Kyrylo Karlov
Charles University  Karthik C. S.
Rutgers University  Ashwin Padaki
Columbia University  Stepan Zharkov
Stanford University

###### Abstract

We consider the $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ clustering problem,
where the goal is to partition a set of points in a metric space into $k$
clusters, minimizing the maximum distance between any two points in the same
cluster. In general metrics, $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ is known
to be $\mathsf{NP}$-hard, while it has a $2$-approximation algorithm [Gon85].
Complementing this algorithm, it is known that
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ is $\mathsf{NP}$-hard to approximate
within a factor better than $2$ in the $\ell_{1}$ and $\ell_{\infty}$ metrics,
and within a factor of $1.969$ in the $\ell_{2}$ metric [FG88].

When $k\geq 3$ is fixed, $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ remains
$\mathsf{NP}$-hard to approximate within a factor better than $2$ in the
$\ell_{\infty}$ metric [Meg90]. However, its approximability in this setting
has not previously been studied in the $\ell_{1}$ and $\ell_{2}$ metrics,
though a $1.415$-approximation algorithm in the $\ell_{2}$ metric follows from
a known result [BHPI02]. In this paper, we address the remaining gap by
showing new hardness of approximation results that hold even when $k=3$.
Specifically, we prove that $\mathsf{Max}$-$3$-$\mathsf{Diameter}$ is
$\mathsf{NP}$-hard to approximate within a factor better than $1.5$ in the
$\ell_{1}$ metric, and within a factor of $1.304$ in the $\ell_{2}$ metric.

##  1 Introduction

The $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ problem is the task of optimizing a
classic clustering objective, where given a set of points in a metric space,
we are required to partition the points into $k$ clusters so as to minimize
the maximum distance between any two points in the same cluster (see Section 2
for a formal definition). One of the main advantages of
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ over clustering objectives such as
$k$-$\mathsf{center}$, $k$-$\mathsf{means}$, and $k$-$\mathsf{median}$ is that
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ is not center-based, and thus one does
not have to worry about the quality of centers in the applications of this
clustering objective.

By the early 1980s, the $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ problem was
known to be $\mathsf{NP}$-complete even in the Euclidean plane (implicit in
[FPT81]). Thus, the attention of the community turned towards understanding
it’s approximability in various metric spaces. There were a series of works
all providing 2-approximation to the $\mathsf{Max}$-$k$-$\mathsf{Diameter}$
problem in general metrics with improved polynomial runtimes [HS85, HS86,
Gon85, FG88]. Hochbaum and Shmoys [HS86] showed that this factor cannot be
improved (assuming $\mathsf{P}$$\neq$$\mathsf{NP}$) for general metrics. Thus,
the focus shifted to $\ell_{p}$-metrics.

Gonzalez [Gon85] showed that the $\mathsf{Max}$-$k$-$\mathsf{Diameter}$
problem in the $\ell_{2}$ metric is $\mathsf{NP}$-hard to approximate within a
factor of 1.733. This was improved by Feder and Greene [FG88] who showed that
the $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ problem in the Euclidean metric is
$\mathsf{NP}$-hard to approximate within a factor of 1.969. Moreover, they
showed that the $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ problem is
$\mathsf{NP}$-hard to approximate within a factor better than 2 in both the
$\ell_{1}$ and $\ell_{\infty}$ metrics. It is worth noting that the results by
Feder and Greene hold even when the input is in $\mathbb{R}^{2}$.

At first glance, it looks like we have hit a road block. The approximability
of the $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ problem is completely understood
in general metrics, as well as the $\ell_{1}$ and $\ell_{\infty}$ metrics; the
small gap in our knowledge is about $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in
the $\ell_{2}$ metric. However, much like other Euclidean clustering problems
(such as Euclidean $k$-$\mathsf{center}$ [FG88, Men88]), this has been open
for decades with no real tools of attack to bridge the gap in approximability.

Over the last two and half decades, the algorithmic community has invested a
lot of effort to understand the approximability of $k$-$\mathsf{center}$,
$k$-$\mathsf{means}$, and $k$-$\mathsf{median}$ when $k$ is fixed. In the case
of $\mathsf{Max}$-$k$-$\mathsf{Diameter}$, however, the fixed-$k$ setting has
not been well-studied.

Thus, the main enquiry of this paper is to understand the complexity and
approximability of $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ when $k$ is fixed.
It has been observed in literature (for example [Meg90]) that
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ can be reduced to the $k$-coloring
problem. Since $2$-coloring is in $\mathsf{P}$, we have that
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ is in $\mathsf{P}$ when $k=2$. We
remark that this tractability is in stark constrast with $k$-$\mathsf{center}$
which is $\mathsf{NP}$-hard even for $k=2$ [Meg90].

Therefore we begin investigating the approximability of
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ when $k=3$. An argument by Megiddo
[Meg90] proves that $\mathsf{Max}$-$3$-$\mathsf{Diameter}$ is
$\mathsf{NP}$-hard to approximate within a factor better than 2 in the
$\ell_{\infty}$-metric by a reduction from the 3-coloring problem. This leaves
us to consider the problem in the $\ell_{1}$ and $\ell_{2}$ metrics.

###  1.1 Our Results

In this paper, we prove strong hardness of approximation results for
$\mathsf{Max}$-$3$-$\mathsf{Diameter}$ in the $\ell_{1}$ and $\ell_{2}$
metrics. Our results are surprising, as it is unclear a priori why
$\mathsf{Max}$-$3$-$\mathsf{Diameter}$ does not admit a $\mathsf{PTAS}$ much
like the other clustering objectives.

First, we present our result for the $\ell_{1}$-metric, which is obtained by a
hard instance in the Hamming metric.

######  Theorem 1.1 (formalized in Theorem 4.4).

For every $\varepsilon>0$ and $k\geq 3$, approximating the
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ problem in the $\ell_{1}$ metric (and
Hamming metric) to a factor $1.5-\varepsilon$ is $\mathsf{NP}$-hard.

To the best of our knowledge, there is no polynomial time algorithm that
achieves a factor less than 2 for $\mathsf{Max}$-$3$-$\mathsf{Diameter}$ in
the $\ell_{1}$ metric.

Since the above result also holds for the Hamming metric, it implies that
$\mathsf{Max}$-$3$-$\mathsf{Diameter}$ problem in the Euclidean metric is
$\mathsf{NP}$-hard to approximate to a factor better than $\sqrt{1.5}\approx
1.224$. Surprisingly, there is a better than 2-approximation algorithm for
$\mathsf{Max}$-$3$-$\mathsf{Diameter}$ in $\ell_{2}$ space. As a
straightforward consequence of the algorithm in [BHPI02] for the $k$-center
problem, there exists an efficient $(\sqrt{2}+\varepsilon)$-approximation
algorithm for the $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ problem in Euclidean
space.

Even more surprisingly, we are able to exploit the structure of the Euclidean
metric to improve on the $\sqrt{1.5}$-factor $\mathsf{NP}$-hardness and prove
the following:

######  Theorem 1.2 (formalized in Theorem 5.3).

For every $k\geq 3$, approximating the $\mathsf{Max}$-$k$-$\mathsf{Diameter}$
problem in the $\ell_{2}$ metric to a factor $1.304$ is $\mathsf{NP}$-hard.

This result is especially significant, since the Euclidean metric is near-
isometrically embeddable into all $\ell_{p}$-metrics, and so hardness within a
factor of 1.304 extends to all $\ell_{p}$ metrics.

Lastly, it is worth noting that even when the input pointset (of size $n$) is
restricted to $O(\log n)$ dimensions, both of our above hardness results still
hold. In Euclidean space, this follows from applying the Johnson-Lindenstrauss
lemma; in Hamming space, it follows from our proof (where we use Hadamard
codes, and we could instead use small-biased sets to bring the dimension down
to $\Theta(\log n)$). Finally, note that when the number of dimensions is
bounded by a constant, the $\mathsf{Max}$-$3$-$\mathsf{Diameter}$ problem is
in $\mathsf{P}$.

Thus, a summary of the best known hardness bounds and approximation algorithms
for the $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ problem, for constant $k\geq
3$, is given in Table 1.

Metric |  $\mathsf{NP}$-Hardness Factor | Polynomial Time Approximation Factor
---|---|---
$\ell_{\infty}$ |  $2-\varepsilon$ [Meg90] |  $2$ [Gon85]
$\ell_{0}/\ell_{1}$ |  $1.5-\varepsilon\ $ [This Paper] |  $2$ [Gon85]
$\ell_{2}$ |  $1.304\ $ [This Paper] |  $1.415$ [BHPI02]
Table 1: State-of-the-art Approximability Results for
$\mathsf{Max}$-$3$-$\mathsf{Diameter}$

###  1.2 Our Techniques

There is a natural connection between the
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ clustering problem and the $k$-coloring
problem. Suppose $P$ is a set of points, and let $\Delta$ be the diameter of
an optimal $3$-clustering of $P$. We can create a graph with points in $P$ as
vertices, and distances longer than $r\Delta$ as edges. Then coloring the
points in $P$ with $k$ colors so that no two adjacent vertices are the same
color directly corresponds to finding a $3$-clustering with diameter
$r\Delta$, an $r$-approximation to the clustering problem. All previous
hardness results for fixed $k$, including the ones in this paper, come from a
reduction from some version of the $k$-coloring problem.

Even though our hardness results for the $\ell_{1}$ and $\ell_{2}$ metrics are
reductions from the coloring problem, the approaches we take are different. In
the $\ell_{2}$ metric, we first construct a set of points in space, and then
prove that the corresponding graph of long distances is hard to color. In the
$\ell_{1}$ metric case, we start with a hard-to-color graph, and we construct
a pointset whose corresponding distance graph is exactly that.

It is important to note here that our embedding techniques are inspired from
the techniques in [Tre00], and they significantly improve upon it (see proof
of Theorem 3.3 for a demonstration of the proof technique in [Tre00]).

However, there are some limitations to showing improved hardness of
approximation, which we outline in Appendix B in the form of barrier results.
Our first barrier result says that if $\sqrt{2}$-approximation in the
Euclidean case is $\mathsf{NP}$-hard for $k=3$, then any hard instance must
lie on the surface of a sphere of radius $\sqrt{2}/2$. In particular, we show
that this implies that the corresponding family of hard-to-color graphs must
have unbounded odd girth. Our second barrier result is specific to the
framework used in Sections 3 and 4.

##  2 Preliminaries

This section contains definitions, remarks, and notation that will be used
throughout this paper.

###  2.1 Diameter Objective.

######  Definition 2.1 (Diameter).

Given a metric space $(X,\text{dist})$ and a set $A\subset X$, we say the
diameter of $A$ is

$\text{diam}(A)\mathrel{\mathop{\ordinarycolon}}=\max_{x,y\in
A}\text{dist}(x,y).$

For a collection of subsets $A_{1},\dots,A_{k}\subset X$, we say

$\text{diam}(\\{A_{1},\dots,A_{k}\\})\mathrel{\mathop{\ordinarycolon}}=\max_{\begin{subarray}{c}i\in[k]\\\
x,y\in A_{i}\end{subarray}}\text{dist}(x,y)$

is the diameter of the collection.

######  Definition 2.2 ($k$-clustering).

Given a set $P$, we say that a collection $\\{A_{1},\dots A_{k}\\}$ is a
$k$-clustering of $P$ if $A_{1},\dots A_{k}$ are pairwise disjoint and
$A_{1}\cup\cdots\cup A_{k}=P$.

######  Definition 2.3 ($\mathsf{Max}$-$k$-$\mathsf{Diameter}$ clustering
problem).

Let $(X,\text{dist})$ be a metric space and let $k$ be a constant. Given as
input a finite set $P\subset X$, find a $k$-clustering
$\\{A_{1},\dots,A_{k}\\}$ that minimizes
$\text{diam}(\\{A_{1},\dots,A_{k}\\})$.

######  Definition 2.4 ($r$-approximate $\mathsf{Max}$-$k$-$\mathsf{Diameter}$
clustering problem).

Let $(X,\text{dist})$ be a metric space and let $k$ be a constant. Given as
input a finite set $P\subset X$, let

$\Delta\mathrel{\mathop{\ordinarycolon}}=\min\text{diam}(\\{A_{1},\dots,A_{k}\\}),$

where the minimum is taken over all possible $k$-clusterings of $P$. Find a
$k$-clustering $\\{A_{1},\dots,A_{k}\\}$ with diameter at most $r\Delta$.

######  Definition 2.5.

Let $k$ be a constant, $r$ a ratio, and $P$ a pointset. Let $\Delta$ be the
optimal $k$-clustering diameter of $P$. Define $\Gamma_{k,r}(P)$ to be the
graph in which the points in $P$ are vertices, with edges between any two
points whose distance is greater than $r\Delta$.

###  2.2 Coloring Problems

######  Definition 2.6 (rainbow $k$-coloring problem).

Let $k$ be a constant. Given a hypergraph $G=(V,E)$ as input, find an
assignment of $k$ colors to the vertices of $G$ such that for any hyperedge
$e\in E$, all vertices in $e$ are assigned to different colors. Such an
assignment is called a rainbow $k$-coloring.

######  Remark 2.1.

We can view 2-regular hypergraphs as graphs where edges of the hypergraph form
vertices of the graph, and vertices of the hypergraph form edges of the graph.
Formally, let $G=(V,E)$ be a 2-regular hypergraph. Then, let
$G^{\prime}=(V^{\prime},E^{\prime})$ be a graph where $V^{\prime}=E$ and
$(e_{1},e_{2})\in E^{\prime}$ if $e_{1}$ and $e_{2}$ share a vertex in $V$.
Rainbow $k$-coloring $G$ is equivalent to coloring the edges of $G^{\prime}$
in $k$ colors such that no two incident edges are the same color. This problem
is called $k$-edge-coloring.

######  Remark 2.2.

It is known that $3$-edge coloring is $\mathsf{NP}$-hard on 3-regular graphs
[Hol81]. So, Remark 2.1 implies that rainbow $3$-coloring is
$\mathsf{NP}$-hard, even when restricted to 2-regular, 3-uniform hypergraphs.

######  Remark 2.3 (Coloring-clustering equivalence).

By assigning each color class to a cluster, we see that $r$-approximate
$k$-clustering a pointset $P$ is equivalent to $k$-coloring the graph
$\Gamma_{k,r}(P)$.

###  2.3 Hadamard Codes

For a bit string $x\in\\{0,1\\}^{q}$, we denote its bitwise complement by
$\overline{x}$.

######  Definition 2.7 (Hadamard Code).

Let $q$ be a power of 2. There exists a subset of $\\{0,1\\}^{q}$ of size $q$
such that the Hamming distance between distinct elements is exactly $q/2$. We
call this the Hadamard code and denote it by $\text{Had}_{q}^{+}$. Define
$\text{Had}_{q}^{-}\mathrel{\mathop{\ordinarycolon}}=\\{\overline{x}\mathrel{\mathop{\ordinarycolon}}x\in\text{Had}_{q}^{+}\\}$.
Then, let

$\text{Had}_{q}\mathrel{\mathop{\ordinarycolon}}=\text{Had}_{q}^{+}\cup\text{Had}_{q}^{-}.$

Throughout Section 4, we will often use letters with subscripts to refer to
elements in $\text{Had}_{q}^{+}$. Distinct letters or subscripts will always
refer to distinct codewords. For example,
$x_{11},x_{12},y_{11}\in\text{Had}_{q}^{+}$ are three distinct codewords.
Given $x,y\in\text{Had}_{q}$, we will denote by $(x,y)$ the bit concatenation
of $x$ and $y$.

######  Remark 2.4.

The set $\text{Had}_{q}$ has the following property: for every
$x\in\text{Had}_{q}$, there is exactly one element in $\text{Had}_{q}$ that is
distance $q$ away, namely $\overline{x}$. All other elements have distance
$q/2$ to $x$.

##  3 A General Metric Embedding

We begin with a general notion of graph embeddability, which provides a useful
framework for proving hardness results in $\ell_{\infty}$ and $\ell_{1}$
space.

######  Definition 3.1.

Let $G$ be a graph. For $r>1$ and $p\in[1,\infty]$, we say $G$ is
$r$-embeddable in $\ell_{p}$-space if there exists $q\in\mathbb{N}$ and a
function $\phi\mathrel{\mathop{\ordinarycolon}}G\to\mathbb{R}^{q}$, such that
both the following hold:

  1. 1.

If $(u,v)$ is an edge in $G$, then
$\left\lVert\phi(u)-\phi(v)\right\rVert_{p}\geq r$.

  2. 2.

Otherwise, $\left\lVert\phi(u)-\phi(v)\right\rVert_{p}\leq 1$.

We call such a map $\phi$ an $r$-embedding of $G$ into $\ell_{p}$ space.

######  Lemma 3.1.

Let $k\geq 3$, and let $G$ be a graph drawn from a family of graphs on which
rainbow $k$-coloring is $\mathsf{NP}$-hard. Suppose there exists a polynomial-
time computable $r$-embedding
$\phi\mathrel{\mathop{\ordinarycolon}}G\to(\mathbb{R}^{q},\ell_{p})$, for
$p\in[1,\infty]$. Given $q\in\mathbb{N}$ and a pointset
$P\subset(\mathbb{R}^{q},\ell_{p})$, it is $\mathsf{NP}$-hard to distinguish
between the following two cases:

  * •

Completeness: There exists a $k$-clustering of $P$ with diameter at most $1$.

  * •

Soundness: Any $k$-clustering of $P$ has diameter at least $r$.

###### Proof.

Consider the pointset $P=\phi(G)\subset\mathbb{R}^{q}$. Any rainbow
$k$-coloring of the vertices of $G$ induces a $k$-clustering of the set $P$
with diameter at most $1$, where color classes correspond to clusters.
Conversely, any $k$-clustering of $P$ with diameter less than $r$ corresponds
to a rainbow $k$-coloring of $G$, since vertices that are adjacent in $G$ are
embedded with distance at least $r$ in $\phi(G)$. Since determining whether or
not $G$ is rainbow $k$-colorable is $\mathsf{NP}$-hard, the result follows. ∎

We use the above framework to achieve a tight hardness result in the
$\ell_{\infty}$ metric, and nontrivial hardness results in the $\ell_{1}$ and
$\ell_{2}$ metrics.

######  Theorem 3.2 ($\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in $\ell_{\infty}$
space).

Let $k\geq 3$ be constant. Given $q\in\mathbb{N}$ and a pointset
$P\subset(\mathbb{R}^{q},\ell_{\infty})$, it is $\mathsf{NP}$-hard to
distinguish between the following two cases:

  * •

Completeness: There exists a $k$-clustering of $P$ with diameter at most $1$.

  * •

Soundness: Any $k$-clustering of $P$ has diameter at least $2$.

###### Proof.

We describe a $2$-embedding of general graphs into $\ell_{\infty}$ space, as
given in [Meg90] (proof of Proposition 2.6). Let $G=(V,E)$ be an arbitrary
graph with $n\mathrel{\mathop{\ordinarycolon}}=|V|$. Define a mapping
$\phi(u)=(p_{u1},\ldots,p_{un})$ given by:

$p_{uv}=\begin{cases}2&\text{if }u=v\\\ 0&\text{if }(u,v)\in E\\\
1&\text{otherwise}\end{cases}.$

Now, let $u,v\in V$. If $(u,v)\in E$, then $|p_{uu}-p_{vu}|=2$ and so
$\left\lVert\phi(u)-\phi(v)\right\rVert_{\infty}\geq 2$. If $(u,v)\notin E$,
then for any $w\in V$ where $p_{uw}=0$ we must have $v\neq w$ and thus
$p_{vw}\leq 1$, yielding $\left\lVert\phi(u)-\phi(v)\right\rVert_{\infty}\leq
1$. Thus, $\phi$ is a $2$-embedding. By Lemma 3.1, the existence of $\phi$
yields the desired claim. ∎

######  Remark 3.1.

Since Gonzalez’s algorithm gives an efficient $2$-approximation of
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in all metric spaces, Theorem 3.2 gives
a tight result for $\ell_{\infty}$ space.

######  Theorem 3.3 ($\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in $\ell_{1}$
space).

Let $k\geq 3$ be constant. Given $q\in\mathbb{N}$ and a pointset
$P\subset(\mathbb{R}^{q},\ell_{1})$, it is $\mathsf{NP}$-hard to distinguish
between the following two cases:

  * •

Completeness: There exists a $k$-clustering of $P$ with diameter at most $1$.

  * •

Soundness: Any $k$-clustering of $P$ has diameter at least $5/4$.

###### Proof.

We will provide a polynomial-time computable $5/4$-embedding of $4$-regular
and $4$-edge-colorable graphs. We know rainbow $3$-coloring is
$\mathsf{NP}$-hard on such graph (see Appendix A). By Lemma 3.1, this is
sufficient to complete the proof.

On an input graph $G=(V,E)$, let $q$ be the smallest power of $2$ that is at
least $|V|$. Since $G$ is $4$-edge colorable, we can decompose $E$ as the
disjoint union of matchings $M_{1},M_{2},M_{3},M_{4}\subseteq E$. For
$i\in[4]$, let $\phi_{i}\mathrel{\mathop{\ordinarycolon}}V\to\text{Had}_{q}$
be defined so that for any $u,v\in V$, we have

$(u,v)\in M_{i}\iff\phi_{i}(u)=\overline{\phi_{i}(v)}.$

Now, take
$\phi(v)\mathrel{\mathop{\ordinarycolon}}=\left(\phi_{1}(v),\phi_{2}(v),\phi_{3}(v),\phi_{4}(v)\right)$.
If $(u,v)\in E$, then $(u,v)\in M_{i}$ for some $i\in[4]$. Then
$\left\lVert\phi(u)-\phi(v)\right\rVert_{1}\geq
t+3\cdot\frac{t}{2}=\frac{5t}{2}$. If $(u,v)\notin E$, then for all $i\in[4]$
we have $(u,v)\notin M_{i}$, so
$\left\lVert\phi(u)-\phi(v)\right\rVert_{1}\leq 4\cdot\frac{t}{2}=2t$. Thus,
$\phi$ is a $5/4$-embedding. ∎

We remark here that the above technique is inspired from [Tre00].

######  Corollary 3.4 ($\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in $\ell_{2}$
space).

Let $k\geq 3$ be constant. Given $q\in\mathbb{N}$ and a pointset
$P\subset(\mathbb{R}^{q},\ell_{2})$, it is $\mathsf{NP}$-hard to distinguish
between the following two cases:

  * •

Completeness: There exists a $k$-clustering of $P$ with diameter at most $1$.

  * •

Soundness: Any $k$-clustering of $P$ has diameter at least $\sqrt{5/4}$.

###### Proof.

Consider the same embedding $\phi$ of $4$-regular and $4$-edge-colorable
graphs from the proof of Theorem 3.3. Since the range of $\phi$ is contained
within the Boolean hypercube $\\{0,1\\}^{4q}$, for each $u,v\in V$ we have
$\left\lVert\phi(u)-\phi(v)\right\rVert_{2}=\sqrt{\left\lVert\phi(u)-\phi(v)\right\rVert_{1}}$.
Hence $\phi$ is a $\sqrt{5/4}$-embedding into $\ell_{2}$ space and the claim
follows. ∎

##  4 Hardness of Approximation of $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in
$\ell_{1}$ Space

In this section, we build on our embedding from Section 3, showing improved
hardness of approximation within a factor of $3/2$ in $\ell_{1}$ space.

###  4.1 Constructing a Better Hard Instance

We begin by considering the graph consisting of the Chvátal graph [Chv70] with
an edge removed, which we denote by $H$. The graph $H$ is a particular graph
on $12$ vertices that is uniquely $3$-colorable. The unique $3$-coloring of
$H$ is shown in Figure 1.

$\displaystyle i$$\displaystyle j$$\displaystyle k$ Figure 1: Unique
$3$-coloring of $H\cup\\{i,j,k\\}$; three auxiliary vertices $i,j,k$ are each
connected to $H$ such that they are forced to be different colors in any
$3$-coloring.
$\displaystyle(i_{1},i_{2})$$\displaystyle(j_{1},j_{2})$$\displaystyle(k_{1},k_{2})$$\displaystyle(\overline{i}_{1},\overline{b}_{ijk})$$\displaystyle(\overline{i}_{1},\overline{c}_{ijk})$$\displaystyle(\overline{a}_{ijk},\overline{k}_{2})$$\displaystyle(i_{1},\overline{k}_{2})$$\displaystyle(j_{1},k_{2})$$\displaystyle(\overline{j}_{1},k_{2})$$\displaystyle(i_{1},\overline{b}_{ijk})$$\displaystyle(\overline{j}_{1},b_{ijk})$$\displaystyle(j_{1},\overline{b}_{ijk})$$\displaystyle(j_{1},b_{ijk})$$\displaystyle(\overline{j}_{1},c_{ijk})$$\displaystyle(a_{ijk},b_{ijk})$$\displaystyle
i$$\displaystyle j$$\displaystyle k$ Figure 2: A $3/2$-embedding of the
$H\cup\\{i,j,k\\}$ using two Hadamard codewords. Note that the dotted lines
are also considered edges.

######  Definition 4.1.

We will define a family of graphs $\widehat{G}=(\widehat{V},\widehat{E})$. Let
$G=(V,E)$ be the incidence hypergraph of a cut-edge free $3$-regular graph.
For each incidence set $\\{i,j,k\\}\in E$, construct a disjoint copy of $H$,
denoted $H_{ijk}$. For $x\in\\{i,j,k\\}$, let $T_{ijk}^{x}$ denote the set of
edges between vertex $x$ and the graph $H_{ijk}$, as shown by the dotted edges
in Figure 1. Then, define

$\widehat{V}=V\cup\bigcup_{\\{i,j,k\\}\in E}V(H_{ijk})$

and

$\widehat{E}=\bigcup_{\\{i,j,k\\}\in
E}\left(E(H_{ijk})\cup\bigcup_{x\in\\{i,j,k\\}}T_{ijk}^{x}\right)$

where $V(H_{ijk})$ and $E(H_{ijk})$ refer respectively to the vertex and edge
set of $H_{ijk}$.

######  Lemma 4.1.

Rainbow $3$-coloring on $\widehat{G}$ is $\mathsf{NP}$-hard.

###### Proof.

Since $H_{ijk}$ is uniquely rainbow $3$-colorable, the graph $\widehat{G}$ is
rainbow $3$-colorable if and only if the initial hypergraph $G$ is rainbow
$3$-colorable. Since $3$-edge-coloring on cut-edge free $3$-regular graphs is
$\mathsf{NP}$-hard (see Appendix A), the family of graphs $\widehat{G}$ is a
hard instance of rainbow $3$-coloring. ∎

###  4.2 Embedding the Hard Instance

Notice that in Figure 2, for each of the auxiliary vertices $i,j,k$, either
their first or second block features in the remainder of the embedding, but
not both. In particular, the codewords $i_{2}$, $j_{1}$, and $k_{1}$ appear
only in the embeddings of $i$, $j$ and $k$, respectively. Thus, we can refer
to this embedding of $H_{ijk}$ as its canonical $(1,2,2)$-oriented embedding;
the triplet $(1,2,2)$ refers to the fact that only the first codeword of $i$,
the second codeword of $j$, and the second codeword of $k$ are used in the
embedding of $H_{ijk}$.

By permuting the order of $i$, $j$, and $k$, we can construct canonical
$(2,1,2)$-oriented and $(2,2,1)$-oriented embeddings of $H_{ijk}$. By
switching the first and second codewords of all embedded points, we see that
$H_{ijk}$ admits any orientation in

$O\mathrel{\mathop{\ordinarycolon}}=\\{(1,2,2),(2,1,2),(2,2,1),(2,1,1),(1,2,1),(1,1,2)\\}.$

Let $\sigma\mathrel{\mathop{\ordinarycolon}}E\to O$, and let
$\sigma(\\{i,j,k\\})_{i}\in\\{1,2\\}$ index which block of $i$ (either $i_{1}$
or $i_{2}$) appears in the gadget $H_{ijk}$.

######  Lemma 4.2.

Suppose there exists $\sigma\mathrel{\mathop{\ordinarycolon}}E\to O$ with the
following property: for any $i\in V$, the two hyperedges $e_{1},e_{2}\in E$
containing $i$ satisfy $\sigma(e_{1})_{i}\neq\sigma(e_{2})_{i}$. Let
$\widehat{G}=(\widehat{V},\widehat{E})$ be as in Definition 4.1 and let
$q=|V|+2|E|$. The following map
$\phi\mathrel{\mathop{\ordinarycolon}}\widehat{G}\to\textup{Had}_{q}\times\textup{Had}_{q}$
is a $3/2$-embedding of $\widehat{G}$:

  * •

For each $i\in V$, set $\phi(i)=(i_{1},i_{2})$, where
$i_{1},i_{2}\in\textup{Had}_{q}$.

  * •

For each $e\in E$ and $h\in H_{e}$, set $\phi(h)$ as in the canonical
$\sigma(e)$-oriented embedding of the $H_{e}$.

###### Proof.

Observe that every edge $(u,v)\in\widehat{E}$ belongs to a subgraph of
$\widehat{G}$ induced by $V(H_{e})\cup e$, for some $e\in E$. Since $\phi$ is
a $3/2$-embedding when restricted to $V(H_{e})\cup e$ by construction, this
confirms that $\left\lVert\phi(u)-\phi(v)\right\rVert_{1}\geq 3q/2$.

Next, we show that if $(u,v)\not\in\widehat{E}$, then
$\left\lVert\phi(u)-\phi(v)\right\rVert_{1}\leq q$. We split into the
following cases:

  1. 1.

Suppose $u\in V$. If $\phi(u)$ and $\phi(v)$ share no codewords, we have
$\left\lVert\phi(u)-\phi(v)\right\rVert_{1}\leq q$ as desired. If they do
share codewords, it must be the case that $v\in H_{e}$ for some $e\in E$ where
$u\in e$. Since $\phi$ is a $3/2$-embedding when restricted to $V(H_{e})\cup
e$, we conclude that $\left\lVert\phi(u)-\phi(v)\right\rVert_{1}\leq q$. The
case $v\in V$ is handled identically.

  2. 2.

Suppose $u,v\in H_{e}$ for some $e$. Then since $\phi$ is a $3/2$-embedding
when restricted to $V(H_{e})$, we have
$\left\lVert\phi(u)-\phi(v)\right\rVert_{1}\leq q$.

  3. 3.

Suppose $u\in H_{e}$ and $v\in H_{f}$ for $e\neq f$. Then $\phi(u)$ and
$\phi(v)$ can only share a codeword associated with a vertex $i\in e\cap f$.
But $\sigma(e)_{i}\neq\sigma(f)_{i}$ by assumption, meaning the first codeword
of $\phi(u)$ is not $i_{1}$ and the second codeword of $\phi(v)$ is not
$i_{2}$ (or vice-versa). Therefore, $\phi(u)$ and $\phi(v)$ have distinct
codewords so $\left\lVert\phi(u)-\phi(v)\right\rVert_{1}\leq q$.

∎

######  Lemma 4.3.

Let $G=(V,E)$ and $\widehat{G}=(\widehat{V},\widehat{E})$ be as in Definition
4.1. There exists an polynomial-time computable map
$\sigma\mathrel{\mathop{\ordinarycolon}}E\to O$ satisfying the property of
Lemma 4.2.

###### Proof.

Recall that $G$ is the incidence graph of a $3$-regular cut-edge free graph
$J$. Constructing a valid assignment $\sigma$ amounts to directing each edge
in $J$ such that no vertex has indegree $3$ or outdegree $3$. Consider running
a depth-first search on $J$, producing a directed graph $\vec{J}$ whose edges
are oriented in the direction of the traversal. We claim that this orientation
satisfies the desired property.

First, no vertex $i$ can have indegree $3$; upon first arriving at $i$, the
next edge traversed will be another edge incident to $i$ and it will be
directed away from $i$.

Moreover, no vertex $j$ can have outdegree $3$. This is clear when $j$ is not
the root vertex of the DFS, as we can only arrive at $j$ through an incoming
edge. Conversely, if $j$ is the root vertex then we observe that each edge
incident to $j$ is not a cut edge, by assumption. Therefore, each of these
edges must be included in a directed cycle. Hence, before traversing another
edge starting at $j$, we will return to $j$ to complete the cycle including
that edge. In particular, $j$ will have indegree at least $1$ and therefore
outdegree at most $2$.

Since DFS runs in polynomial time, we have shown that an orientation $\vec{J}$
can be computed in polynomial time. Hence, the same holds for $\sigma$, as
desired. ∎

######  Theorem 4.4 ($\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in $\ell_{1}$
space).

Let $k\geq 3$ be constant. Given $q\in\mathbb{N}$ and a pointset
$P\subset(\mathbb{R}^{q},\ell_{1})$, it is $\mathsf{NP}$-hard to distinguish
between the following two cases:

  * •

Completeness: There exists a $k$-clustering of $P$ with diameter at most $1$.

  * •

Soundness: Any $k$-clustering of $P$ has diameter at least $3/2$.

###### Proof.

Putting together Lemmas 4.2 and 4.3, we have shown the existence of a
polynomial-time computable $3/2$-embedding of $\widehat{G}$. Lemma 4.1 states
that $\widehat{G}$ is a hard instance of rainbow $3$-coloring, and so applying
Lemma 3.1 completes our proof. ∎

As with Corollary 3.4, this result directly translates to a hardness result of
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in Euclidean space.

######  Corollary 4.5 ($\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in $\ell_{2}$
space).

Let $k\geq 3$ be constant. Given $q\in\mathbb{N}$ and a pointset
$P\subset(\mathbb{R}^{q},\ell_{2})$, it is $\mathsf{NP}$-hard to distinguish
between the following two cases:

  * •

Completeness: There exists a $k$-clustering of $P$ with diameter at most $1$.

  * •

Soundness: Any $k$-clustering of $P$ has diameter at least $\sqrt{3/2}$.

##  5 Hardness of Approximation of Euclidean
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$

In this section, we outline a new technique for constructing pointsets on the
surface of a sphere that are hard to approximately cluster. Using this
construction, we prove hardness of $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in
Euclidean space within a factor of $1.304$, a significant improvement from the
$\sqrt{3/2}\approx 1.224$ factor achieved in Corollary 4.5.

###  5.1 A Pointset from Regions on a Sphere

######  Definition 5.1.

For distinct coordinates $a,b,c\in[q]$, define a sphere
$S_{abc}\subset\mathbb{R}^{q}$ as follows:

$S_{abc}\mathrel{\mathop{\ordinarycolon}}=\mathinner{\left\\{x\in\mathbb{R}^{q}\mathrel{\mathop{\ordinarycolon}}x_{a}^{2}+x_{b}^{2}+x_{c}^{2}=\frac{1}{2};\;x_{i}=0\text{
for }i\not\in\\{a,b,c\\}\right\\}}.$

Let $e_{i}\in\mathbb{R}^{q}$ denote the vector where the $i$-th coordinate is
$\sqrt{2}/2$, and all other coordinates are 0. Let
$\overline{e}_{i}\mathrel{\mathop{\ordinarycolon}}=-e_{i}$. Note that for
$i\neq j$, the distance between $\pm e_{i}$ and $\pm e_{j}$ is 1. Next, define

$\displaystyle S_{abc}^{a}$
$\displaystyle\mathrel{\mathop{\ordinarycolon}}=\mathinner{\left\\{x\in
S_{abc}\mathrel{\mathop{\ordinarycolon}}x_{a}\geq 0,x_{b}\leq 0,x_{c}\leq
0\right\\}},$ $\displaystyle S_{abc}^{b}$
$\displaystyle\mathrel{\mathop{\ordinarycolon}}=\mathinner{\left\\{x\in
S_{abc}\mathrel{\mathop{\ordinarycolon}}x_{a}\leq 0,x_{b}\geq 0,x_{c}\leq
0\right\\}},$ $\displaystyle S_{abc}^{c}$
$\displaystyle\mathrel{\mathop{\ordinarycolon}}=\mathinner{\left\\{x\in
S_{abc}\mathrel{\mathop{\ordinarycolon}}x_{a}\leq 0,x_{b}\leq 0,x_{c}\geq
0\right\\}}.$

$\overline{e_{a}}$$\overline{e_{b}}$$\overline{e_{c}}$$e_{a}$$e_{b}$$e_{c}$
Figure 3: The set $S_{abc}^{a}\cup S_{abc}^{b}\cup S_{abc}^{c}$, indicated by
the colored regions.

######  Definition 5.2.

Let $\kappa\in\mathbb{N}$. We define a set of points $P_{abc}^{\kappa}\subset
S_{abc}^{a}\cup S_{abc}^{b}\cup S_{abc}^{c}$ as follows:

$\displaystyle P_{abc}^{\kappa}\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\mathinner{\left\\{\frac{x}{\left\lVert
x\right\rVert}\cdot\frac{\sqrt{2}}{2}\mathrel{\mathop{\ordinarycolon}}x=\alpha_{a}e_{a}+\alpha_{b}\overline{e}_{b}+\alpha_{c}\overline{e}_{c};\;\alpha_{a}+\alpha_{b}+\alpha_{c}=\kappa;\;\alpha_{a},\alpha_{b},\alpha_{c}\in\mathbb{N}\cup\\{0\\}\right\\}}$
$\displaystyle\cup$ $\displaystyle\mathinner{\left\\{\frac{x}{\left\lVert
x\right\rVert}\cdot\frac{\sqrt{2}}{2}\mathrel{\mathop{\ordinarycolon}}x=\alpha_{a}\overline{e}_{a}+\alpha_{b}e_{b}+\alpha_{c}\overline{e}_{c};\;\alpha_{a}+\alpha_{b}+\alpha_{c}=\kappa;\;\alpha_{a},\alpha_{b},\alpha_{c}\in\mathbb{N}\cup\\{0\\}\right\\}}$
$\displaystyle\cup$ $\displaystyle\mathinner{\left\\{\frac{x}{\left\lVert
x\right\rVert}\cdot\frac{\sqrt{2}}{2}\mathrel{\mathop{\ordinarycolon}}x=\alpha_{a}\overline{e}_{a}+\alpha_{b}\overline{e}_{b}+\alpha_{c}e_{c};\;\alpha_{a}+\alpha_{b}+\alpha_{c}=\kappa;\;\alpha_{a},\alpha_{b},\alpha_{c}\in\mathbb{N}\cup\\{0\\}\right\\}}.$

Note that $e_{a},e_{b},e_{c}\in P^{\kappa}_{abc}$.

######  Lemma 5.1.

The set $P_{abc}^{12}$ has the following properties:

  * •

There exists a 3-clustering of $P_{abc}^{12}$ with diameter at most $1$.

  * •

For any $3$-clustering of $P_{abc}^{12}$ with diameter at most 1.304, the
points $e_{a},e_{b},$ and $e_{c}$ are in three different clusters.

###### Proof.

Let

$\displaystyle A\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\mathinner{\left(P^{12}_{abc}\cap
S_{abc}^{a}\right)}\setminus\mathinner{\left\\{\overline{e}_{b}\right\\}},$
$\displaystyle B\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\mathinner{\left(P^{12}_{abc}\cap
S_{abc}^{b}\right)}\setminus\mathinner{\left\\{\overline{e}_{c}\right\\}},$
$\displaystyle C\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\mathinner{\left(P^{12}_{abc}\cap
S_{abc}^{c}\right)}\setminus\mathinner{\left\\{\overline{e}_{a}\right\\}}.$

Then, $P^{12}_{abc}$ is the disjoint union of $A,B,$ and $C$, and the
diameters of $A$, $B$, and $C$ are at most 1, as desired.

The second property is verified by a computer. We construct a graph where
vertices correspond to points in $P^{12}_{abc}$ and edges correspond to
distances more than 1.304. Running a 3-coloring algorithm and verifying that
that the vertices corresponding to $e_{a},e_{b},$ and $e_{c}$ are always
colored with 3 different colors yields the desired property. ∎

######  Conjecture 5.1.

For any $\varepsilon>0$, there exists a $\kappa\in\mathbb{N}$ such that

  * •

There exists a 3-clustering of $P_{abc}^{\kappa}$ with diameter at most $1$.

  * •

For any $3$-clustering of $P_{abc}^{\kappa}$ with diameter at most
$\sqrt{1+\sqrt{2}/2}-\varepsilon$, the points $e_{a},e_{b},$ and $e_{c}$ are
in three different clusters.

######  Remark 5.1.

There exists a 3-clustering of $S_{abc}^{a}\cup S_{abc}^{b}\cup S_{abc}^{c}$
of diameter $\sqrt{1+\sqrt{2}/2}\approx 1.306$ where $e_{b}$ and $e_{c}$ are
in the same cluster.

###### Proof.

Let

$\displaystyle A\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\mathinner{\left(x\in S_{abc}^{a}\cup S_{abc}^{b}\cup
S_{abc}^{c}\mathrel{\mathop{\ordinarycolon}}x_{a}\leq x_{b},x_{a}\leq
x_{c}\right)},$ $\displaystyle B\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\mathinner{\left(x\in S_{abc}^{a}\cup S_{abc}^{b}\cup
S_{abc}^{c}\mathrel{\mathop{\ordinarycolon}}x_{b}\leq x_{c},x_{b}\leq
x_{a}\right)}\setminus A,$ $\displaystyle C\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\mathinner{\left(x\in S_{abc}^{a}\cup S_{abc}^{b}\cup
S_{abc}^{c}\mathrel{\mathop{\ordinarycolon}}x_{c}\leq x_{a},x_{c}\leq
x_{b}\right)}\setminus(A\cup B).$

We have that $S_{abc}^{a}\cup S_{abc}^{b}\cup S_{abc}^{c}$ is the disjoint
union of $A,B$, and $C$, and the diameters of $A,B$ and $C$ are all
$\sqrt{1+\sqrt{2}/2}$. ∎

###  5.2 Reduction from Coloring

######  Definition 5.3.

Let $G=(V,E)$ be a 3-uniform hypergraph and let $V=[q]$. Define

$P_{G}\mathrel{\mathop{\ordinarycolon}}=\bigcup_{\\{a,b,c\\}\in
E}P^{12}_{abc}.$

######  Lemma 5.2.

Let $G$ and $P_{G}$ be as above. The following properties hold:

  * •

Completeness: If $G$ is rainbow 3-colorable, then there exists a 3-clustering
of $P_{G}$ with diameter at most 1.

  * •

Soundness: If $G$ is not rainbow 3-colorable, then any 3-clustering of $P_{G}$
has diameter at least 1.304.

###### Proof.

We first prove completeness. Suppose $G$ is rainbow $3$-colorable, and let
$V_{A},V_{B},V_{C}$ be the three color classes in a rainbow 3-coloring of $G$.
Define the following $3$-clustering $\\{A,B,C\\}$ of $P^{12}_{abc}$:

$\displaystyle A\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\bigcup_{\begin{subarray}{c}\\{a,b,c\\}\in E\\\ a\in
V_{A}\end{subarray}}\mathinner{\left(P^{12}_{abc}\cap S_{abc}^{a}\right)},$
$\displaystyle B\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\mathinner{\left(\bigcup_{\begin{subarray}{c}\\{a,b,c\\}\in E\\\
a\in V_{B}\end{subarray}}\mathinner{\left(P^{12}_{abc}\cap
S_{abc}^{b}\right)}\right)}\setminus A,$ $\displaystyle
C\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\mathinner{\left(\bigcup_{\begin{subarray}{c}\\{a,b,c\\}\in E\\\
a\in V_{C}\end{subarray}}\mathinner{\left(P^{12}_{abc}\cap
S_{abc}^{c}\right)}\right)}\setminus(A\cup B).$

We claim each of these clusters has diameter at most 1. We prove this for $A$;
the reasoning for $B$ and $C$ is identical. Define

$Q_{A}\mathrel{\mathop{\ordinarycolon}}=\mathinner{\left\\{x\in\mathbb{R}^{q}\mathrel{\mathop{\ordinarycolon}}x_{a}\geq
0\text{ for }a\in V_{A};\;x_{a}\leq 0\text{ for }a\not\in V_{A}\right\\}}$

Suppose $x\in A$. Then, there exists some $a\in V_{a}$ and $\\{a,b,c\\}\in E$
such that $x\in S_{abc}^{a}$. This means that $x_{a}\geq 0$ and
$x_{b},x_{c}\leq 0$, and all other coordinates of $x$ are 0. So $x\in Q_{A}$,
and we therefore have $A\subseteq Q_{A}$.

Let $x,y\in A$. Since $x,y\in Q_{A}$, we have
$\operatorname{sgn}(x_{i})=\operatorname{sgn}(y_{i})$ for each $i\in[q]$.
Hence, the inner product $\langle x,y\rangle$ is nonnegative, meaning, the
angle between the vectors formed by $x$ and $y$ is at most $\pi/2$. Since $x$
and $y$ lie on the surface of a radius $\sqrt{2}/2$ sphere, we have
$\left\lVert x-y\right\rVert_{2}\leq 1$. Thus, $A$ has diameter at most 1.

Next, we will prove soundness. Suppose there is a 3-clustering $\\{A,B,C\\}$
of $P_{G}$ with diameter at most 1.304. Define a $3$-coloring
$\\{V_{A},V_{B},V_{C}\\}$ of $V$ where, for each cluster $X\in\\{A,B,C\\}$,
$V_{X}$ contains vertex $v$ if $e_{v}\in X$. By Lemma 5.1, for any neighboring
vertices $a,b\in V$, $e_{a}$ and $e_{b}$ must be in different clusters, so $a$
and $b$ must be colored differently. With this, we have proved that $G$ is
rainbow $3$-colorable. ∎

######  Theorem 5.3 ($\mathsf{Max}$-$k$-$\mathsf{Diameter}$ in Euclidean
space).

Let $k\geq 3$ be constant. Given $q\in\mathbb{N}$ and a pointset
$P\subset(\mathbb{R}^{q},\ell_{2})$, it is $\mathsf{NP}$-hard to distinguish
between the following two cases:

  * •

Completeness: There exists a $k$-clustering of $P$ with diameter at most $1$.

  * •

Soundness: Any $k$-clustering of $P$ has diameter at least $1.304$.

###### Proof.

By Remark 2.2, rainbow 3-coloring on 3-uniform hypergraphs is
$\mathsf{NP}$-hard (see Remark 2.2). We reduce from this problem. Given an
input hypergraph $G$, we can construct $P_{G}$ in polynomial time. The result
follows immediately from Lemma 5.2. ∎

### Acknowledgements

We thank Vincent Cohen-Addad and Euiwoong Lee for pointing us to [BHPI02] and
it’s implications to Euclidean $\mathsf{Max}$-$k$-$\mathsf{Diameter}$.

This work was carried out while Kyrylo, Ashwin, and Stepan were participating
in the DIMACS REU 2023. Kyrylo was supported by the CoSP, an European Union’s
Horizon 2020 programme, grant agreement No. 823748. Karthik was supported by
the National Science Foundation under Grant CCF-2313372 and a grant from the
Simons Foundation, Grant Number 825876, Awardee Thu D. Nguyen. Ashwin and
Stepan were supported by the NSF grant CNS-2150186.

## References

  * [BCM+18] Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Oliver Schaudt, Maya Stein, and Mingxian Zhong.  Three-coloring and list three-coloring of graphs without induced paths on seven vertices.  Combinatorica, 38(4), Aug 2018.
  * [BHPI02] Mihai Bādoiu, Sariel Har-Peled, and Piotr Indyk.  Approximate clustering via core-sets.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 250–257, 2002.
  * [Chv70] V. Chvátal.  The smallest triangle-free 4-chromatic 4-regular graph.  Journal of Combinatorial Theory, 9(1):93–94, Jul 1970.
  * [DGK63] Ludwig Danzer, Branko Grünbaum, and Victor Klee.  Helly’s theorem and its relatives.  In Proceedings of symposia in pure mathematics, pages 101–180. American Mathematical Society, 1963.
  * [FG88] 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, page 434–444, Chicago, Illinois, United States, 1988\. ACM Press.
  * [FPT81] Robert J Fowler, Michael S Paterson, and Steven L Tanimoto.  Optimal packing and covering in the plane are np-complete.  Information processing letters, 12(3):133–137, 1981.
  * [GJS76] M. R. Garey, David S. Johnson, and Larry J. Stockmeyer.  Some simplified np-complete graph problems.  Theor. Comput. Sci., 1(3):237–267, 1976.
  * [Gon85] Teofilo F. Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theoretical Computer Science, 38:293–306, 1985.
  * [Hol81] Ian Holyer.  The np-completeness of edge-coloring.  SIAM Journal on computing, 10(4):718–720, 1981.
  * [HS85] Dorit S Hochbaum and David B Shmoys.  A best possible heuristic for the k-center problem.  Mathematics of operations research, 10(2):180–184, 1985.
  * [HS86] Dorit S. Hochbaum and David B. Shmoys.  A unified approach to approximation algorithms for bottleneck problems.  Journal of the ACM, 33(3):533–550, May 1986.
  * [Meg90] Nimrod Megiddo.  On the complexity of some geometric problems in unbounded dimension.  Journal of Symbolic Computation, 10(3–4):327–334, 1990.
  * [Men88] Stuart G Mentzer.  Approximability of metric clustering problems.  Manuscript. https://www. academia. edu/23251714/Approximability of Metric Clustering Problems, 1988.
  * [MG92] Jayadev Misra and David Gries.  A constructive proof of vizing’s theorem.  Inf. Process. Lett., 41(3):131–133, 1992.
  * [Tre00] Luca Trevisan.  When hamming meets euclid: The approximability of geometric tsp and steiner tree.  SIAM Journal on Computing, 30(2):475–485, 2000.

##  Appendix A Stronger Hardness of $3$-coloring

In this section we show that a more restricted version of $3$-coloring is
still $\mathsf{NP}$-complete. We update the gadget of the Theorem 2.3 of
[GJS76] which makes the resulting graph $4$-edge colorable. Which makes
$3$-coloring on $4$-edge colorable graphs with maximum degree $4$
$\mathsf{NP}$-complete.

######  Theorem A.1.

Rainbow $3$-coloring on $4$-edge colorable, degree at most $4$, planar graphs
is $\mathsf{NP}$-complete.

###### Proof.

The proof of the Theorem 2.2 of [GJS76] uses a reduction from rainbow
$3$-coloring of planar graphs and replaces each vertex with high degree
(larger than $4$) by a gadget. The gadget reduces the degree to $4$. We modify
the gadget slightly to obtain a $4$-edge colorable graph. To do this, we
substitute the outer nodes of the gadget with a diamond graphs. For example,
see Figure 4 for the modified gadget for degree $3$ and $4$ nodes ($H_{3}$ and
$H_{4}$, respectively).

$\displaystyle H_{3}$ equivalent$\displaystyle H_{4}$ equivalent$\displaystyle
1$$\displaystyle 2$$\displaystyle 3$$\displaystyle 1$$\displaystyle
2$$\displaystyle 3$$\displaystyle 4$ Figure 4: Modified gadget, new nodes and
edges colored red, outer nodes colored blue

Given a hard instance $G$ of $3$-coloring, let $v_{1}$, $v_{2}$, $\ldots$,
$v_{k}$ be nodes of the degree $\geq 3$. Replace each $v_{i}$ of degree $r$
with the $H_{r}$ gadget. Neighbors of $v_{i}$ become outer vertices of the
gadget. Let $\widetilde{G}$ be the resultant graph.

Analogously to [GJS76] $\widetilde{G}$ is planar with maximum degree $4$.
Moreover, $\widetilde{G}$ is $3$-colorable if and only if $G$ is
$3$-colorable. For any $3$-coloring, the endpoints of each diamond must be
colored by the same color. Since, the original gadgets from [GJS76] are
$3$-colorable, every proper $3$-coloring of $G$ can be extended to a proper
coloring of $\widetilde{G}$.

Now we show that $\widetilde{G}$ is $4$-edge colorable. Every vertex of the
diamond which is not adjacent to the original gadget in [GJS76] has degree
$3$. Therefore, regardless of the color of the edges outside the diamond, the
two edges connected to original gadget can be colored arbitrarily. Therefore
any edge-coloring of the rest of the graph (excluding all of the modified
$H_{r}$) can be extended to a proper $4$-edge coloring including the $H_{r}$
if the unmodified $H_{r}$ is $4$-edge colorable for every $r$. Since the graph
excluding all $H_{r}$’s has max degree at most $3$ (excluding the $H_{r}$’s in
the sense of treating edges incident to outlet nodes as edges to degree $1$
vertices), it has a proper $4$-edge coloring by Vizing’s theorem. Moreover,
such a coloring can be found in polynomial time [MG92].

It is easy to check that $H_{r}$ admits a proper $4$-edge coloring for all
$r$. For example, see the two composable proper $4$-edge colorings of the
unmodified $H_{3}$ in Figure 5.

Figure 5: Proper $4$-edge colorings of unmodified $H_{3}$

∎

######  Lemma A.2.

$3$-edge coloring is $\mathsf{NP}$-hard, even on cut-edge free graphs of
degree at most $3$.

###### Proof.

We reduce from $3$-edge coloring on $3$-regular graphs. This is known to be
$\mathsf{NP}$-hard [Hol81]. Let $G=(V,E)$ be an instance of $3$-edge coloring
on a degree at most $3$ graph. Suppose that $e=(u,v)\in E$ is a cut edge. Let
$G_{u}$ and $G_{v}$ be the two disconnected components of $G$ obtained by
deleting the edge $e$. Note that $u$ and $v$ each have degree at most $2$ in
$G_{u}$ and $G_{v}$, respectively. Since $G_{u}$ and $G_{v}$ are only
connected in $G$ via $e$, if both are $3$-edge colorable, we can assume
without loss of generality that their $3$-edge colorings color the non-$e$
edges incident to $u$ and $v$ with a total of two distinct colors. Namely, we
can set $e$ to be the third color to obtain a proper $3$-edge coloring of $G$.
Clearly if $G$ is $3$-edge colorable then each of its subgraphs must be
properly $3$-edge colorable. Hence, finding a proper $3$-edge coloring of $G$
reduces to finding a proper $3$-edge coloring of $G_{u}$ and $G_{v}$ (we can
find $e$ in polynomial time using a DFS).

Moreover, we can assume that $G$ is connected (or else reduce to considering
its connected components separately) and, if $G$ has a vertex of degree $1$,
it necessarily still contains a cut edge (the edge to that vertex).
Additionally, any graph of degree at most $2$ is a disjoint union of cycles
and paths and it is easy to compute a proper $3$-edge coloring for it.

Then, if there were a polynomial time algorithm for $3$-edge coloring on cut-
edge free graphs of degree at most $3$, we could partition any degree at most
$3$ input into cut-edge free subgraphs, apply the algorithm, and determine
$3$-edge colorability for the whole graph. $\mathsf{NP}$-hardness of $3$-edge
coloring on $3$-regular graphs then implies the desired result. ∎

##  Appendix B Barriers to Proving Hardness of
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$

In this section, we give several necessary conditions for a
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ clustering instance to be hard.

The section is structured as follows. In the Euclidean setting, we outline a
nontrivial approximation algorithm for $\mathsf{Max}$-$k$-$\mathsf{Diameter}$
which is a basic corollary of a $(1+\varepsilon)$-approximation algorithm for
constant $k$-center [BHPI02]. By analyzing this algorithm, we show strong
conditions under which $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ is in
$\mathsf{P}$. In the $\ell_{1}$ setting, we mention other obstacles to proving
hardness related to the framework of $r$-embeddings used throughout Section 4.

###  B.1 Large Odd Girth Barrier

In this section, we prove that instances of $3$-clustering that are hard to
approximate within a factor of $\sqrt{2}-\varepsilon$ must be contained in a
ball of radius $\sqrt{2}$. We mention a graph theoretic implication of this
restriction related to the existence of short odd cycles.

######  Definition B.1 ($k$-center clustering problem).

Let $(X,\text{dist})$ be a metric space and $k\in\mathbb{N}$. Given as input a
finite set $P\subset X$, find a $k$-clustering
$\\{A_{1},\ldots,A_{k}\\}\subset P$ and a collection of “centers”
$\\{a_{1},\ldots,a_{k}\\}$ that minimizes

$\max_{i\in[k],\,x\in A_{i}}\text{dist}(x,a_{i}).$

######  Theorem B.1 (follows from [BHPI02]).

Let $\varepsilon>0$ and $k$ a constant. In Euclidean space,
$(\sqrt{2}+\varepsilon)$-approximate $k$-clustering is in $\mathsf{P}$.

###### Proof.

From [BHPI02], $(1+\varepsilon)$-approximation of Euclidean $k$-center is in
$\mathsf{P}$. By Jung’s theorem [DGK63], any set of points with diameter
$\Delta$ is contained in a closed ball with radius $r$ satisfying

$r\leq\Delta\sqrt{\frac{n}{2(n+1)}}\leq\frac{\Delta}{\sqrt{2}}$

Let $\Delta$ be the optimal $\mathsf{Max}$-$k$-$\mathsf{Diameter}$ of the
given set of points. Applying Jung’s theorem, the optimal clustering for the
$k$-center objective will have diameter

$\Delta^{\prime}=2r\leq\Delta\sqrt{2}$

Therefore, $(1+\varepsilon)$-approximation of $k$-center immediately gives
$(\sqrt{2}+\varepsilon)$-approximation of
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$. ∎

######  Theorem B.2.

Let $\varepsilon>0$ be a sufficiently small constant. Then, there exists a
polynomial time $(\sqrt{2}-\varepsilon)$-approximation algorithm for
$3$-clustering, when restricted to pointsets $P$ not contained in a bounding
sphere with diameter $\Delta\cdot\left(\sqrt{2}+50\varepsilon^{1/8}\right)$,
where $\Delta$ is the optimal $3$-diameter of $P$.

###### Proof.

Let $\varepsilon^{\prime}=45\varepsilon^{1/4}$ and fix a pointset $P$ not
contained in any bounding sphere with diameter
$\sqrt{2}+\varepsilon^{\prime}$. By scaling, we can assume that
$\Delta=\frac{\sqrt{2}}{\sqrt{2}+\varepsilon}$ without loss of generality. Let
$A\cup B\cup C$ be an optimal $3$-clustering of $P$.

We run the algorithm from Theorem B.1 on the pointset $P$, with approximation
factor $\sqrt{2}+\varepsilon$, hence obtaining a $3$-clustering of $P$ with
diameter at most $\Delta\cdot(\sqrt{2}+\varepsilon)=\sqrt{2}$. Theorem 2.7 of
[BHPI02] gives that all three clusters can be written as the intersection of
balls in $\mathbb{R}^{q}$ with the pointset $P$, with points contained in
multiple balls assigned arbitrarily. Moreover, we desire a stronger property:
that the optimal clusters $A,B,C$ are each contained in one of these balls.
Slightly extending their algorithm by returning all $3$-clusterings enumerated
by the simulation of the “guessing oracle”, we can ensure that one of the
returned $3$-clusterings achieves a $(\sqrt{2}+\varepsilon)$-approximation
factor as well as the desired property. It suffices to run the following
procedure over all of these $3$-clusterings. On at least one iteration, the
desired approximation will hold.

Let $N_{A},N_{B},N_{C}$ be balls of diameter $\sqrt{2}$ that contain $A,B,C$,
respectively. Let $a,b,c$ be their respective centers. We now split into two
cases which, by a relabeling argument, are exhaustive.

  * •

Case I: $N_{A}\cap N_{B},\,N_{A}\cap N_{C},\,N_{B}\cap N_{C}$ each have
diameter $\leq\sqrt{2}-\varepsilon$. In this case, we have the following
algorithm:

    1. 1.

For each point $p\in P$, initialize a set $S_{p}$ as follows:

$S_{p}=\\{X\in\\{A,B,C\\}\mathrel{\mathop{\ordinarycolon}}p\in N_{X}\\}$

as the set of balls that contain $p$.

    2. 2.

For every pair of points $p,q\in P$ such that $\left\lVert
p-q\right\rVert_{2}>\Delta$, if $S_{p}$ contains only one element, and $S_{q}$
contains that element, remove it from $S_{q}$. Repeat this until no such
removals are possible.

    3. 3.

Let

$\displaystyle A^{\prime}$
$\displaystyle\mathrel{\mathop{\ordinarycolon}}=\\{p\in
P\mathrel{\mathop{\ordinarycolon}}A\in S_{p},B\not\in S_{p}\\}$ $\displaystyle
B^{\prime}$ $\displaystyle\mathrel{\mathop{\ordinarycolon}}=\\{p\in
P\mathrel{\mathop{\ordinarycolon}}B\in S_{p},C\not\in S_{p}\\}$ $\displaystyle
C^{\prime}$
$\displaystyle\mathrel{\mathop{\ordinarycolon}}=P\setminus(A^{\prime}\cup
B^{\prime}).$

Output the $3$-clustering $\\{A^{\prime},B^{\prime},C^{\prime}\\}$.

We can show that the following property remains true throughout the iterations
of step 2 of the algorithm: if $p$ is in some optimal cluster
$X\in\\{A,B,C\\}$, then $X\in S_{p}$. It is true in the initialization of
$S_{p}$ in step 1 of the algorithm. We only remove $X$ from $S_{p}$ if there
exists some $q$ such that $\left\lVert p-q\right\rVert_{2}>\Delta$, and $q\in
X$. So, $p$ cannot be in $X$, because the optimal clustering $\\{A,B,C\\}$ has
diameter $\Delta$. Thus, if $p\in X$, then $X\in S_{p}$.

Let $p,q\in A^{\prime}$. Note that $A\in S_{p}$ and $A\in S_{q}$ by
definition. If $S_{p}=\\{A\\}$ or $S_{q}=\\{A\\}$, then $\left\lVert
p-q\right\rVert_{2}\leq\Delta$, or $A$ would have been removed. In all other
possible cases, $C\in S_{p}$ and $C\in S_{q}$. So, $p,q\in N_{A}\cap N_{C}$.
Thus, $\left\lVert p-q\right\rVert_{2}\leq\sqrt{2}-\varepsilon$.

Similarly, if $p,q\in B^{\prime}$, then either $\left\lVert
p-q\right\rVert_{2}\leq\Delta$ or $p,q\in N_{A}\cap N_{B}$. If $p,q\in
C^{\prime}$, then either $\left\lVert
p-q\right\rVert_{2}\leq\Delta\leq\sqrt{2}-\varepsilon$ or $p,q\in N_{C}\cap
N_{B}$. In all cases, $\left\lVert
p-q\right\rVert_{2}\leq\sqrt{2}-\varepsilon$, so our $3$-clustering has
diameter at most $\sqrt{2}-\varepsilon$.

  * •

Case II: $N_{A}\cap N_{B}$ has diameter $>\sqrt{2}-\varepsilon$. We claim
that, in this case, the diameter of $C\cap(A\cup B)$ is at most
$\sqrt{2}-\varepsilon$. Given that this is true consider the following
algorithm:

    1. 1.

For each point $p\in P$, initialize

$S_{p}=\\{X\in\\{A,B,C\\}\mathrel{\mathop{\ordinarycolon}}p\in N_{X}\\}$

as the set of balls that contain $p$, as in Case I.

    2. 2.

For every pair of points $p,q\in P$ such that $\left\lVert
p-q\right\rVert_{2}>\Delta$, if $S_{p}$ contains only one element, and $S_{q}$
contains that element, remove it from $S_{q}$. Repeat this until no such
removals are possible, as in Case I.

    3. 3.

Let

$\displaystyle C^{\prime}$
$\displaystyle\mathrel{\mathop{\ordinarycolon}}=\\{p\in
P\mathrel{\mathop{\ordinarycolon}}C\in S_{p}\\}.$

Find an optimal $2$-clustering of $P\setminus C^{\prime}$, and call the output
clusters $A^{\prime}$ and $B^{\prime}$. Output the clustering
$A^{\prime},B^{\prime},C^{\prime}$.

Note that for any point $p\in P\setminus C^{\prime},$ we have that $C\not\in
S_{p}$. Thus, $P\setminus C^{\prime}\subseteq A\cup B$, so there exists a
2-clustering of $P\setminus C^{\prime}$ of diameter at most $\Delta$. So,
$A^{\prime}$ and $B^{\prime}$ have diameter at most $\Delta$.

Now, for any $p,q\in C^{\prime}$, if $S_{p}=\\{C\\}$ or $S_{q}=\\{C\\}$, then
$\left\lVert p-q\right\rVert_{2}\leq\Delta$, or $C$ would have been removed.
So, if $\left\lVert p-q\right\rVert_{2}>\Delta$, then both $S_{p}$ and $S_{q}$
contain either $A$ or $B$. In this case, $p,q\in C\cap(A\cup B)$, so
$\left\lVert p-q\right\rVert_{2}\leq\sqrt{2}-\varepsilon$. Hence, the
clustering $\\{A^{\prime},B^{\prime},C^{\prime}\\}$ has diameter at most
$\sqrt{2}-\varepsilon$.

It remains to verify our claim that $C\cap(A\cup B)$ has diameter at most
$\sqrt{2}-\varepsilon$. First, observe that $N_{A}\cup N_{B}$ are contained
within a ball $N_{D}$ whose center $d$ is the midpoint between $a$ and $b$ and
whose radius is $\frac{\alpha+\sqrt{2}}{2}$, where
$\alpha\mathrel{\mathop{\ordinarycolon}}=\left\lVert a-b\right\rVert_{2}$.
Since $N_{A}\cap N_{B}$ has diameter at least $\sqrt{2}-\varepsilon$, by the
Pythagorean Theorem we have:

$\alpha\leq
2\sqrt{\left(\frac{\sqrt{2}}{2}\right)^{2}-\left(\frac{\sqrt{2}-\varepsilon}{2}\right)^{2}}=\sqrt{2\varepsilon\sqrt{2}-\varepsilon^{2}}.$

Now, we apply the fact that $P$ is not contained in a bounding sphere of
diameter $\Delta\cdot(\sqrt{2}+\varepsilon^{\prime})$. If
$\varepsilon^{\prime}\geq 2\varepsilon$, we observe that

$\Delta\cdot(\sqrt{2}+\varepsilon^{\prime})=\sqrt{2}\cdot\frac{\sqrt{2}+\varepsilon^{\prime}}{\sqrt{2}+\varepsilon}=\sqrt{2}+\sqrt{2}\cdot\frac{\varepsilon^{\prime}-\varepsilon}{\sqrt{2}+\varepsilon}\geq\sqrt{2}+\sqrt{2}\cdot\frac{\varepsilon^{\prime}/2}{\sqrt{2}}=\sqrt{2}+\frac{\varepsilon^{\prime}}{2}.$

Hence, it is also true that $P$ is not contained in a bounding sphere of
diameter $\sqrt{2}+\frac{\varepsilon^{\prime}}{2}$. The same is true for
$N_{C}\cup N_{D}$, since $P\subset N_{C}\cup N_{D}$, meaning:

$\displaystyle\sqrt{2}+\frac{\varepsilon^{\prime}}{2}$
$\displaystyle\leq\text{diameter}(N_{C}\cup N_{D})$
$\displaystyle\leq\left\lVert
c-d\right\rVert_{2}+\text{radius}(N_{C})+\text{radius}(N_{D})$
$\displaystyle=\left\lVert
c-d\right\rVert_{2}+\frac{\sqrt{2}}{2}+\frac{\alpha+\sqrt{2}}{2}$
$\displaystyle=\left\lVert c-d\right\rVert_{2}+\frac{\alpha}{2}+\sqrt{2}.$

Hence, $\left\lVert
c-d\right\rVert_{2}\geq\varepsilon^{\prime}-\frac{\alpha}{2}$. Finally, let
$h$ denote the diameter of $N_{C}\cap N_{D}$; since $A\cup B\subset N_{D}$ and
$C\subseteq N_{C}$, it suffices to show that $h\leq\sqrt{2}-\varepsilon$. By
the Pythagorean Theorem, we have:

$\displaystyle\frac{h}{2}$
$\displaystyle\leq\sqrt{\text{radius}(N_{D})^{2}-\left(\frac{\left\lVert
c-d\right\rVert_{2}}{2}\right)^{2}}$
$\displaystyle\leq\frac{1}{2}\cdot\sqrt{(\alpha+\sqrt{2})^{2}-\left(\frac{\varepsilon^{\prime}-\alpha}{2}\right)^{2}}$
$\displaystyle=\frac{1}{2}\cdot\sqrt{\frac{3\alpha^{2}}{4}+2\alpha\sqrt{2}+\frac{\alpha\varepsilon^{\prime}}{2}+2-\frac{{\varepsilon^{\prime}}^{2}}{4}}$

Hence, it suffices to show that:

$(\sqrt{2}-\varepsilon)^{2}=2-2\varepsilon\sqrt{2}+\varepsilon^{2}\geq\frac{3\alpha^{2}}{4}+\left(2\sqrt{2}+\frac{\varepsilon^{\prime}}{2}\right)\cdot\alpha+2-\frac{{\varepsilon^{\prime}}^{2}}{4}$

From here, we provide a sequence of stronger inequalities, eventually showing
that our setting of $\varepsilon^{\prime}=60\varepsilon^{1/4}$ is satisfies
the above inequality. First, recall that
$\alpha\leq\sqrt{2\varepsilon\sqrt{2}-\varepsilon^{2}}$. Thus, it is
sufficient to have

$2-2\varepsilon\sqrt{2}+\varepsilon^{2}\geq\frac{6\varepsilon\sqrt{2}-3\varepsilon^{2}}{4}+\left(2\sqrt{2}+\frac{\varepsilon^{\prime}}{2}\right)\sqrt{2\varepsilon\sqrt{2}-\varepsilon^{2}}+2-\frac{{\varepsilon^{\prime}}^{2}}{4}$

Subtracting $(2+\frac{6\varepsilon\sqrt{2}-3\varepsilon^{2}}{4})$ from both
sides, it is equivalent that

$\frac{7}{4}(\varepsilon^{2}-2\varepsilon\sqrt{2})\geq\left(2\sqrt{2}+\frac{\varepsilon^{\prime}}{4}\right)\sqrt{2\varepsilon\sqrt{2}-\varepsilon^{2}}-\frac{{\varepsilon^{\prime}}^{2}}{4}$

Applying the trivial bound $\varepsilon^{2}\geq 0$, it is sufficient that

$-\frac{7\varepsilon}{\sqrt{2}}\geq\left(2\sqrt{2}+\frac{\varepsilon^{\prime}}{2}\right)\sqrt{2\varepsilon\sqrt{2}}-\frac{{\varepsilon^{\prime}}^{2}}{4}$

For $\varepsilon^{\prime}\leq 1$, we have
$\left(2\sqrt{2}+\frac{\varepsilon^{\prime}}{2}\right)\sqrt{2\sqrt{2}}<6$, so
it would be sufficient if

$-\frac{7\varepsilon}{\sqrt{2}}\geq
6\sqrt{\varepsilon}-\frac{{\varepsilon^{\prime}}^{2}}{4}.$

Rearranging, we have:

${\varepsilon^{\prime}}^{2}\geq
24\sqrt{\varepsilon}+\frac{28\varepsilon}{\sqrt{2}}.$

Finally, for $\varepsilon\leq 1$ it is true that
$\varepsilon\leq\sqrt{\varepsilon}$, and since $24+\frac{28}{\sqrt{2}}<45$, it
is good enough to have

${\varepsilon^{\prime}}^{2}\geq 45\sqrt{\varepsilon}$

This is satisfied when $\varepsilon^{\prime}=45\varepsilon^{1/4}.$ Note that
our argument relied on $\varepsilon\leq 1$, $\varepsilon^{\prime}\leq 1$ and
$\varepsilon^{\prime}\geq 2\varepsilon$ all holding. One can verify that for
$\varepsilon^{\prime}=45\varepsilon^{1/4}$, all of these bounds are true when
$\varepsilon$ is sufficiently small.

In both cases, then, we produced an algorithm which outputs a $3$-clustering
with diameter at most $\sqrt{2}-\varepsilon$. Since the optimal $3$-clustering
has diameter $\Delta=\frac{\sqrt{2}}{\sqrt{2}+\varepsilon}$, we achieve an
approximation ratio of:

$\frac{\sqrt{2}-\varepsilon}{\Delta}=\frac{(\sqrt{2}-\varepsilon)(\sqrt{2}+\varepsilon)}{\sqrt{2}}=\frac{2-\varepsilon^{2}}{\sqrt{2}}=\sqrt{2}-\frac{\varepsilon^{2}}{\sqrt{2}}.$

We have demonstrated a
$(\sqrt{2}-\frac{\varepsilon^{2}}{\sqrt{2}})$-approximation algorithm for
pointsets not contained in a bounding sphere of diameter
$\Delta\cdot\left(\sqrt{2}+45\varepsilon^{1/4}\right)$. By a change of
variables $\varepsilon\mapsto 2^{1/4}\sqrt{\varepsilon}$, this proves the
original statement, since it gives a $(\sqrt{2}-\varepsilon)$-approximation
for pointsets not contained in a bounding sphere with diameter

$\Delta\cdot\left(\sqrt{2}+45\left(2^{1/4}\sqrt{\varepsilon}\right)^{1/4}\right)=\Delta\cdot\left(\sqrt{2}+45\cdot
2^{1/16}\varepsilon^{1/8}\right).$

Since $45\cdot 2^{1/16}<50$, this algorithm also holds for pointsets not
contained in a bounding sphere with diameter
$\Delta\cdot\left(\sqrt{2}+50\varepsilon^{1/8}\right)$, which is what we
wanted to show.

∎

This means that if we hope to prove hardness of $\sqrt{2}$-approximation, we
need the pointset to to lie inside a sphere of diameter $\sqrt{2}$. In all of
our hardness proofs, we have thought of clustering a pointset $P$ as
equivalent to coloring the graph on $P$ where long distances form the edges.
On a sphere, far away points must be almost diametrically opposite. This
implies that the coloring instance cannot have small odd cycles. We formalize
this statement with the following definition and theorem.

######  Definition B.2 (Odd Girth).

Given a graph $G$, we say that the odd girth of $G$ is the length of the
smallest odd cycle. If there are no odd cycles, we say that the odd girth is
infinite.

######  Theorem B.3.

For any $C\in\mathbb{N}$, there exists an $\varepsilon>0$ such that
$(\sqrt{2}-\varepsilon)$-approximate 3-clustering is in $\mathsf{P}$, when
restricted to pointsets $P$ such that $\Gamma_{k,\sqrt{2}-\varepsilon}(P)$ has
odd girth at most $C$.

###### Proof.

Assume via scaling without loss of generality that the optimal $3$-clustering
diameter of $P$ is 1. We will prove that for small enough $\varepsilon$, there
is no pointset $P$ contained in a ball of diameter $\sqrt{2}+\varepsilon$ such
that $\Gamma_{k,\sqrt{2}-\varepsilon}(P)$ is an odd cycle of length less than
$C$. Then, the statement follows from Theorem B.2.

So, suppose for contradiction that $P$ is as described above. Since the
optimal diameter is $1$, all edges in $\Gamma_{k,\sqrt{2}-\varepsilon}(P)$
have length at least $\sqrt{2}-\varepsilon$. Let $x,y\in P$ such that the
corresponding points in $\Gamma_{k,\sqrt{2}-\varepsilon}(P)$ are neighbors.
Note that since the cycle is odd, there is an even length path between $x$ and
$y$ in $\Gamma_{k,\sqrt{2}-\varepsilon}(P)$ that has length less than $C$. Let
$x=x_{0},x_{1},\dots,x_{m}=y\in P$ be every other point along this path. Note
that for any $\delta>0$, there is an $\varepsilon>0$ such that any two points
that share a neighbor must be at most distance $\delta$ apart. Let
$\delta=\sqrt{2}/C$. Then, by triangle inequality, we have

$\left\lVert x-y\right\rVert_{2}\leq
m\cdot\frac{\sqrt{2}}{C}<\sqrt{2}-\varepsilon.$

However, since $x$ and $y$ are neighbors, $\left\lVert
x-y\right\rVert_{2}\geq\sqrt{2}-\varepsilon$, and we have a contradiction. ∎

###  B.2 Barrier in $\ell_{1}$ Space

In Section 4, we showed hardness results within a factor of $r$ for
$\mathsf{Max}$-$k$-$\mathsf{Diameter}$ as follows. We constructed graph
families $G$ on which $3$-coloring is $\mathsf{NP}$-hard, produced an
$r$-embedding $\phi$ of $G$ (Definition 3.1), and concluded that
$\phi(G)\subset\\{0,1\\}^{q}$ is a hard instance of $3$-clustering. In this
subsection, we show that this framework is too rigid to prove hardness within
a factor of $r$ for $r>5/3$.

######  Definition B.3.

Let $G$ and $H$ be graphs. We say that $G$ is $H$-free if no induced subgraph
of $G$ is isomorphic to $H$.

######  Theorem B.4.

Let $H$ be a graph such that $H$-free $k$-coloring is in P and H is not
$(r+\varepsilon)$-embeddable, where $\varepsilon>0$. Then, exact
$k$-clustering can be solved in polynomial time when restricted to pointsets
$P$ such that $\Gamma_{k,r}(P)=\Gamma_{k,1}(P)$.

###### Proof.

Let $\mathcal{A}$ be a polynomial time algorithm which runs $k$-coloring on
$H$-free graphs. We observe that the graph $\Gamma_{k,r}(P)$ must be $H$-free,
or else $\Gamma_{k,r}^{-1}(H)\subset P$ would give an
$(r+\varepsilon)$-embedding of $H$. By running $\mathcal{A}$ on
$\Gamma_{k,r}(P)$, we obtain a $k$-coloring. By assumption, this is also a
valid $k$-coloring of $\Gamma_{k,1}(P)$. This corresponds to an exact
$k$-clustering of $P$, as desired. ∎

Theorem B.4 can be viewed as a way to show that certain instances of
$k$-clustering are not hard to compute exactly, let alone hard to approximate.
In order to make use of the theorem, we must find graphs $H$ such that
$k$-coloring $H$-free graphs can be done efficiently.

######  Lemma B.5.

[BCM+18] Let $P_{7}$ denote the path graph on $7$ vertices. There exists a
polynomial time algorithm to $3$-color $P_{7}$-free graphs.

######  Corollary B.6.

Exact $k$-clustering can be solved in polynomial time when restricted to
pointsets $P$ such that $\Gamma_{k,5/3}(P)=\Gamma_{k,1}(P)$.

###### Proof.

Using the method in Appendix C, we verify that the graph $P_{7}$ is not
$r$-embeddable for any $r>5/3$. Applying Lemma B.5 and Theorem B.4 gives the
result. ∎

######  Remark B.1.

Corollary B.6 provides a barrier to our technique in Section 4. It implies
that if $\phi$ is an $r$-embedding, then for $r>5/3$ the pointset
$\phi(\widehat{G})$ is easy to optimally $3$-cluster, provided that the
optimal $3$-clustering of $\phi(\widehat{G})$ has diameter equal to the short
distance of $\phi$.

##  Appendix C Testing $r$-embeddability with a Linear Program

It turns out finding the largest ratio $r$ for which a given graph $H$ is
$r$-embeddable into $(\\{0,1\\}^{q},\ell_{1})$ can be framed as the solution
to a certain linear program. To see this, let $H$ be a graph on $n$ vertices
labeled $v_{1},v_{2},\ldots,v_{n}$, and let $\phi$ be an $r$-embedding of $H$
into the space $\\{0,1\\}^{q}$, with short distance $s$. For each
$w\in\\{0,1\\}^{n}$, associate a nonnegative integer $x_{w}$ indicating the
number of indices $i\in[q]$ such that $(\phi(v_{j}))_{i}=w_{j}$ holds for all
$j\in[n]$. Then, distances in our embedded space can be written as the
following linear combination:

$\left\lVert\phi(v_{a})-\phi(v_{b})\right\rVert_{0}=\sum_{\begin{subarray}{c}w\in\\{0,1\\}^{n}\\\
w_{a}\neq w_{b}\end{subarray}}x_{w}.$

Then, for a given short distance parameter $s$, finding the largest possible
embeddability ratio $r$ is equivalent to solving the following optimization
problem over nonnegative integer variables
$\\{x_{w}\mathrel{\mathop{\ordinarycolon}}w\in\\{0,1\\}^{n}\\}$ and a rational
variable $r$:

$\begin{array}[]{ll@{}ll}\text{maximize}&r&\\\ \text{subject
to}&\begin{cases}\displaystyle\sum_{\begin{subarray}{c}w\in\\{0,1\\}^{n}\\\
w_{a}\neq w_{b}\end{subarray}}x_{w}\geq rs&\text{if }(v_{a},v_{b})\in E\\\
\displaystyle\sum_{\begin{subarray}{c}w\in\\{0,1\\}^{n}\\\ w_{a}\neq
w_{b}\end{subarray}}x_{w}\leq s&\text{if }(v_{a},v_{b})\notin
E\end{cases}\end{array}$

We can remove dependence on $s$ by simply setting $s=1$ and allowing each
$x_{w}$ to take any nonnegative rational value, obtaining the following linear
program:

$\begin{array}[]{ll@{}ll}\text{maximize}&r&\\\ \text{subject
to}&\begin{cases}\displaystyle\sum_{\begin{subarray}{c}w\in\\{0,1\\}^{n}\\\
w_{a}\neq w_{b}\end{subarray}}x_{w}\geq r&\text{if }(v_{a},v_{b})\in E\\\
\displaystyle\sum_{\begin{subarray}{c}w\in\\{0,1\\}^{n}\\\ w_{a}\neq
w_{b}\end{subarray}}x_{w}\leq 1&\text{if }(v_{a},v_{b})\notin
E\end{cases}\end{array}$

Moreover, since each of our constraints have integer coefficients, the
solution vector to this linear program will be rational. Thus, we can scale
each $x_{w}$ to be an integer, thus obtaining an embedding into
$\\{0,1\\}^{q}$ that achieves the optimal ratio $r$, where
$q=\displaystyle\sum_{\begin{subarray}{c}w\in\\{0,1\\}^{n}\end{subarray}}x_{w}\in\mathbb{N}$.

In particular, for a given graph $H$ and parameter $r>1$, this gives us a
computational way to check whether or not $H$ is $r$-embeddable in Hamming
space.