11institutetext: Faculty of Mathematics and Physics, Charles University, Czech
Republic
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Generalized $k$-Center:
Distinguishing Doubling and Highway Dimension††thanks: Andreas Emil Feldmann
was supported by the project 19-27871X of GA ČR. Tung Anh Vu was supported by
the project 22-22997S of GA ČR. An extended abstract of this paper appeared at
the 48th International Workshop on Graph-Theoretic Concepts in Computer
Science in 2022.

Andreas Emil Feldmann  0000-0001-6229-5332
Tung Anh Vu  0000-0002-8902-5196

###### Abstract

We consider generalizations of the $k$-Center problem in graphs of low
doubling and highway dimension. For the Capacitated $k$-Supplier with Outliers
(CkSwO) problem, we show an efficient parameterized approximation scheme
(EPAS) when the parameters are $k$, the number of outliers and the doubling
dimension of the supplier set. On the other hand, we show that for the
Capacitated $k$-Center problem, which is a special case of CkSwO, obtaining a
parameterized approximation scheme (PAS) is $\mathrm{W[1]}$-hard when the
parameters are $k$, and the highway dimension. This is the first known example
of a problem for which it is hard to obtain a PAS for highway dimension, while
simultaneously admitting an EPAS for doubling dimension.

###### Keywords:

Capacitated $k$-Supplier with Outliers Highway Dimension Doubling Dimension
Parameterized Approximation

##  1 Introduction

The well-known $k$-Center problem and its generalizations has plenty of
applications, for example selecting suitable locations for building hospitals
to serve households of a municipality (see [3] for a survey of healthcare
facility location in practice). In this setting, the number of hospitals we
can actually build is limited, e.g. by budgetary constraints. We want to
choose the locations so that the quality of the provided service is optimal,
and a societally responsible way of measuring the quality of service is to
ensure some minimal availability of healthcare to every household. We can
quantify this by measuring the distance of a household to its nearest
hospital, and then minimize this distance over all households. This strategy,
however, does not account for the reality that healthcare providers have
(possibly different) limits on the number of patients they can serve, and thus
we introduce capacity constraints. Furthermore, as the instances are given by
transportation networks, we model them by the titular doubling dimension and
highway dimension, which we define later.

We formalize the problem as follows. In the Capacitated $k$-Supplier (CkS)
problem, the input consists of a graph ${G=(V,E)}$ with positive edge lengths,
a set ${V_{S}\subseteq V}$ of _suppliers_ , a set ${V_{C}\subseteq V}$ of
_clients_ , a _capacity function ${L\colon V_{S}\to\bbbn}$_, and an integer
${k\in\bbbn}$. A _feasible solution_ is an _assignment function ${\phi\colon
V_{C}\to V_{S}}$_ such that ${\lvert\phi(V_{C})\rvert\leq k}$ and for every
supplier ${u\in\phi(V_{C})}$ we have ${\lvert\phi^{-1}(u)\rvert\leq L(u)}$.
For a pair of vertices ${u,v\in V}$ we denote by ${\mathrm{dist}_{G}(u,v)}$
the _shortest-path distance_ between vertices $u$ and $v$ with respect to edge
lengths of $G$. For a subset of vertices ${W\subseteq V}$ and a vertex ${u\in
V}$, we denote ${\mathrm{dist}_{G}(u,W)=\min_{w\in W}\mathrm{dist}_{G}(u,w)}$.
We omit the subscript $G$ if the graph is clear from context. The _cost_ of a
solution $\phi$ is defined as $\operatorname{cost}(\phi)=\max_{u\in
V_{C}}\mathrm{dist}(u,\phi(u))$ and we want to find a feasible solution of
minimum cost. Let us mention the following special cases of CkS. If
${V=V_{S}=V_{C}}$, then the problem is called Capacitated $k$-Center (CkC). If
${L(u)=\infty}$ for every supplier ${u\in V_{S}}$, then the problems are
called $k$-Supplier and $k$-Center respectively. It is known that $k$-Center
is already $\mathrm{NP}$-hard [28].

Two popular approaches of dealing with $\mathrm{NP}$-hard problems are
_approximation algorithms_ [33, 34] and _parameterized algorithms_ [14]. Given
an instance $\mathcal{I}$ of some minimization problem, a  _$c$ -approximation
algorithm_ computes in polynomial time a solution of cost at most
$c\cdot\mathrm{OPT}(\mathcal{I})$ where $\mathrm{OPT}(\mathcal{I})$ is the
optimum cost of the instance $\mathcal{I}$, and we say that $c$ is the
_approximation ratio_ of the algorithm. If the instance is clear from context,
we write only $\mathrm{OPT}$. In a _parameterized problem_ , the input
$\mathcal{I}$ comes with a _parameter $q\in\bbbn$_. If there exists an
algorithm which computes the optimum solution in time
$f(q)\cdot\lvert\mathcal{I}\rvert^{\mathcal{O}(1)}$ where $f$ is some
computable function, then we call such a problem _fixed parameter tractable
(FPT)_ and the algorithm an _FPT algorithm_. The rationale behind
parameterized algorithms is to capture the “difficulty” of the instance by the
parameter $q$ and then design an algorithm which is allowed to run in time
superpolynomial in $q$ but retains a polynomial running time in the size of
the input. In this work, we focus on the superpolynomial part of the running
time of $\mathrm{FPT}$ algorithms, so we will express
$f(q)\cdot\lvert\mathcal{I}\rvert^{\mathcal{O}(1)}$ as
$\mathcal{O}^{*}(f(q))$; in particular the “$\mathcal{O}^{*}$” notation
ignores the polynomial factor in the input size.

It is known that unless $\mathrm{P}=\mathrm{NP}$, $k$-Center and $k$-Supplier
do not admit approximation algorithms with an approximation ratio better than
2 and 3 [29]. It is shown in the same work that these results are tight by
giving corresponding approximation algorithms. For Capacitated $k$-Center, An
et al. [4] give a 9-approximation algorithm, and Cygan et al. [15] show a
lower bound111To the best of our knowledge, this reduction does not give a
straightforward hardness result in the parameterized setting. of
$3-\varepsilon$ for approximation assuming $\mathrm{P}\neq\mathrm{NP}$. From
the perspective of parameterized algorithms, Feldmann and Marx [23] show that
$k$-Center is $\mathrm{W[1]}$-hard in planar graphs of constant doubling
dimension when the parameters are $k$, highway dimension and pathwidth. Under
the standard assumption
$\mathrm{FPT}\subsetneq\mathrm{W[1]}\subsetneq\mathrm{W[2]}$, this means that
an $\mathrm{FPT}$ algorithm for $k$-Center in planar constant doubling
dimension graphs with the aforementioned parameters is unlikely to exist. To
overcome these hardness results, we will design _parameterized
$c$-approximation algorithms_, which are algorithms with FPT runtime which
output a solution of cost at most $c\cdot\mathrm{OPT}$. The approach of
parameterized approximation algorithms has been studied before, see the survey
in [22].

Let us discuss possible choices for a parameter for these problems. An
immediate choice would be the size $k$ of the desired solution. Unfortunately,
Feldmann [20] has shown that approximating $k$-Center within a ratio better
than 2 when the parameter is $k$ is $\mathrm{W[2]}$-hard. So to design
parameterized approximation algorithms, we must explore other parameters.
Guided by the introductory example, we focus on parameters which capture
properties of transportation networks.

Abraham et al. [2] introduced the _highway dimension_ in order to explain fast
running times of various shortest-path heuristics in road networks. The
definition of highway dimension is motivated by the following empirical
observation of Bast et al. [5, 6]. Imagine we want to travel from some point
$A$ to some sufficiently far point $B$ along the quickest route. Then the
observation is that if we travel along the quickest route, we will inevitably
pass through a sparse set of “access points”. Highway dimension measures the
sparsity of this set of access points around any vertex of a graph. We give
one of the several formal definitions of highway dimension, see [8, 21]. Let
$(X,\mathrm{dist})$ be a metric, for a point $u\in X$ and a radius
$r\in\bbbr^{+}$ we call the set $B_{u}(r)=\\{v\in X\mid\mathrm{dist}(u,v)\leq
r\\}$ the _ball of radius $r$ centered at $u$_.

######  Definition 1 ([21])

The _highway dimension_ of a graph $G$ is the smallest integer $h$ such that,
for some universal constant222See [21, Section 9] for a discussion. In
essence, the highway dimension of a given graph can vary depending on the
selection of $\gamma$. $\gamma\geq 4$, for every $r\in\bbbr^{+}$, and every
ball $B_{v}(\gamma r)$ of radius $\gamma r$ where $v\in V(G)$, there are at
most $h$ vertices in $B_{v}(\gamma r)$ hitting all shortest paths of length
more than $r$ that lie in $B_{v}(\gamma r)$.

We show the following hardness of parameterized approximation for CkC in low
highway dimension graphs. Among the definitions of highway dimensions, the one
we use gives us the strongest hardness result, cf. [8, 21].

###### Theorem 1.1

Consider any universal constant $\gamma$ in Definition 1. For any
$\varepsilon>0$, there is no parameterized
$((1+\frac{1}{\gamma})-\varepsilon)$-approximation algorithm for CkC with
parameters $k$, treewidth333See Appendix 5 for a formal definition., and
highway dimension unless $\mathrm{FPT}=\mathrm{W[1]}$.

Another parameter we consider is _doubling dimension_ , defined as follows.

###### Definition 2

The _doubling constant_ of a metric space $(X,\mathrm{dist})$ is the smallest
value $\lambda$ such for every $x\in X$ and every radius $r\in\bbbr^{+}$,
there exist at most $\lambda$ points $y_{1},\ldots,y_{\lambda}\in X$ such that
$B_{u}(r)\subseteq\cup_{i=1}^{\lambda}B_{y_{i}}(\frac{r}{2})$. We say that the
ball $B_{x}(r)$ is _covered_ by balls
$B_{y_{1}}(\frac{r}{2}),\ldots,B_{y_{\lambda}}(\frac{r}{2})$. The _doubling
dimension_ $\Delta(X)$ of $X$ is defined as $\log_{2}(\lambda)$. The doubling
dimension of a graph is the doubling dimension of its shortest path metric.

Folklore results show that every metric for which the distance function is
given by the $\ell_{q}$-norm in $D$-dimensional space $\bbbr^{D}$ has doubling
dimension $\mathcal{O}(D)$. As a transportation network is embedded on a large
sphere (namely the Earth), a reasonable model is to assume that the shortest-
path metric abides to the Euclidean $\ell_{2}$-norm. Buildings in cities form
city blocks, which form a grid of streets. Therefore it is reasonable to
assume that the distances in cities are given by the Manhattan
$\ell_{1}$-norm. Road maps can be thought of as a mapping of a transportation
network into $\bbbr^{2}$. It is then sensible to assume that transportation
networks have constant doubling dimension.

Prior results on problems in graphs of low doubling and highway dimension went
“hand in hand” in the following sense. For the $k$-Median problem
parameterized by the doubling dimension, Cohen-Addad et al. [13] show an
_efficient parameterized approximation scheme (EPAS)_ , which is a
parameterized algorithm that for some parameter $q$ and any $\varepsilon>0$
outputs a solution of cost at most $(1+\varepsilon)\mathrm{OPT}$ and runs in
time $\mathcal{O}^{*}(f(q,\varepsilon))$ where $f$ is a computable function.
In graphs of constant highway dimension, Feldmann and Saulpic [24] follow up
with a _polynomial time approximation scheme (PTAS)_ for $k$-Median. If we
allow $k$ as a parameter as well, then Feldmann and Marx [23] show an EPAS for
$k$-Center in low doubling dimension graphs, while Becker et al. [7] show an
EPAS for $k$-Center in low highway dimension graphs. By using the result of
Talwar [32] one can obtain _quasi-polynomial time approximation
schemes(QPTAS)_ for problems such as TSP, Steiner Tree, and Facility Location
in low doubling dimension graphs. Feldmann et al. [21] extend this result to
low highway dimension graphs and obtain analogous QPTASs. The takeaway is that
approximation schemes for low doubling dimension graphs can be extended to the
setting of low highway dimension graphs. In light of Theorem 1.1, we would
then expect that CkC is also hard in graphs of low doubling dimension.

Our main contribution lies in breaking the status quo by showing an EPAS for
CkC in low doubling dimension graphs. This is the first example of a problem,
for which we provably cannot extend an algorithmic result in low doubling
dimension graphs to the setting of low highway dimension graphs.444We remark
that for this distinction to work, one has to be careful of the used
definition of highway dimension: a stricter definition of highway dimension
from [1] already implies bounded doubling dimension. On the other hand, for
certain types of transportation networks, it can be argued that the doubling
dimension is large, while the highway dimension is small. See [24, Appendix A]
for a detailed discussion. In fact, our algorithm even works in the supplier
with outliers regime, where we are allowed to ignore some clients: in the
Capacitated $k$-Supplier with Outliers (CkSwO) problem, in addition to the CkS
input $(G,k,L)$, we are given an integer $p$. A _feasible solution_ is an
_assignment_ $\phi\colon V_{C}\to V_{S}\cup\\{\bot\\}$ which, in addition to
the conditions specified in the definition of CkS, satisfies
$\lvert\phi^{-1}(\bot)\rvert\leq p$. Vertices $\phi^{-1}(\bot)$ are called
_outliers_. The goal is to find a solution of minimum cost, which is defined
as $\operatorname{cost}(\phi)=\max_{u\in
V_{C}\setminus\phi^{-1}(\bot)}\mathrm{dist}(u,\phi(u))$. Facility location and
clustering with outliers were introduced by Charikar et al. [11]. Among other
results, they showed a 3-approximation algorithm for $k$-Center with Outliers
and an approximation lower bound of $2-\varepsilon$. Later, Harris et al. [27]
and Chakrabarty et al. [10] independently closed this gap and showed a
2-approximation algorithm for the problem. For CkSwO, Cygan and Kociumaka [16]
show a 25-approximation algorithm. It may be of interest that the algorithm we
show requires only that the doubling dimension of the supplier set to be
bounded.

###### Theorem 1.2

Let $\mathcal{I}=(G,k,p,L)$ be an instance of Capacitated $k$-Supplier with
Outliers. Moreover, let $(V_{S},\mathrm{dist})$ be the shortest-path metric
induced by $V_{S}$ and $\Delta$ be its doubling dimension. There exists an
algorithm which for any $\varepsilon>0$ outputs a solution of cost
$(1+\varepsilon)\mathrm{OPT}(\mathcal{I})$ in time
$\mathcal{O}^{*}((k+p)^{k}\cdot\varepsilon^{-\mathcal{O}(k\Delta)})$.

In light of the following results, this algorithm is almost the best we can
hope for. We have already justified the necessity of approximation by the
result of Feldmann and Marx [23]. An EPAS parameterized only by $\Delta$ is
unlikely to exist, as Feder and Greene [19] have shown that unless
${\mathrm{P}=\mathrm{NP}}$, approximation algorithms with ratios better than
$1.822$ and 2 for two-dimensional Euclidean, resp. Manhattan metrics cannot
exist. Hence it is necessary to parameterize by both $k$ and $\Delta$. The
only improvement we can hope for is a better dependence on the number of
outliers in the running time, e.g. by giving an algorithm which is polynomial
in $p$.

Given our hardness of approximation result for CkC on low highway dimension
graphs in Theorem 1.1 and the known EPAS for $k$-Center given by Becker et al.
[7], it is evident that the hardness stems from the introduction of
capacities. For low doubling dimension graphs we were able to push the
existence of an EPAS further than just introducing capacities, by considering
suppliers and outliers. It therefore becomes an interesting question whether
we can show an EPAS also for low highway dimension graphs when using suppliers
and outliers, but without using capacities. The following theorem shows that
this is indeed possible.

###### Theorem 1.3

Let $\mathcal{I}=(G,k,p)$ be an instance of the $k$-Supplier with Outliers
problem. There exists an EPAS for this problem with parameters $k$, $p$,
$\varepsilon$, and highway dimension of $G$.

###  1.1 Used techniques

To prove Theorem 1.1, we enhance a result of Dom et al. [17] which shows that
Capacitated Dominating Set is $\mathrm{W[1]}$-hard in low treewidth graphs.

We prove Theorem 1.2 by using the concept of a $\delta$-net which is a sparse
subset of the input metric such that every input point has a net point near
it. In Lemma 7 we show that the size of the net, for
$\delta=\varepsilon\cdot\mathrm{OPT}$, can be bounded by parameters $k$,
number of outliers $p$, doubling dimension, and $\varepsilon$. A naive
approach, which ignores capacities of suppliers, would be to guess a $k$-size
subset of the net which is a feasible $(1+\varepsilon)$-approximate solution.
This is in fact the approach used by Feldmann and Marx [23] to show an EPAS
for $k$-Center in low doubling dimension graphs. To support the capacities, we
need further ideas regarding the structure of the solution with respect to the
net. We present these in Lemmas 8 and 9.

To prove Theorem 1.3, we generalize the EPAS for $k$-Center in low highway
dimension graphs by Becker et al. [7]. A major component of this algorithm is
an EPAS for kSwO in low treewidth graphs, cf. Theorem 4.1, which generalizes
an EPAS for $k$-Center in low treewidth graphs by Katsikarelis et al. [30].

##  2 Inapproximability in low highway dimension graphs

In this section we are going to prove Theorem 1.1, i.e. we show that there is
no parameterized approximation scheme for Capacitated $k$-Center in graphs of
low highway dimension unless $\mathrm{FPT}=\mathrm{W[1]}$.

We reduce from Multicolored Clique, which is known to be a
$\mathrm{W[1]}$-hard problem [14, Theorem 13.25]. The input of Multicolored
Clique consists of a graph $G$ and an integer $k$. The vertex set of $G$ is
partitioned into _color classes $V_{1},\ldots,V_{k}$_ where each color class
is an independent set. The goal is to find a $k$-clique. Note that endpoints
of every edge of $G$ have to be in different color classes. Hence if a
$k$-clique exists in $G$, then it has exactly one vertex in each color class.

To prove Theorem 1.1, we will need several settings of edge lengths. Namely
for every $\lambda\geq 2\gamma\geq 8$, given an instance $\mathcal{I}=(G,k)$
of Multicolored Clique, we produce in polynomial time a CkC instance
$\overline{\mathcal{I}}_{\lambda}=(\overline{G},\overline{k},L,d_{\lambda})$
where the highway dimension and treewidth of $\overline{G}$ is
$\mathcal{O}(k^{4})$ and ${\overline{k}=7k(k-1)+2k}$. If we are not interested
in a particular setting of $\lambda$ or we speak generally about all instances
for all possible settings of $\lambda$, we omit the subscript.

It follows from [14] that we can assume without loss of generality that every
color class consists of $N$ vertices and the number of edges between every two
color classes is $M$. For two integers $m\leq n$ by $\langle m,n\rangle$ we
mean the set of integers $\\{m,m+1,\ldots,n\\}$, and $\langle m\rangle=\langle
1,m\rangle$. For distinct $i,j\in\langle k\rangle$ we denote by $E_{i,j}$ the
set of ordered pairs of vertices $(u,v)$ such that $u\in V_{i}$, $v\in V_{j}$,
and $\\{u,v\\}$ is an edge in $G$. When we add an  _$(A,B)$ -arrow_ from
vertex $u$ to vertex $v$, we add $A$ subdivided edges between $u$ and $v$ and
additionally we add $B$ unique vertices to the graph and connect them to $v$,
see Fig. 1. When we _mark_ a vertex $u$, we add $\overline{k}+1$ new vertices
to the graph and connect them to $u$. We denote the set of all marked vertices
by $Z$.

Figure 1: The result of adding an $(A,B)$-arrow from $u$ to $v$.

We first describe the structure of $\overline{G}$ and we set the capacities
and edge lengths of $\overline{G}$ afterwards. See Fig. 2 for an illustration
of the reduction.

##### Color class gadget.

For each color class $V_{i}$, we create a gadget as follows. We arbitrarily
order vertices of $V_{i}$ and to the $j\textsuperscript{th}$ vertex $u\in
V_{i}$ we assign numbers $u^{\uparrow}=j\cdot 2N^{2}$ and
$u^{\downarrow}=2N^{3}-u^{\uparrow}$. For each vertex $u\in V_{i}$ we create a
vertex $\overline{u}$ and we denote $\overline{V}_{i}=\\{\overline{u}\mid u\in
V_{i}\\}$. We add a marked vertex $x_{i}$ and connect it to every vertex of
$\overline{V}_{i}$. We add a set $S_{i}$ of $\overline{k}+1$ vertices and
connect each vertex of $S_{i}$ to every vertex of $\overline{V}_{i}$. For
every $j\in\langle k\rangle\setminus\\{i\\}$ we add a pair of marked vertices
$y_{i,j}$ and $z_{i,j}$. We denote $Y_{i}=\cup_{j\in\langle
k\rangle\setminus\\{i\\}}\\{y_{i,j},z_{i,j}\\}$. For every vertex
$\overline{u}\in\overline{V}_{i}$ we add a
$(u^{\uparrow},u^{\downarrow})$-arrow from $u$ to each vertex of
$\cup_{j\in\langle k\rangle\setminus\\{i\\}}y_{i,j}$ and a
$(u^{\downarrow},u^{\uparrow})$-arrow from $u$ to each vertex of
$\cup_{j\in\langle k\rangle\setminus\\{i\\}}z_{i,j}$.

##### Edge set gadget.

For every $i\in\langle k-1\rangle,j\in\langle i+1,k\rangle$ we create a gadget
for the edge set $E_{i,j}$ as follows. For every edge $e\in E_{i,j}$ we create
a vertex $\overline{e}$ and we denote $\overline{E}_{i,j}=\\{\overline{e}\mid
e\in E_{i,j}\\}$. We add a marked vertex $x_{i,j}$ and connect it to every
vertex of $\overline{E}_{i,j}$. We add a set $S_{i,j}$ of $\overline{k}+1$
vertices and connect each vertex of $S_{i,j}$ to every vertex of
$\overline{E}_{i,j}$. We add four marked vertices
$p_{i,j},p_{j,i},q_{i,j},q_{j,i}$. Consider an edge $e=(u,v)\in E_{i,j}$, we
connect $\overline{e}$ to $p_{i,j}$ with a
$(u^{\downarrow},u^{\uparrow})$-arrow, to $q_{i,j}$ with a
$(u^{\uparrow},u^{\downarrow})$-arrow, to $p_{j,i}$ with a
$(v^{\downarrow},v^{\uparrow})$-arrow, and to $q_{j,i}$ with a
$(v^{\uparrow},v^{\downarrow})$-arrow. We denote
$\mathcal{S}=(\cup_{i\in\langle k\rangle}S_{i})\cup(\cup_{i\in\langle
k-1\rangle,j\in\langle i+1,k\rangle}S_{i,j})$.

##### Adjacency gadget.

To connect the color class gadgets and the edge set gadgets, for every
distinct $i,j\in\langle k\rangle$ we add marked vertices $r_{i,j}$ and
$s_{i,j}$, and we add $(2N^{3},0)$-arrows from $y_{i,j}$ to $r_{i,j}$, from
$p_{i,j}$ to $r_{i,j}$, from $z_{i,j}$ to $s_{i,j}$, and from $q_{i,j}$ to
$s_{i,j}$.

Figure 2: Part of the reduction for color class $V_{i}$ and edge set
$E_{i,j}$. Vertex $\overline{e}$ represents an edge ${(v,w)\in E_{i,j}}$ in
$G$. We omit the sets $S_{i}$ and $S_{i,j}$. Marked vertices are drawn by
boxes and we omit their $\overline{k}+1$ “private” neighbors. Edges drawn by a
dashed line have length $1$ and the remaining edges have length $\lambda$. We
also omit the appropriate arrows from vertices of
$\overline{V}_{i}\setminus\\{\overline{u}\\}$ to $y_{i,j}$ and to $z_{i,j}$,
and the appropriate arrows from vertices of
$\overline{E}_{i,j}\setminus\\{\overline{e}\\}$ to $p_{i,j}$ and to $q_{i,j}$.

##### Capacities.

We now describe the capacities ${L\colon V(\overline{G})\to\bbbn}$. To
streamline the exposition, we will assume that each vertex of
$\phi(V(\overline{G}))$ covers itself at no “cost” with respect to the
capacity. For every two distinct ${i,j\in\langle k\rangle}$, the vertex
$x_{i}$ has capacity ${N-1+\overline{k}+1}$, the vertex $x_{i,j}$ has capacity
${M-1+\overline{k}+1}$, vertices $y_{i,j}$ and $z_{i,j}$ have capacity
${2N^{4}+\overline{k}+1}$, vertices $p_{i,j}$ and $q_{i,j}$ have capacity
${2MN^{3}+\overline{k}+1}$, vertices $r_{i,j}$ and $s_{i,j}$ have capacity
${2N^{3}+\overline{k}+1}$, and the remaining vertices have capacity equal to
their degree.

##### Edge lengths.

Given $\lambda\in\bbbr^{+}$ we set edge lengths $d_{\lambda}\colon
E(\overline{G})\to\bbbr$ as follows. For every $i\in\langle k\rangle$ and
every vertex $\overline{u}\in\overline{V}_{i}$, we assign length $1$ to edges
between $\overline{u}$ and $N(\overline{u})\setminus(\\{x_{i}\\}\cup S_{i})$,
i.e. the set of vertices originating from subdivided edges of arrows between
$\overline{u}$ and $Y_{i}$. Similarly for every $i\in\langle
k-1\rangle,j\in\langle i+1,k\rangle$ and every vertex
$\overline{v}\in\overline{E}_{i,j}$, we assign length $1$ to edges between
$\overline{v}$ and $N(\overline{v})\setminus(\\{x_{i,j}\\}\cup S_{i,j})$. To
the remaining edges we assign length $\lambda$.

From the way we assign edge lengths $d_{\lambda}$, in a solution $\phi$ of
cost $\lambda+1$ such that
$\lvert\phi(V(\overline{G}))\rvert\leq\overline{k}$, it must be the case that
$Z\subseteq\phi(V(\overline{G}))$, since $Z$ is the set of marked vertices
with $\overline{k}+1$ private neighbors.

Dom et al. [17, Observation 1] observe that
$\mathrm{tw}(\overline{G})=\mathcal{O}(k^{4})$: The size of $\mathcal{S}$ is
$\mathcal{O}(k^{4})$ and the size of $Z$ is $\frac{1}{2}(13k^{2}-11k)$.
Removing $\mathcal{S}\cup Z$ leaves us with a forest and the observation
follows.

We prove that $\overline{G}$ has bounded highway dimension. For an interval of
reals $I$, we will consider shortest paths of $\overline{G}$ such that their
length belongs to $I$, thus we accordingly denote this set by
$\mathcal{P}_{I}$. We also denote
$\mathcal{V}=(\cup_{i=1}^{k}\overline{V_{i}})\cup(\cup_{1\leq i<j\leq
k}\overline{E}_{i,j})$.

###### Lemma 1

For any $\lambda\geq 2\gamma$, where $\gamma$ is the universal constant in
Definition 1, graph $\overline{G}$ with edge lengths $d_{\lambda}$ has highway
dimension $h(\overline{G})\in\mathcal{O}(k^{4})$.

###### Proof

Consider a scale $r\geq 2$ and any shortest path
$\pi\in\mathcal{P}_{(r,\infty)}$. Let ${H=\mathcal{S}\cup Z}$. From the way we
constructed $\overline{G}$, the maximal length of a shortest path which does
not contain an edge of length $\lambda$ is 2. Thus $\pi$ has to contain an
edge of length $\lambda$. Every edge of length $\lambda$ is adjacent to a
vertex of $H$, which means that $H$ forms a hitting set for
$\mathcal{P}_{(r,\infty)}$. We have $\lvert\mathcal{S}\cup
Z\rvert=\mathcal{O}(k^{4})$, and this trivially bounds $\lvert B_{u}(\gamma
r)\cap H\rvert=\mathcal{O}(k^{4})$ for any vertex $u\in V(\overline{G})$.

Now consider the case $r<2$. Let $H=\mathcal{S}\cup\mathcal{V}\cup Z$. We have
already seen that every edge of length $\lambda$ is incident to
$\mathcal{S}\cup Z$. Every edge of length $1$ is incident to a vertex of
$\mathcal{V}$, hence the set $H$ hits all shortest paths
$\mathcal{P}_{(r,\infty)}$. We have $\gamma r<\lambda$, as $\lambda\geq
2\gamma$. This means that if $B_{u}(\gamma r)$ contains a vertex $v$ other
than $u$, then $\mathrm{dist}(u,v)<\lambda$. From the construction of the
graph, it then must be the case that $\mathrm{dist}(u,v)=1$, and in fact
$\\{u,v\\}\in E(\overline{G})$ and $d_{\lambda}(u,v)=1$. Let $F=\\{e\in
E(\overline{G})\mid d_{\lambda}(e)=1\\}$. We have to bound the size of
$B_{u}(\gamma r)\cap H$ where $u$ is an endpoint of an edge in $F$. We will
show that the bound is $1$.

For every edge of $F$, one of its endpoints is a vertex $u\in\mathcal{V}$ and
the other is a vertex which belongs to a vertex originating from a subdivided
edge of an arrow incident to $u$. In the first case, a shortest path between
any pair of vertices of $\mathcal{V}$ has to contain two edges of length
$\lambda$. Thus the distance between them is at least $2\lambda$. Any shortest
path from a vertex of $\mathcal{V}$ to a vertex of $\mathcal{S}\cup Z$
contains an edge of length $\lambda$. Thus for a vertex $u\in\mathcal{V}$, we
have $B_{u}(\gamma r)\cap H=\\{u\\}$ as $\gamma r<\lambda$. In the second
case, a vertex $v$ belonging to a subdivided edge has degree two and exactly
one of the edges incident to it has length $1$; the other has length
$\lambda$, which is not consequential in the current case as $\gamma
r<\lambda$. The neighbor $w$ of $v$ such that $d_{\lambda}(v,w)=1$ belongs to
$\mathcal{V}$. This means that ${\lvert B_{v}(\gamma r)\cap H\rvert=1}$ since
${B_{v}(\gamma r)=\\{v,w\\}}$, i.e. we have considered all the possible cases.
∎

Now we prove that $\mathcal{I}$ contains a $k$-clique if and only if
$\overline{\mathcal{I}}_{\lambda}$ contains a solution of cost at most
$\lambda+1$. As $d_{\lambda}$ assigns edge lengths 1 and $\lambda$, this will
imply that if $\mathcal{I}$ does not contain a $k$-clique, then any solution
of $\overline{\mathcal{I}}$ has to have cost at least $\lambda+2$ and vice
versa.

The forward implication follows implicitly from the original result of Dom et
al. [17], since we can interpret a capacitated dominating set as a solution of
cost $\lambda$, hence we omit the proof.

######  Lemma 2 ([17, Lemma 1])

If $\mathcal{I}$ contains a $k$-clique, then
$\overline{\mathcal{I}}_{\lambda}$ contains a solution of cost $\lambda$.

To prove the backward implication, we start need to show that a solution of
cost $\lambda+1$ has to open a vertex in every $\overline{V}_{i}$ and every
$\overline{E}_{i,j}$. In contrast to Lemma 2, the backward implication does
not simply follow from the original result since we have added edge lengths to
the graph.

###### Lemma 3

Let $\phi$ be a solution of $\overline{\mathcal{I}}_{\lambda}$ of cost
$\lambda+1$, and $D=\phi(V(\overline{G}))$. Then for each $i\in\langle
k\rangle$ we have $\lvert\overline{V}_{i}\cap D\rvert=1$ and for each
$i\in\langle k-1\rangle,j\in\langle i+1,k\rangle$ we have and
$\lvert\overline{E}_{i,j}\cap D\rvert=1$.

###### Proof

We prove this statement by contradiction. Suppose that there exists $i$ such
that $\lvert\overline{V}_{i}\cap D\rvert\neq 1$. We first consider the case
when $\lvert\overline{V}_{i}\cap D\rvert=0$. Vertices of $S_{i}$ have to be
covered by vertices at distance at most $\lambda+1$ from them excluding those
belonging to $\overline{V}_{i}$. Let $W$ be the set of vertices originating
from subdivided edges of arrows between $\overline{V}_{i}$ and $Y_{i}$. Then
it must be the case that $\phi^{-1}(S_{i})\subseteq S_{i}\cup W$ as
$(\cup_{u\in S_{i}}B_{u}(\lambda+1))\setminus\overline{V_{i}}=S_{i}\cup W$.
The distance between a pair of vertices of $S_{i}$ is $2\lambda$, which is
strictly greater than $\lambda+1$ since $\lambda\geq 2\gamma\geq 8$. Hence for
a vertex $u\in(D\cap S_{i})$ we have $\lvert\phi^{-1}(u)\cap S_{i}\rvert\leq
1$. For a vertex $w\in W$ we have $L(w)=2$, and so $\lvert\phi^{-1}(w)\cap
S_{i}\rvert\leq 2$. In total, we would have to pick at least
$\frac{\overline{k}+1}{2}$ vertices of $S_{i}\cup W$ to cover $S_{i}$. We have
$\lvert Z\rvert>\overline{k}-\frac{\overline{k}+1}{2}$ and $D$ must contain
$Z$. As $Z\cap(S_{i}\cup W)=\emptyset$, this contradicts the fact that $\lvert
D\rvert\leq\overline{k}$ and thus $\lvert\overline{V}_{i}\cap D\rvert\geq 1$.

In the case that there exist $i$ and $j$ such that
$\lvert\overline{E}_{i,j}\cap D\rvert=0$, we can apply a similar argument to
show that $\lvert\overline{E}_{i,j}\cap D\rvert\geq 1$

We have shown that every $\overline{V}_{i}$ and every $\overline{E}_{i,j}$
contains at least one vertex of $D$. By calculating $\overline{k}-\lvert
Z\rvert=k+\binom{k}{2}$, which is equal to the number of color classes plus
the number of edge sets, it follows that each of them must contain exactly $1$
vertex of $D$ as $Z\subset D$. ∎

Now we show that if $\overline{\mathcal{I}}_{\lambda}$ contains a solution of
cost $\lambda+1$, then $\mathcal{I}$ contains a $k$-clique.

###### Lemma 4

If $\overline{\mathcal{I}}_{\lambda}$ has a solution $\phi$ of cost
$\lambda+1$, then $\mathcal{I}$ contains a $k$-clique.

###### Proof

Let $D=\phi(V(\overline{G}))$. For $i\in\langle k\rangle$ let
$\overline{u}_{i}$ be the vertex of $\overline{V}_{i}\cap D$ and for
${i\in\langle k-1\rangle},j\in\langle i+1,k\rangle$ let $\overline{e}_{i,j}$
be the vertex of $\overline{E}_{i,j}\cap D$. These vertices are well-defined
by Lemma 3. To prove that these vertices encode a $k$-clique in $G$, we want
to show for every $i\in\langle k-1\rangle,j\in\langle i+1,k\rangle$ that
vertices $u_{i}$ and $u_{j}$, which correspond to $\overline{u}_{i}$ and
$\overline{u}_{j}$ respectively, are incident to the edge $e_{i,j}$
corresponding to the vertex $\overline{e}_{i,j}$. We will only present the
proof of incidence for $u_{i}$ and $e_{i,j}$, for $u_{j}$ we can proceed
analogously. Let $v$ be the vertex of the edge $e_{i,j}$ which belongs to
$V_{i}$ in $G$. Before we prove that $u_{i}$ and $e_{i,j}$ are incident, we
first argue that $u_{i}^{\uparrow}+v^{\downarrow}=2N^{3}$.

We prove this statement by contradiction. First suppose
$u_{i}^{\uparrow}+v^{\downarrow}<2N^{3}$. Then
$u_{i}^{\uparrow}+v^{\downarrow}\leq 2N^{3}-2N^{2}$ as for every two distinct
vertices $w_{1}$ and $w_{2}$ of a color class we have $\lvert
w_{1}^{\uparrow}-w_{2}^{\uparrow}\rvert\geq 2N^{2}$ and $\lvert
w_{1}^{\downarrow}-w_{2}^{\downarrow}\rvert\geq 2N^{2}$. Consider the set

$\mathcal{T}=(N(y_{i,j})\cup N(r_{i,j})\cup
N(p_{i,j}))\setminus\phi^{-1}(\\{x_{i},u_{i},e_{i,j},x_{i,j}\\}).$ (1)

It follows that in a solution of cost $\lambda+1$, vertices of $\mathcal{T}$
must be covered by $y_{i,j}$, $r_{i,j}$ or $p_{i,j}$ as edges of
$\overline{G}$ have length $1$ or $\lambda$. We have
$L(y_{i,j})+L(r_{i,j})+L(p_{i,j})=2N^{4}+2MN^{3}+2N^{3}+3(\overline{k}+1)$.
However,

$\displaystyle\lvert\mathcal{T}\rvert$ $\displaystyle\geq
2N^{4}+2MN^{3}+4N^{3}+3(\overline{k}+1)-((2N^{3}-2N^{2})+(N-1)+(M-1))$
$\displaystyle>2N^{4}+2MN^{3}+2N^{3}+3(\overline{k}+1),$ (2)

where we used that $M\leq N^{2}$ and $N^{2}>N$. Thus $y_{i,j}$, $r_{i,j}$, and
$p_{i,j}$ cannot cover $\mathcal{T}$. This contradicts the fact that $\phi$ is
a solution of cost $\lambda+1$.

If $u_{i}^{\uparrow}+v^{\downarrow}>2N^{3}$, then
$u_{i}^{\downarrow}+v^{\uparrow}<2N^{3}$ and we can apply the identical
argument for vertices $z_{i,j},s_{i,j},q_{i,j}$.

It remains to prove that $u_{i}$ is incident to $e_{i,j}$. Again, let $v$ be
the vertex of $e_{i,j}$ which lies in $V_{i}$ of $G$. We know from the
preceding argument that $u_{i}^{\uparrow}+v^{\downarrow}=2N^{3}$. However, the
only vertex $w\in V_{i}$ such that $w^{\downarrow}=2N^{3}-u_{i}^{\uparrow}$ is
$u_{i}$ itself; for any $w\in V_{i}\setminus\\{u_{i}\\}$ we would have
$\lvert(u_{i}^{\uparrow}+w^{\downarrow})-2N^{3}\rvert\geq 2N^{2}$. Hence
$v=u_{i}$ and so $e_{i,j}$ is incident to $u_{i}$. This concludes the proof. ∎

We are ready to prove Theorem 1.1.

######  Proof (of Theorem 1.1)

Let $\gamma\geq 4$ be the universal constant in Definition 1, and
$\lambda=2\gamma$. For contradiction, suppose that there exists an algorithm
$\mathcal{A}$ with an approximation ratio
$c=\left((1+\frac{1}{\gamma})-\varepsilon\right)$ for some fixed
$\varepsilon>0$ parameterized by $k$, treewidth and highway dimension.

Given a Multicolored Clique instance $\mathcal{I}=(G,k)$, we produce a CkC
instance $\overline{\mathcal{I}}_{\lambda}=(\overline{G},\overline{k},L)$ with
edge lengths $d_{\lambda}$ using the reduction from Section 2. We run
algorithm $\mathcal{A}$ on the instance $\mathcal{\overline{I}}$, which takes
time
$\mathcal{O}^{*}(f(\overline{k},\mathrm{tw}(\overline{G}),h(\overline{G})))$
for some computable function $f$. We have $\overline{k}=7k(k-1)+2k$. By the
observation of Dom et al. [17], graph $\overline{G}$ has treewidth
$\mathcal{O}(k^{4})$. By Lemma 1, graph $\overline{G}$ has highway dimension
$\mathcal{O}(k^{4})$. Thus there exists a computable function $g$ such that
$f(\overline{k},\mathrm{tw}(\overline{G}),h(\overline{G}))\leq g(k)$. If
$\mathcal{I}$ is a YES-instance, then $\mathcal{\overline{I}}$ has a solution
of cost $\lambda$ by Lemma 2. On the other hand, if $\mathcal{I}$ is a NO-
instance, then any solution of $\mathcal{\overline{I}}$ has to have cost at
least $\lambda+2$, which follows from Lemma 4. Algorithm $\mathcal{A}$ is able
to distinguish between these two cases in time
$\mathcal{O}^{*}(f(\overline{k},\mathrm{tw}(\overline{G}),h(\overline{G})))=\mathcal{O}^{*}(g(k))$,
since $c<\frac{\lambda+2}{\lambda}$. This is an $\mathrm{FPT}$ algorithm for a
$\mathrm{W[1]}$-hard problem, which contradicts
$\mathrm{FPT}\neq\mathrm{W[1]}$. ∎

##  3 EPAS on graphs of bounded doubling dimension

In this section we prove Theorem 1.2, i.e. we show the existence of an EPAS
for CkSwO on instances where the supplier set has bounded doubling dimension.
To be more precise, we develop a decision algorithm which, given a cost
$\varrho\in\bbbr^{+}$, and $\varepsilon>0$, computes a solution of cost
$(1+\varepsilon)\varrho$ in $\mathrm{FPT}$ time with parameters $k$, $p$,
doubling dimension and $\varepsilon$. Formally, the result is the following
lemma.

###### Lemma 5

Let $\mathcal{I}=(G,k,p,L)$ be a CkSwO instance. Moreover, let
$(V_{S},\mathrm{dist})$ be the shortest-path metric induced by $V_{S}$ and
$\Delta$ be its doubling dimension. There exists an algorithm which, given a
cost $\varrho\in\bbbr^{+}$ and $\varepsilon>0$, either

  * •

computes a feasible solution of cost $(1+\varepsilon)\varrho$ if
$(1+\varepsilon)\varrho\geq\mathrm{OPT}(\mathcal{I})$, or

  * •

correctly decides that $\mathcal{I}$ has no solution of cost at most
$\varrho$,

running in time
$\mathcal{O}^{*}\left((k+p)^{k}\varepsilon^{-\mathcal{O}(k\Delta)}\right)$.

Using Lemma 5, we can obtain the algorithm of Theorem 1.2 as follows. We can
first assume without loss of generality, that $V_{C}\cup V_{S}=V(G)$. Suppose
that we can guess the optimum cost $\mathrm{OPT}$ of any CkSwO instance. By
using $\mathrm{OPT}$ as $\varrho$ in Lemma 5, we can output a solution of cost
$(1+\varepsilon)\mathrm{OPT}$. To guess the optimum cost $\mathrm{OPT}$,
observe that $\mathrm{OPT}$ must be one of the inter-vertex distances. Hence
the minimum inter-vertex distance $\varrho$ for which the algorithm outputs a
solution has the property that $\varrho\leq\mathrm{OPT}$ and consequently
$(1+\varepsilon)\varrho\leq(1+\varepsilon)\mathrm{OPT}$.

The main ingredient of the algorithm is the notion of a $\delta$-net. For a
metric $(X,\mathrm{dist})$, a subset $Y\subseteq X$ is called a _$\delta$
-cover_ if for every $u\in X$ there exists a $v\in Y$ such that
$\mathrm{dist}(u,v)\leq\delta$. If a $\delta$-cover $Y$ has an additional
property that for every two distinct $u,v\in Y$ we have
$\mathrm{dist}(u,v)>\delta$, then we say that $Y$ is a _$\delta$ -net_.
Observe that a $\delta$-net can be computed greedily in polynomial time.

Let us give the main idea behind the algorithm. Given an instance of the
problem and $\varepsilon>0$, let $\phi^{*}$ be an optimum solution of cost
$\mathrm{OPT}$, $V_{C}^{*}$ be clients that are not outliers according to
$\phi^{*}$, i.e. $V_{C}^{*}=\\{u\in V_{C}\mid\phi^{*}(u)\neq\bot\\}$, and $Y$
be an $(\varepsilon\cdot\mathrm{OPT})$-net of the metric
$(V_{S},\mathrm{dist})$. Consider an assignment function $\phi$ constructed as
follows. For each client $u\in V_{C}^{*}$ we set $\phi(u)$ to the nearest
point of $Y$ to $\phi^{*}(u)$, and for the remaining clients we set the value
of $\phi$ to $\bot$. If for every selected supplier
$s\in(\phi(V_{C})\setminus\\{\bot\\})$ we have $\lvert\phi^{-1}(s)\rvert\leq
L(s)$, then $\phi$ is a feasible solution. Since $Y$ is an
$(\varepsilon\cdot\mathrm{OPT})$-net, the cost of $\phi$ is at most
$(1+\varepsilon)\mathrm{OPT}$.

The main obstacle to implementing an algorithm from this idea is that we do
not know the optimum solution $\phi^{*}$. However, by the definition of the
net $Y$, we know that each selected supplier $\phi^{*}(V_{C}^{*})$ is near
some point of $Y$. If $Y$ was not too large, we could guess which $k$ of its
points are near to every supplier of $\phi^{*}(V_{C}^{*})$. Later, we will
also show how to ensure that the solution we create respects capacities of
suppliers we pick.

We now show how to bound the size of the net. Let $(X,\mathrm{dist})$ be a
metric of doubling dimension $\Delta$, by the _aspect ratio_ of a set
$X^{\prime}\subseteq X$, we mean the diameter of $X^{\prime}$ divided by the
minimum distance between any two distinct points of $X^{\prime}$, that is
$\frac{\max_{u,v\in X^{\prime}}\mathrm{dist}(u,v)}{\min_{u,v\in
X^{\prime},u\neq v}\mathrm{dist}(u,v)}.$ The following lemma by Gupta et al.
[26] shows that the cardinality of a subset $X^{\prime}\subseteq X$ can be
bounded by its aspect ratio and $\Delta$.

######  Lemma 6 ([26])

Let $(X,\mathrm{dist})$ be a metric and $\Delta$ its doubling dimension.
Consider a subset ${X^{\prime}\subseteq X}$ of aspect ratio $\alpha$ and
doubling dimension $\Delta^{\prime}$. Then it holds that
$\Delta^{\prime}=\mathcal{O}(\Delta)$ and $\lvert X^{\prime}\rvert\leq
2^{\mathcal{O}(\Delta\lceil\log_{2}\alpha\rceil)}$.

Using Lemma 6, we bound the size of $Y$.

###### Lemma 7

Let $\mathcal{I}=(G,k,p,L)$ be an instance of the CkSwO problem,
${\varepsilon>0}$, and ${\varrho\in\bbbr^{+}}$ a cost. Moreover let
$(V_{S},\mathrm{dist})$ be the shortest-path metric induced by $V_{S}$ and
$\Delta$ its doubling dimension. Assume that for each supplier $s\in V_{S}$
there exists a client $c\in V_{C}$ such that $\mathrm{dist}(s,c)\leq\varrho$.
If $\mathcal{I}$ has a feasible solution $\phi$ with
$\operatorname{cost}(\phi)\leq\varrho$, then an $(\varepsilon\varrho)$-net $Y$
of $V_{S}$ has size at most $(k+p)\varepsilon^{-\mathcal{O}(\Delta)}$.

Before we prove the lemma, let us make a few comments the statement of the
lemma. We do not know the cost of the optimum solution and we are merely
guessing it. Hence we need to also consider the case when our guess on the
cost $\varrho$ is wrong, i.e. it is less than the cost of the optimum
solution. The requirement that every supplier has a client nearby is a natural
one: if we assume that our solution has cost $\varrho$ and a supplier $s$ has
$\mathrm{dist}(s,V_{C})>\varrho$, then it will never be picked in a solution.
Thus we can without loss of generality remove all such suppliers from the
input.

######  Proof (of Lemma 7)

Let $V_{C}^{\prime}=\\{u\in V_{C}\mid\phi(u)\neq\bot\\}$ and
$V_{S}^{\prime}=\phi(V_{C}^{\prime})$. Since $\phi$ is a solution of cost
$\varrho$, all clients of $V_{C}^{\prime}$ can be covered by balls of radius
$\varrho$ around vertices of $V_{S}^{\prime}$ and there are $k$ such balls. To
cover the outliers $V_{C}\setminus V_{C}^{\prime}$, we use the fact that there
are at most $p$ of them. Thus we place a ball of radius $\varrho$ centered at
each outlier. Since every supplier is at distance at most $\varrho$ from some
client and every client lies in one of the balls of radius $\varrho$ we have
placed, by increasing the radius of every placed ball to $2\varrho$ we cover
all suppliers as well.

In total, $V_{C}\cup V_{S}$ can be covered by $k+p$ balls of diameter at most
$4\varrho$. For each such ball, let us consider the aspect ratio of points of
the net $Y$ which lie in it. Since the diameter is at most $4\varrho$ and the
distance of every two points of a net is more than $\varepsilon\varrho$, the
aspect ratio is at most $\frac{4}{\varepsilon}$. By Lemma 6 each of the balls
contains at most $\varepsilon^{-\mathcal{O}(\Delta)}$ points of $Y$. Thus
$\lvert Y\rvert\leq(k+p)\varepsilon^{-\mathcal{O}(\Delta)}$. ∎

When we gave the intuition behind the algorithm, we assumed that the derived
solution $\phi$, which replaces every optimum supplier of
$\phi^{*}(V_{C})\setminus\\{\bot\\}$ by its nearest net point, does not
violate the capacity of any selected net point, i.e. for every
$s\in\phi(V_{C})\setminus\\{\bot\\}$ we have $\lvert\phi^{-1}(s)\rvert\leq
L(s)$. This does not have to be the case, so instead of replacing every
optimum supplier by its nearest net point, we need to select the replacement
net point in a more sophisticated manner, in particular to avoid violating the
capacity of the replacement net point.

Let $V_{S}^{*}$ be the optimum supplier set corresponding to the optimum
assignment function $\phi^{*}$. Suppose that we are able to guess a subset
$S^{*}\subseteq Y$ of size $k$ such that for every supplier $u\in V_{S}^{*}$
we have $\mathrm{dist}(u,S^{*})\leq\varepsilon\varrho$. Let $A\colon
V_{S}^{*}\to S^{*}$ map each optimum supplier to its nearest net point. As we
have discussed, we cannot just replace each supplier $u\in V_{S}^{*}$ by
$A(u)$ since it may happen that ${\lvert(\phi^{*})^{-1}(u)\rvert>L(A(u))}$.
However, there is a supplier in the ball $B_{A(u)}(\varepsilon\varrho)$ which
is guaranteed to have capacity at least $L(u)$ since $u\in
B_{A(u)}(\varepsilon\varrho)$ Thus we can implement the “replacement step” by
replacing each optimum supplier by the supplier of highest capacity in
$B_{A(u)}(\varepsilon\varrho)$ and this increases the cost of the optimum
solution by at most $2\varepsilon\varrho$, i.e. the diameter of the ball.

We must also consider the case when $\lvert A^{-1}(v)\rvert>1$ for some net
point $v\in S^{*}$. Generalizing the previous idea, we replace suppliers
$A^{-1}(v)$ by $\lvert A^{-1}(v)\rvert$ suppliers of
$B_{v}(\varepsilon\varrho)$ with the highest capacities. As we do not know the
optimum solution, we do not know $\lvert A^{-1}(v)\rvert$ either.
Nevertheless, we know that $\lvert S^{*}\rvert\leq k$, and so we can afford to
guess these values after guessing the set $S^{*}$.

The final ingredient we need is the ability to verify our guesses. That is,
given a set of at most $k$ suppliers, we need to check if there exists a
feasible solution of a given cost which assigns clients to a prescribed set of
suppliers. We do so by a standard reduction to network flows.

###### Lemma 8

Given a CkSwO instance $\mathcal{I}=(G,k,p,L)$, a cost $\varrho\in\bbbr^{+}$,
and a subset $S\subseteq V_{S}$, we can determine in polynomial time whether
there exists an assignment $\phi\colon V_{C}\to S$ such that
$\lvert\phi(u)^{-1}\rvert\leq L(u)$ for each $u\in S$,
$\lvert\phi^{-1}(\bot)\rvert\leq p$, and
$\operatorname{cost}(\phi)\leq\varrho$.

###### Proof

We build a network $N=(G^{\prime}=(V^{\prime},E^{\prime}),a,b,c)$ where $a\in
V^{\prime}$ is the source, $b\in V^{\prime}$ is the sink, and
$c:E^{\prime}\to\bbbr^{+}_{0}$ assigns capacities to edges of the directed
graph $G^{\prime}=(V^{\prime},E^{\prime})$. Refer to Fig. 3 for an example of
such a network. For each vertex of $S\cup V_{C}$ we are going to create a
unique vertex in $V^{\prime}$, we denote this bijection by $m$. For a subset
$U\subseteq S\cup V_{C}$ we denote $m(U)=\\{m(u)\mid u\in U\\}$. For each
client $u\in V_{C}$ we add a vertex $v_{u}$ to $V^{\prime}$, assign
$m(u)=v_{u}$, and add an edge from $a$ to $v_{u}$ with capacity $1$. For each
supplier $s\in S$ we add a vertex $v_{s}$ to $V^{\prime}$ and assign
$m(s)=v_{s}$. We add edges from each vertex of $\\{m(u)\mid u\in V_{C}\cap
B_{s}(\varrho)\\}$ to $v_{s}$ with capacity $1$. We add an edge from $v_{s}$
to $b$ with capacity $L(s)$. Finally we add a vertex $o$ and add edges from
each $m(V_{C})$ to $o$ with capacity $1$ and an edge from $o$ to $b$ with
capacity $p$.

We claim that the desired assignment $\phi:V_{C}^{\prime}\to S$ exists if and
only if the maximum flow of $N$ is $\lvert V_{C}\rvert$.

To prove the forward implication, let $\phi$ be a feasible solution of the
instance $\mathcal{I}$. For each client $u$ such that $\phi(u)\neq\bot$, we
send a unit flow on the path $(a,m(u),m(\phi(u)),b)$. As $\phi$ is a feasible
solution, for each $s\in V_{S}$ there are at most $L(s)$ units flowing through
the edge $(m(s),b)$. For each outlier $v\in\phi^{-1}(\bot)$ we send a unit of
flow on the path $(a,m(v),o,b)$. The solution $\phi$ creates at most $p$
outliers, thus the flow through the edge $(o,b)$ is at most $p$, which does
not exceed the capacity of the edge $(o,b)$. There is one unit of flow going
through each client, hence the flow has value $\lvert V_{C}\rvert$. All edges
leaving the source $a$ are saturated and there are no incoming edges to $a$
hence this flow is also maximum.

To prove the backward implication, let the maximum flow of the network $N$ be
$\lvert V_{C}\rvert$ and let $f$ be the corresponding flow. Assume that $f$
assigns an integral flow to each edge, this is without loss of generality
since we can compute such a flow using the Edmonds–Karp [18] algorithm, and it
is a well known fact that if the capacities are integral, then the flow
through each edge will be integral as well. To simplify the exposition, let
$E^{\prime}=E^{\prime}\setminus\\{e\in E^{\prime}\mid f(e)=0\\}$, that is we
remove all edges through which there is no flow. From the construction of
network $N$ and the preceding assumptions, each vertex of $m(V_{C})$ has one
outgoing edge and this edge has its other endpoint in $m(S)\cup\\{o\\}$. We
construct a feasible solution $\phi$ to the instance $\mathcal{I}$ as follows.
If the outgoing edge from $m(u)$ of a client $u\in V_{C}$ ends in $o$, then we
set $\phi(u)=\bot$. Otherwise the outgoing edge from $m(u)$ ends in $m(s)$ of
some supplier $s\in V_{S}$, then we set $\phi(u)=s$. Since the capacity of the
edge $(o,b)$ is $p$ there can be at most $p$ outliers in our solution $\phi$.
From the construction of the network, the distance between a client and its
assigned supplier is at most $\varrho$. Finally, the capacity of the edge
$(m(s),b)$ for a supplier $s\in S$ is set to $L(s)$, hence there cannot be
more than $L(s)$ clients assigned to $s$.

Clearly, the construction of the network $N$ can be done in polynomial time.
The aforementioned Edmonds–Karp algorithm [18] has a polynomial running time.
Note that we have also described how to compute a feasible solution to
$\mathcal{I}$ of cost $\varrho$ such that $S$ is the set of opened suppliers
from a maximal flow in $N$. ∎

Figure 3: On the left, we have a CkSwO instance with one allowed outlier.
Vertices $s_{1}$, $s_{2}$, and $s_{3}$ are suppliers and circles centered at
them have radius $\varrho$. The remaining vertices are clients. The capacities
are $L(s_{1})=1$, $L(s_{2})=2$, $L(s_{3})=2$. On the right, we have the result
of applying Lemma 8 on the instance in the left figure. Edges with unspecified
capacity have capacity $1$.

We now prove the correctness of the replacement strategy.

###### Lemma 9

Let $\mathcal{I}=(G,k,p,L)$ be a CkSwO instance such that there exists a
solution $\phi^{*}$ of cost $\varrho$ and for each supplier there exists a
client at distance at most $\varrho$ from it. Given an
$(\varepsilon\varrho)$-net $Y$ of the shortest-path metric induced by $V_{S}$,
and $\varepsilon>0$, we can compute a solution of cost
$(1+2\varepsilon)\varrho$ in time $\mathcal{O}^{*}\left(\binom{\lvert
Y\rvert}{k}k^{k}\right)$.

###### Proof

Let $V_{S}^{*}=\phi^{*}(V_{C})\setminus\\{\bot\\}$. For an optimum supplier
$u\in V_{S}^{*}$ it may happen that $\lvert B_{u}(\varepsilon\varrho)\cap
Y\rvert>1$, i.e. it is close to more than one net point. This may cause issues
when we guess for each net point $v\in Y$ the size of
$B_{v}(\varepsilon\varrho)\cap V_{S}^{*}$. To circumvent this problem, we fix
a linear order $\preceq$ on the set of net points $Y$ and we assign each
optimum supplier to the first close net point. Formally, we define for a net
point $v\in Y$

  * •

$P(v)=\\{v^{\prime}\in Y\mid v^{\prime}\prec v\\}$ (note that $v\not\in
P(v)$),

  * •

$M(v)=B_{v}(\varepsilon\varrho)\setminus(\cup_{v^{\prime}\in
P(v)}B_{v^{\prime}}(\varepsilon\varrho))$,

  * •

$D(v)=\lvert M(v)\cap V_{S}^{*}\rvert$, and

  * •

$R(v)$ to be the set of $D(v)$ suppliers in $M(v)$ with the highest
capacities.

For a net point $v\in Y$, it is easy to see that $\sum_{s\in
R(v)}L(s)\geq\sum_{t\in M(v)\cap V_{S}^{*}}L(t)$. The sets $\\{R(v)\mid v\in
Y\\}$ are disjoint by the way we defined $M(v)$.

We guess a subset $Y^{\prime}\subseteq Y$ of size $k$ such that
$V_{S}^{*}\subseteq\bigcup_{v\in Y^{\prime}}B_{v}(\varepsilon\varrho)$. For
each $v\in Y^{\prime}$ we guess $D(v)$ and select $S=\bigcup_{v\in
Y^{\prime}}R(v)$. We apply the algorithm from Lemma 8 with the set $S$ and
cost $(1+2\varepsilon)\varrho$. If this check passes, then the solution we
obtain is in fact a solution of cost $(1+2\varepsilon)\varrho$ since we
replaced each optimum supplier by a supplier at distance at most
$2\varepsilon\varrho$ from it. Conversely, if none of our guesses pass this
check, then the instance $\mathcal{I}$ has no solution of cost $\varrho$.

The running time of our algorithm is dominated by the time required to guess
$Y^{\prime}$ and the cardinalities $D(v)$ for each $v\in Y^{\prime}$. From
$\lvert Y^{\prime}\rvert\leq k$, the time required to guess the $Y^{\prime}$
is $\mathcal{O}\left(\binom{\lvert Y\rvert}{k}\right)$. Since $D(v)\leq k$ for
every $v\in Y$, the time required to guess $D(v)$ for each $v\in Y^{\prime}$
is $\mathcal{O}(k^{k})$. In total, the running time of the algorithm is
$\mathcal{O}^{*}\left(\binom{\lvert Y\rvert}{k}k^{k}\right)$. ∎

We are ready to prove Lemma 5.

######  Proof (of Lemma 5)

To satisfy the requirements of Lemma 7 and Lemma 9, we remove all suppliers
which do not have a client at distance $\varrho$ from them. The algorithm then
computes a $(\varepsilon\varrho)$-net $Y$ of the metric
$(V_{S},\mathrm{dist})$. By Lemma 7, if the net $Y$ has more than
$(k+p)\varepsilon^{-\mathcal{O}(\Delta)}$ points, then the algorithm concludes
that the instance has no solution of cost $\varrho$. To compute a solution of
cost $(1+2\varepsilon)\varrho$ or to show that there exists no solution of
cost $\varrho$, we apply the algorithm given by Lemma 9. Since the net $Y$ has
size at most $(k+p)\varepsilon^{-\mathcal{O}(\Delta)}$, the running time of
the algorithm is
$\mathcal{O}^{*}\left((k+p)^{k}\varepsilon^{-\mathcal{O}(k\Delta)}\right)$. ∎

##  4 EPAS for kSwO in Low Highway Dimension Graphs

In this section we prove Theorem 1.3, i.e. we show an EPAS for $k$-Supplier
with Outliers in low highway dimension graphs. We assume without loss of
generality that edge lengths are integral. In our algorithm, we will require
the constant $\gamma$ in Definition 1 to be strictly greater than $4$.

In contrast to CkSwO, we can simply specify the solution of kSwO for a given
cost $\varrho$ by a subset of suppliers $S\subseteq V_{S}$. Then a client $c$
can be assigned to any supplier $s$ such that $\mathrm{dist}(c,s)\leq\varrho$;
if such a supplier does not exist, then $c$ is an outlier. For such a solution
$S$, we denote the set of outliers by $S^{\bot}$.

Let us first give an overview of our algorithm. We use a framework by Becker
et al. [7] for embedding low highway dimension graphs into low treewidth
graphs. An _embedding_ of an (undirected) _guest graph_ $G$ into a _host
graph_ $H$ is a distance-preserving injective mapping $\psi\colon V(G)\to
V(H)$. For the purpose of this overview, suppose that for every two vertices
$u,v\in V(G)$ we have
$\mathrm{dist}_{G}(u,v)\leq\mathrm{dist}_{H}(\psi(u),\psi(v))\leq
c\cdot\mathrm{dist}_{G}(u,v)$ for some constant $c\in\bbbr^{+}$. Ideally, we
would like to solve the problem optimally in the host graph and then translate
the solution in the host graph back into the input guest graph. The resulting
solution in the guest graph would be a $c$-approximate solution of the input
instance.

Our situation is complicated by the fact that optimally solving $k$-Center,
which is a special case of kSwO, is already $\mathrm{W[1]}$-hard in low
treewidth graphs, as was shown by Katsikarelis et al. [30]. On the bright
side, the authors of the same paper show that it is possible to design an EPAS
for $k$-Center in low treewidth graphs. We generalize their algorithm to kSwO.
The following theorem summarizes the properties of the algorithm we obtain.

###### Theorem 4.1

Let ${\mathcal{I}=(G,k,p)}$ be a kSwO instance, $\varrho\in\bbbn$ a cost, and
${\varepsilon>0}$. Suppose that we receive a nice tree decomposition555See
Section 5 for a formal definition. of $G$ of width $\mathrm{tw}(G)$ on input.
There exists an algorithm which either

  * •

returns a solution of cost $(1+\varepsilon)\varrho$ if
$(1+\varepsilon)\varrho\geq\mathrm{OPT}(\mathcal{I})$, or

  * •

correctly decides that $\mathcal{I}$ does not have a feasible solution of cost
$\varrho$,

running in time
$\mathcal{O}^{*}\left((\mathrm{tw}(G)/\varepsilon)^{\mathcal{O}(\mathrm{tw}(G))}\right)$.

To ease the presentation, we defer the full proof of Theorem 4.1 to Section 5,
however, let us at least give the idea behind the algorithm. We use the
standard approach of dynamic programming on nice tree decompositions. We use a
technique of Lampis [31] for designing approximation schemes for problems hard
in low treewidth graphs. The idea behind his technique is that if the cause of
the hardness of a problem is due to the necessity of storing large numbers in
the dynamic programming table, which in our case are integers from 0 to
$\varrho$, then instead of storing exact values we store powers of
$(1+\delta)$ for an appropriately selected $\delta$. This decreases the size
of the dynamic programming table from $\varrho^{\mathrm{tw}}$ to roughly
$(\log\varrho)^{\mathcal{O}(\mathrm{tw})}$, which is sufficient for us. This
approach is not cost-free though, since storing rounded approximate values may
create errors which can accumulate during the execution of the algorithm. We
will show how to bound this error in the height of the given tree
decomposition. Together with a result of Chatterjee et al. [12], which
rebalances a given tree decomposition into a nice tree decomposition with a
logarithmic height and while only increasing the width by a constant factor,
we will obtain an EPAS parameterized by treewidth of the input graph.

The main result by Becker et al. [7] that we use is the following theorem.
Note that this result requires that the universal constant $\gamma$ in
Definition 1 is strictly greater than $\gamma$.

######  Theorem 4.2 ([7, Theorem 4])

There is a function $f(\cdot,\cdot,\cdot)$ such that, for every
$\varepsilon>0$, graph $G$ of highway dimension $h$, and set of vertices
$U\subseteq V(G)$, there exists a graph $H$ and an embedding $\psi\colon
V(G)\to V(H)$ such that

  * •

$H$ has treewidth at most $f(h,\lvert U\rvert,\varepsilon)$ and

  * •

for all vertices $u,v\in V(G)$

$\begin{split}\mathrm{dist}_{G}(u,v)&\leq\mathrm{dist}_{H}(\psi(u),\psi(v))\\\
&\leq(1+\mathcal{O}(\varepsilon))\mathrm{dist}_{G}(u,v)+\varepsilon\cdot\min\\{\mathrm{dist}_{G}(u,U),\mathrm{dist}_{G}(v,U)\\}.\end{split}$
(3)

Our algorithm starts by computing a constant factor approximation solution $S$
to the input instance, we can compute such solution using the result of Cygan
and Kociumaka [16]. We select $S\cup S^{\bot}$ as the set $U$ in Theorem 4.2.
Since $S$ is a feasible solution, we have $\lvert U\rvert\leq k+p$. We apply
the algorithm of Theorem 4.2 on graph $G$ to obtain a host graph $H$ with an
embedding $\psi\colon V(G)\to V(H)$. For a subset of suppliers $S\subseteq
V_{S}$ let $\operatorname{cost}_{G}(S)$ be the cost $S$ in graph $G$ with its
edge lengths.

Let $\mathrm{OPT}_{G}$ and $\mathrm{OPT}_{H}$ be the optimum cost of the
instance $G$ and $H$ respectively. We apply the algorithm of Theorem 4.1 on
graph $H$ with values $\varrho$ and $\varepsilon$ to obtain a solution $S$
such that $\operatorname{cost}_{H}(S)\leq(1+\varepsilon)\varrho$. As $\psi$ is
an injective function, it is correct to refer to $S$ as a solution in $G$. Our
goal is to bound the cost of the obtained solution in the input graph $G$,
which we do in the following lemma.

###### Lemma 10

Let $S$ be a $(1+\varepsilon)$-approximate solution in the host graph $H$,
i.e. ${\operatorname{cost}_{H}(S)\leq(1+\varepsilon)\mathrm{OPT}_{H}}$. Then
$\operatorname{cost}_{G}(S)\leq(1+\mathcal{O}(\varepsilon))\mathrm{OPT}_{G}$.

###### Proof

Let $S^{*}$ be a solution of $G$ of cost $\mathrm{OPT}_{G}$ and
$V_{C}^{*}=(V_{C}\setminus(S^{*})^{\bot})$. For a client $u\in V_{C}^{*}$ we
denote by $S^{*}(u)$ the nearest supplier of $S^{*}$ to $u$. By definition of
kSwO we have $\operatorname{cost}_{H}(S^{*})=\max_{u\in
V_{C}^{*}}\mathrm{dist}_{H}(u,S)$. From (3) we get

$\operatorname{cost}_{H}(S^{*})\leq\\\ \max_{u\in
V_{C}^{*}}\\{(1+\mathcal{O}(\varepsilon))\mathrm{dist}_{G}(u,S^{*}(u))+\varepsilon\cdot\min\\{\mathrm{dist}_{G}(u,U),\mathrm{dist}_{G}(S^{*}(u),U)\\}\\}.$
(4)

By maximizing over each term of (4) and using the fact that
${\min\\{a,b\\}\leq a}$ for any ${a,b\in\bbbr^{+}_{0}}$ in the second term we
get

$\operatorname{cost}_{H}(S^{*})\leq(1+\mathcal{O}(\varepsilon))\mathrm{OPT}_{G}+\varepsilon\cdot\max_{u\in
V_{C}^{*}}\mathrm{dist}_{G}(u,U).$ (5)

We are going to give an upper bound for the second term of (5) using the first
term. There are two cases to consider. If $u$ is covered by the constant-
approximate solution, then
$\mathrm{dist}_{G}(u,U)=\mathcal{O}(\mathrm{OPT}_{G})$. Otherwise $u$ has to
be an outlier in the approximate solution. We added all outliers to the set
$u$, so we have ${\mathrm{dist}_{G}(u,U)=0}$ in this case. In total, we have

$\operatorname{cost}_{H}(S^{*})\leq(1+\mathcal{O}(\varepsilon))\mathrm{OPT}_{G}.$
(6)

As $S^{*}$ is an optimal solution in $G$ but not necessarily in $H$ we get
from (6)

$\mathrm{OPT}_{H}\leq\operatorname{cost}_{H}(S^{*})\leq(1+\mathcal{O}(\varepsilon))\mathrm{OPT}_{G}$
(7)

The approximate solution has cost $(1+\varepsilon)\mathrm{OPT}_{H}$. By
multiplying both sides of (7), we get the desired bound. ∎

We are ready to prove Theorem 1.3.

######  Proof (of Theorem 1.3.)

Lemma 10 shows the correctness of the algorithm, it remains to bound its
running time. The algorithm consists of three steps, first we compute a
constant-factor approximation to the instance in polynomial time. Then we run
the algorithm from Theorem 4.2 on the input to obtain a host graph $H$. This
step runs in time $\mathcal{O}^{*}(g(k,p,h,\varepsilon))$ for some computable
function $g$. Finally, we run the algorithm from Theorem 4.1 on $H$. This step
takes time
$\mathcal{O}((\mathrm{tw}(H)/\varepsilon)^{\mathcal{O}(\mathrm{tw}(H))})$
where $\mathrm{tw}(H)=\mathcal{O}^{*}(g^{\prime}(k,p,h,\varepsilon))$ for some
computable function $g^{\prime}$. Thus the algorithm runs in $\mathrm{FPT}$
time with parameters $k$, $p$, $\varepsilon$, and the highway dimension of the
input.

##  5 EPAS for $k$-Supplier with Outliers on Low Treewidth Graphs

The following definition of treewidth is given in [14]. A  _tree
decomposition_ of a graph $G$ is a pair $\mathcal{T}=(T,\\{X_{t}\\}_{t\in
V(T)})$, where $T$ is a tree whose every node $t$ is assigned a vertex subset
$X_{t}\subseteq V(G)$, called a _bag_ , such that the following three
properties hold.

###### Property 1

Every vertex of $G$ is in at least one bag, i.e. $\cup_{t\in V(T)}X_{t}=V(G)$.

###### Property 2

For every edge $e\in E(G)$, there exists a node $t\in T$ such that the
corresponding bag $X_{t}$ contains both endpoints of $e$.

###### Property 3

For every $v\in V(G)$, the set $T_{u}=\\{t\in V(T)\mid u\in X_{t}\\}$, that is
the set of nodes whose corresponding bags contain $u$, induces a connected
subtree of $T$.

To improve comprehensibility, we shall refer to vertices of the underlying
tree as _nodes_. It follows from Property 3 that for all $i,j,k\in V(T)$, if
$j$ is on the path from $i$ to $k$ in $T$, then $X_{i}\cap X_{k}\subseteq
X_{j}$. The _width_ of a tree decomposition $\mathcal{T}=(T,\\{X_{t}\\}_{t\in
V(T)})$ equals $\max_{t\in V(T)}(\lvert X_{t}\rvert-1)$, that is, the maximum
size of its bag minus $1$. The _treewidth_ of a graph $G$, denoted by
$\mathrm{tw}(G)$, is the minimum possible width of a tree decomposition of
$G$.

For algorithmic purposes, it is often more convenient to work with nice tree
decompositions: a rooted tree decomposition $(T,\\{X_{t}\\}_{t\in V(T)})$ with
root $r\in V(T)$ is a _nice tree decomposition_ if each of its leaves $\ell\in
V(T)$ contains an empty bag (that is $X_{\ell}=\emptyset$) and inner nodes are
one of the following three types:

  * •

Introduce node: a node $t$ with exactly one child $t^{\prime}$ where
$X_{t}=X_{t^{\prime}}\cup\\{u\\}$ for some vertex $u\not\in X_{t^{\prime}}$.
We say that $u$ is _introduced_ at $t$.

  * •

Forget node: a node $t$ with exactly one child $t^{\prime}$ where
$X_{t}=X_{t^{\prime}}\setminus\\{v\\}$ for some vertex $v\in X_{t^{\prime}}$.
We say that $v$ is _forgotten_ at $t$.

  * •

Join node: a node $t$ with exactly two children $t_{1},t_{2}$ where
$X_{t}=X_{t_{1}}=X_{t_{2}}$.

It is known that if graph $G$ admits a tree decomposition of width at most
$k$, then it also admits a nice tree decomposition of width at most $k$.
Furthermore, given a tree decomposition $\mathcal{T}=(T,\\{X_{t}\\}_{t\in
V(T)})$ of $G$ of width at most $k$, one can in
$\mathcal{O}(k^{2}\cdot\max(\lvert V(T)\rvert,\lvert V(G)\rvert))$ time
compute a nice tree decomposition of $G$ of width at most $k$ that has at most
$\mathcal{O}(k\cdot\lvert V(G)\rvert)$ nodes, for more details, see [14, Lemma
7.4]. For this reason we shall always assume without loss of generality that
input tree decompositions of our algorithms are nice. By $V_{t}$ we denote
vertices which appear in bags in the subtree rooted at the vertex
corresponding to $X_{t}$ and by $G[X_{t}]$ and $G[V_{t}]$ we denote the
subgraph induced by vertices in bag $X_{t}$ and vertices $V_{t}$ respectively.

In this section we develop an EPAS for kSwO parameterized by $k$, $p$,
$\varepsilon$, and the treewidth of the input graph to prove Theorem 4.1. To
simplify the exposition, we restrict ourselves to instances with integral edge
lengths, and we also assume that $V_{S}\cap V_{C}=\emptyset$. We start by
giving an exact algorithm for the problem, which we later turn into an
approximation scheme by the technique of Lampis [31]. The overall approach
generalizes the approach for obtaining an EPAS for $k$-Center by Katsikarelis
et al. [30]. In the rest of this section, we denote the treewidth of the input
graph by $\mathrm{tw}$. The properties of the exact algorithm are summarized
by the following theorem.

###### Theorem 5.1

There exists an algorithm which given a kSwO instance $\mathcal{I}$ and cost
$\varrho\in\bbbn$ decides whether $\mathcal{I}$ has a feasible solution of
cost $\varrho$ running in time
$\mathcal{O}^{*}\left(\varrho^{\mathcal{O}(\mathrm{tw})}\right)$.

We give an equivalent formulation of kSwO which is more convenient for our
purposes. Let $(G,k,p)$ be an instance of the kSwO problem where $G=(V,E)$ has
edge lengths $d\colon E\to\bbbn$ and vertices are partitioned into clients
$V_{C}$ and suppliers $V_{S}$. A _distance labelling_ function $\mathrm{dl}$
of $G$ is a function $\mathrm{dl}\colon
V\to\\{0,\ldots,\varrho\\}\cup\\{\infty\\}$. We require that only suppliers
can have label $0$. We say that a vertex $u\in V$ is _satisfied_ by
$\mathrm{dl}$ if $\mathrm{dl}(u)=0$ or $u$ has a finite label and there exists
a neighbor $v\in N(u)$ such that $\mathrm{dl}(u)\geq\mathrm{dl}(v)+d(u,v)$.
Given a distance labelling function $\mathrm{dl}$, if every client is either
satisfied or has label $\infty$, then we say that $\mathrm{dl}$ is _valid_. We
define the _cost_ of a distance labelling function $\mathrm{dl}$ as
$\lvert\mathrm{dl}^{-1}(0)\rvert$ and the _penalty_ as
$\lvert\mathrm{dl}^{-1}(\infty)\cap V_{C}\rvert$. The following lemma shows
the equivalence between the two formulations. A special case of this statement
for $k$-Center is proved in the original algorithm, cf. [30, Lemma 26].

###### Lemma 11

A kSwO instance $\mathcal{I}=(G,k,p)$ admits a feasible solution of cost
$\varrho$ if and only if it admits a valid distance labelling function
$\mathrm{dl}\colon V\to\\{0,\ldots,\varrho\\}\cup\\{\infty\\}$ of cost $k$ and
penalty $p$.

###### Proof

Let $S\subseteq V_{S}$ be a solution of $\mathcal{I}$ of cost $\varrho$. We
construct the required distance labelling function $\mathrm{dl}$ as follows:

  1. 1.

for each vertex $u\in V$ with $\mathrm{dist}(u,S)\leq\varrho$ we set
$\mathrm{dl}(u)=\mathrm{dist}(u,S)$,

  2. 2.

we set the labels of the remaining vertices to $\infty$.

It is immediate that the cost of $\mathrm{dl}$ is at most $k$. From the
definition of kSwO it is also clear that outliers are clients whose distance
from $S$ exceeds $\varrho$, therefore the penalty of $\mathrm{dl}$ is at most
$p$. Consider a vertex $u\in V$ and a shortest path $\pi$ of length at most
$\varrho$ between $u$ and its nearest opened supplier $s\in S$. Let $v$ be the
neighbor of $u$ on $\pi$. We have
$\mathrm{dist}(u,s)=d(u,v)+\mathrm{dist}(v,s)$ and
$\mathrm{dl}(u)=\mathrm{dist}(u,s)$ and $\mathrm{dl}(v)=\mathrm{dist}(v,s)$,
this shows that every vertex and particularly every client with a finite label
is satisfied.

For the opposite direction, let $\mathrm{dl}$ be a distance labelling function
with properties given by the lemma statement. We select vertices with label
$0$ as the solution $S$. By definition of a distance labelling function these
can only be suppliers. It suffices to show that the distance of vertices with
finite labels from $S$ is at most the value of their label. This is the case
because a valid distance labelling function assigns finite labels to all but
(up to) $p$ vertices and the maximum finite label is $\varrho$. We prove this
claim by induction on label values. The base case is immediate since vertices
with label $0$ are precisely the solution $S$. In the induction step consider
a vertex $u$ with a finite label $\ell$. Since $u$ is a satisfied vertex,
there exists a neighbor $v\in N(u)$ such that
$\mathrm{dl}(u)\geq\mathrm{dl}(v)+d(u,v)$. As edge lengths are positive, we
have $\mathrm{dl}(u)>\mathrm{dl}(v)$ and using triangle inequality we obtain

$\mathrm{dist}(u,S)\leq\mathrm{dist}(u,v)+\mathrm{dist}(v,S)\leq\mathrm{dist}(u,v)+\mathrm{dl}(v)\leq\mathrm{dl}(u)$
(8)

where the second inequality follows from the induction hypothesis
$\mathrm{dist}(v,S)\leq\mathrm{dl}(v)$. This shows that clients with finite
labels are covered by the solution $S$ and since the penalty of $\mathrm{dl}$
is at most $p$, there are at most $p$ outliers. Also the cost of $\mathrm{dl}$
is at most $k$ thus we also have $\lvert S\rvert\leq k$. ∎

According to the proven equivalence, we may refer to a client with label
$\infty$ as an outlier and a supplier with label $0$ as an opened supplier.

We are ready to prove Theorem 5.1. The algorithm will be a standard dynamic
programming procedure on a nice tree decomposition of the input graph. As is
customary, let us assume that a nice tree decomposition of the input graph $G$
is given as a part of the input.

######  Proof (Theorem 5.1)

Let $\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ be a nice tree decomposition of
the input graph $G$ of width $\mathrm{tw}(G)$. For every node of $i\in
V(\mathcal{T})$ we maintain a dynamic programming table

$D_{i}\colon\big{(}(X_{i}\to\\{0,\ldots,\varrho\\}\cup\\{\infty\\})\times
2^{X_{i}\cap
V_{C}}\times\\{0,\ldots,k\\}\times\\{0,\ldots,p\\}\big{)}\to\\{0,1\\}.$ (9)

We may refer to the value $0$ in the dynamic programming table as _false_ and
to $1$ as _true_. Let $i$ be a node of a nice tree decomposition, recall that
$V_{i}$ is the set of vertices $u\in V(G)$ such that there exists a bag
corresponding to a node in the subtree rooted at $i$ which contains $u$. For a
distance labelling function $\mathrm{dl}$ of $X_{i}$ where $i\in V(T)$, a
subset of clients $S\subseteq X_{i}\cap V_{C}$ and constants $k_{i}$ and
$p_{i}$ the entry $D_{i}[\mathrm{dl},S,k_{i},p_{i}]$ is going to be $1$ if and
only if there exists a distance labelling function $\mathrm{dl}_{*}$ of
$G[V_{i}]$ such that

  * •

$\mathrm{dl}_{*}$ _agrees_ with $\mathrm{dl}$ on $X_{i}$, i.e. $(\forall u\in
X_{i})(\mathrm{dl}(u)=\mathrm{dl}_{*}(u))$,

  * •

the cost of $\mathrm{dl}_{*}$ is $k_{i}$, that is
$\lvert\mathrm{dl}_{*}^{-1}(0)\rvert=k_{i}$,

  * •

the penalty of $\mathrm{dl}_{*}$ is $p_{i}$, that is
$\lvert\mathrm{dl}_{*}^{-1}(\infty)\cap V_{C}\rvert=p_{i}$,

  * •

aside from clients $\mathrm{dl}_{*}^{-1}(\infty)\cap V_{C}$ with an infinite
label, every client $((V_{i}\setminus X_{i})\cup S)\cap V_{C}$ is satisfied.

In combination with Lemma 11, the input admits a feasible solution of cost
$\varrho$ if there exists a distance labelling $\mathrm{dl}_{r}$ of the root
node $r$, and constants $k_{r}\leq k$ and $p_{r}\leq p$ such that the entry
$D_{r}[\mathrm{dl}_{r},X_{r}\cap V_{C},k_{r},p_{r}]$ has value $1$.

To simplify the exposition, assume that every value of the dynamic programming
table at each node is initialized to value $0$.

##### Leaf node.

For a leaf node $\ell$ we have $V_{\ell}=\emptyset$. Thus the only table entry
which can have value $1$ is $D_{\ell}[\mathrm{dl},\emptyset,0,0]$ where the
domain of $\mathrm{dl}$ is an empty set.

##### Introduce node.

Let $i$ be an introduce node with a child node $j$ where
$X_{i}=X_{j}\cup\\{u\\}$ and $u\not\in X_{j}$. Let
$D_{j}[\mathrm{dl}_{j},S_{j},k_{j},p_{j}]$ be an entry of the table of the
child node $j$ with value $1$. We construct a distance labelling function
$\mathrm{dl}_{i}$ which agrees with $\mathrm{dl}_{j}$ on $X_{j}$ and tries all
possible values for $u$. In particular the constructed distance labelling
functions set $\mathrm{dl}_{i}(u)$ to values
$\\{1,\ldots,\varrho\\}\cup\\{\infty\\}$ and additionally we try the label $0$
for $u$ if $u$ is a supplier. For such a distance labelling function
$\mathrm{dl}_{i}$ we compute $S_{i}$ to be the set of satisfied clients of
$X_{i}$ as follows. We add the entire set $S_{j}$ to $S_{i}$, we add $u$ to
$S_{i}$ if there exists a neighbor $v\in N(u)$ so that
$\mathrm{dl}_{i}(u)\geq\mathrm{dl}_{i}(v)+d(u,v)$, and we add neighbors $w\in
N(u)$ to $S_{i}$ for which it holds that
$\mathrm{dl}_{i}(w)\geq\mathrm{dl}_{i}(u)+d(u,w)$. If $\mathrm{dl}_{i}(u)=0$
and $k_{j}\leq k-1$, then we set the entry
$D_{i}[\mathrm{dl}_{i},S_{i},k_{j}+1,p_{j}]$ to true. If
$\mathrm{dl}_{i}(u)\in\\{1,\ldots,\varrho\\}$, then we set the entry
$D_{i}[\mathrm{dl}_{i},S_{i},k_{j},p_{j}]$ to true. If
$\mathrm{dl}_{i}(u)=\infty$, $u\in V_{C}$, and $p_{j}\leq p-1$, then we set
the entry $D_{i}[\mathrm{dl}_{i},S_{i},k_{j},p_{j}+1]$ to true. If
$\mathrm{dl}_{i}(u)=\infty$ and $u\in V_{S}$, then we set the entry
$D_{i}[\mathrm{dl}_{i},S_{i},k_{j},p_{j}]$ to true.

We proceed to showing the correctness. Let $\widehat{\mathrm{dl}}$ be a
distance labelling function of $G[V_{i}]$ with cost $\widehat{k}$ and penalty
$\widehat{p}$ such that all clients of $V_{i}\setminus X_{i}$ with a finite
label are satisfied. We denote by $\widehat{S}$ the set of clients in $V_{i}$
satisfied by $\widehat{\mathrm{dl}}$. We want to show that the algorithm sets
the table entry $D_{i}[\mathrm{dl}_{i},S_{i},k_{i},p_{i}]$ to $1$ where
$\mathrm{dl}_{i}$ agrees with $\widehat{\mathrm{dl}}$ on $X_{i}$,
$S_{i}=\widehat{S}\cap X_{i}$, $k_{i}=\widehat{k}$, and $p_{i}=\widehat{p}$.
By the induction hypothesis this property holds in the child node, thus there
exists an entry $D_{j}[\mathrm{dl}_{j},S_{j},k_{j},p_{j}]$ with value $1$
where $\mathrm{dl}_{j}$ agrees with $\widehat{\mathrm{dl}}$ on $X_{j}$,
$S_{j}=\widehat{S}\cap X_{j}$, and the cost and the penalty of
$\widehat{\mathrm{dl}}$ restricted to $V_{j}$ is $k_{j}$ and $p_{j}$
respectively. The algorithm considers a distance labelling function
$\mathrm{dl}_{i}$ which agrees with $\mathrm{dl}_{j}$ on $X_{j}$ and sets
$\mathrm{dl}_{i}(u)=\widehat{\mathrm{dl}}(u)$. We need to show that the
algorithm computes the set $S_{i}$ correctly. Recall that by Property 3 of
tree decompositions we have $u\not\in V_{j}$. If a client of $X_{i}\setminus
N[u]$ is satisfied by $\mathrm{dl}_{j}$, then it is also satisfied by
$\mathrm{dl}_{i}$ since the label of the neighbor which satisfies it remains
the same. Hence we have $S_{j}\subseteq S_{i}$ and $S_{i}\setminus
S_{j}\subseteq N[u]$. The algorithm handles this by adding the entire set
$S_{j}$ to $S_{i}$. If $u\in\widehat{S}$, then there exists a neighbor $v\in
N(u)\cap V_{i}$ such that
$\widehat{\mathrm{dl}}(u)\geq\widehat{\mathrm{dl}}(v)+d(u,v)$. In particular
this means that there exists a node in a subtree rooted at $i$ whose bag
contains $v$. We need to show that $v\in X_{i}$ as well. For a vertex $a\in
V(G)$, let $T_{a}$ be the set of nodes of the tree decomposition $\mathcal{T}$
whose bags contain $a$. For a subset $U\subseteq V(T)$ we denote
$X_{U}=\\{X_{w}\mid w\in U\\}$. By Property 2 of tree decompositions, there
must exist a node of $\mathcal{T}$ whose corresponding bag contains both $u$
and $v$. Thus $X_{T_{u}}\cap X_{T_{v}}\neq\emptyset$. If it were the case that
$v\not\in X_{i}$, then a tree decomposition satisfying properties $u\in
X_{i}$, $u\not\in X_{j}$, $v\in V_{i}$, and that there exists a node whose bag
contains both $u$ and $v$ necessarily violates Property 3. We conclude that
$v\in X_{i}$. Since $\widehat{\mathrm{dl}}$ agrees with $\mathrm{dl}_{i}$, the
algorithm will find $v$ in $X_{i}$ and add $u$ to $S_{i}$. For a client $w\in
N(u)\cap X_{i}$, we have $(N(w)\cap X_{i})\setminus(N(w)\cap X_{j})=\\{u\\}$,
since $i$ is an introduce node introducing $u$. Therefore the only reason why
$w$ would be satisfied by $\mathrm{dl}_{i}$ but not by $\mathrm{dl}_{j}$ is
that it is satisfied by $u$. Then the set $S_{j}$ is the set $S_{i}$ without
clients in $X_{i}$ which are satisfied only by $u$. The algorithm adds to
$S_{i}$ those vertices of $N(u)\cap X_{i}$ which are satisfied by $u$. It
remains to describe values $k_{i}$ and $p_{i}$, we distinguish the following
cases:

  * •

Case $\widehat{\mathrm{dl}}(u)=0$. As $u\not\in V_{j}$, we have
$\lvert\widehat{\mathrm{dl}}^{-1}(0)\cap
V_{i}\rvert=\lvert\widehat{\mathrm{dl}}^{-1}(0)\cap V_{j}\rvert+1$. Since
$\widehat{\mathrm{dl}}(u)\neq\infty$, we have
$\lvert\widehat{\mathrm{dl}}^{-1}(\infty)\cap V_{i}\cap
V_{C}\rvert=\lvert\widehat{\mathrm{dl}}^{-1}(\infty)\cap V_{j}\cap
V_{C}\rvert$. Thus the algorithm sets $k_{i}=k_{j}+1$ and $p_{i}=p_{j}$.

  * •

Case $\widehat{\mathrm{dl}}(u)\in\\{1,\ldots,\varrho\\}$. Since
$\widehat{\mathrm{dl}}(u)\not\in\\{0,\infty\\}$, we have
$\lvert\widehat{\mathrm{dl}}^{-1}(0)\cap
V_{i}\rvert=\lvert\widehat{\mathrm{dl}}^{-1}(0)\cap V_{j}\rvert$ and
$\lvert\widehat{\mathrm{dl}}^{-1}(\infty)\cap V_{i}\cap
V_{C}\rvert=\lvert\widehat{\mathrm{dl}}^{-1}(\infty)\cap V_{j}\cap
V_{C}\rvert$, hence $k_{i}=k_{j}$ and $p_{i}=p_{j}$ respectively.

  * •

Case $\widehat{\mathrm{dl}}(u)=\infty$. We have
$\lvert\widehat{\mathrm{dl}}^{-1}(0)\cap
V_{i}\rvert=\lvert\widehat{\mathrm{dl}}^{-1}(0)\cap V_{j}\rvert$ and therefore
$k_{i}=k_{j}$. If $u\in V_{C}$, then
$\lvert\widehat{\mathrm{dl}}^{-1}(\infty)\cap V_{i}\cap
V_{C}\rvert=\lvert\widehat{\mathrm{dl}}^{-1}(\infty)\cap V_{j}\cap
V_{C}\rvert+1$ and $p_{i}=p_{j}+1$. Otherwise $u\in V_{S}$ and then we have
$p_{i}=p_{j}$.

For the opposite direction, assume that the algorithm sets the value of an
entry $D_{i}[\mathrm{dl}_{i},S_{i},k_{i},p_{i}]$ to $1$. By the description of
the algorithm, this means that there exists an entry
$D_{j}[\mathrm{dl}_{j},S_{j},k_{j},p_{j}]$ in the table of the child node set
to $1$ where $\mathrm{dl}_{i}$ agrees with $\mathrm{dl}_{j}$ on $X_{j}$,
$S_{j}\subseteq S_{i}$, $k_{j}\leq k_{i}$, and $p_{j}\leq p_{i}$. By the
induction hypothesis there exists a valid distance labelling function
$\widehat{\mathrm{dl}}_{j}$ on $V_{j}$ which agrees with $\mathrm{dl}_{j}$ on
$X_{j}$, satisfies clients $S_{j}$ of $X_{j}$, and has cost $k_{j}$ and
penalty $p_{j}$. We claim that the function $\widehat{\mathrm{dl}}_{i}$ which
extends $\widehat{\mathrm{dl}}_{j}$ by setting
$\widehat{\mathrm{dl}}_{i}(u)=\mathrm{dl}_{i}(u)$ has the required properties.
We need to show that all clients of $S_{i}$ are satisfied by
$\widehat{\mathrm{dl}}_{i}$. Every satisfied client of $S_{j}$ is still
satisfied by $\widehat{\mathrm{dl}}_{i}$ since the distance label of the
neighbor which satisfies it is preserved. From the description of the
algorithm it is clear that the added clients $S_{i}\setminus S_{j}$ are
satisfied by $\widehat{\mathrm{dl}}_{i}$. It remains to verify that the
algorithm computes the cost of $\widehat{\mathrm{dl}}_{i}$ correctly. Recall
that $V_{i}\setminus V_{j}=\\{u\\}$. We distinguish the following cases based
on the description of the algorithm:

  * •

Case $\mathrm{dl}_{i}(u)=0$. In this case
$\widehat{\mathrm{dl}}_{i}^{-1}(0)=\widehat{\mathrm{dl}}_{j}^{-1}(0)\cup\\{u\\}$
and $\widehat{\mathrm{dl}}_{i}^{-1}(\infty)\cap
V_{C}=\widehat{\mathrm{dl}}_{j}^{-1}(\infty)\cap V_{C}$. Then the cost of
$\widehat{\mathrm{dl}}_{i}$ is $k_{j}+1$ and the penalty is $p_{j}$.

  * •

Cases $\mathrm{dl}_{i}(u)\in\\{1,\ldots,\varrho\\}$ and
$\mathrm{dl}_{i}(u)=\infty\wedge u\in V_{S}$. In this case
$\widehat{\mathrm{dl}}_{i}^{-1}(0)=\widehat{\mathrm{dl}}_{j}^{-1}(0)$ and
$\widehat{\mathrm{dl}}_{i}^{-1}(\infty)\cap
V_{C}=\widehat{\mathrm{dl}}_{j}^{-1}(\infty)\cap V_{C}$. Then the cost of
$\widehat{\mathrm{dl}}_{i}$ is $k_{j}$ and the penalty is $p_{j}$.

  * •

Case $\mathrm{dl}_{i}(u)=\infty\wedge u\in V_{C}$. In this case
$\widehat{\mathrm{dl}}_{i}^{-1}(0)=\widehat{\mathrm{dl}}_{j}^{-1}(0)$ and
$\widehat{\mathrm{dl}}_{i}^{-1}(\infty)\cap
V_{C}=\left(\widehat{\mathrm{dl}}_{j}^{-1}(\infty)\cap
V_{C}\right)\cup\\{u\\}$. Then the cost of $\widehat{\mathrm{dl}}_{i}$ is
$k_{j}$ and the penalty is $p_{j}+1$.

##### Forget node.

Let $i$ be a forget node where $X_{i}=X_{j}\setminus\\{u\\}$ and $u\in X_{j}$.
For any distance labelling function $\mathrm{dl}$ of $X_{i}$ we denote
$L_{c}(\mathrm{dl})$ the set of functions which extend $\mathrm{dl}$ by
assigning labels $\\{1,\ldots,\varrho\\}$ to $u$, $L_{s}(\mathrm{dl})$ the set
of functions which extend $\mathrm{dl}$ by assigning labels
$\\{0,\ldots,\varrho\\}\cup\\{\infty\\}$ to $u$, and $L_{\infty}(\mathrm{dl})$
the extension of $\mathrm{dl}$ which assigns label $\infty$ to $u$. Let
$\mathrm{dl}_{i}$ be any distance labelling function of $X_{i}$, $S_{i}$ be
any subset of clients of $X_{i}$, $k_{i}\in\\{0,\ldots,k\\}$, and
$p_{i}\in\\{0,\ldots,p\\}$. If $u$ is a supplier, then we set

$D_{i}[\mathrm{dl}_{i},S_{i},k_{i},p_{i}]=\bigvee_{\mathrm{dl}_{j}\in
L_{s}(\mathrm{dl}_{i})}D_{j}[\mathrm{dl}_{j},S_{i},k_{i},p_{i}].$ (10)

If $u$ is a client, then we set

$D_{i}[\mathrm{dl}_{i},S_{i},k_{i},p_{i}]=\left(\bigvee_{\mathrm{dl}_{j}\in
L_{c}(\mathrm{dl}_{i})}D_{j}[\mathrm{dl}_{j},S_{i}\cup\\{u\\},k_{i},p_{i}]\right)\vee
D_{j}[L_{\infty}(\mathrm{dl}),S_{i},k_{i},p_{i}].$ (11)

We proceed to showing the correctness. Recall that by properties of nice tree
decompositions, we have $V_{i}=V_{j}$ for the forget node $i$. Let
$\widehat{\mathrm{dl}}$ be a distance labelling function of $G[V_{i}]$ of cost
$\widehat{k}$ and penalty $\widehat{p}$ such that all clients of
$V_{i}\setminus X_{i}$ with a finite label are satisfied. Given a node $t$ of
the tree decomposition, let $\widehat{\mathrm{dl}}_{t}$ be the restriction of
$\widehat{\mathrm{dl}}$ to $X_{t}$, and $\widehat{S}_{t}$ be the set of
satisfied of clients of $X_{t}$ by $\widehat{\mathrm{dl}}$. Our goal is to
show that the algorithm sets the entry
$D_{i}[\widehat{\mathrm{dl}}_{i},\widehat{S}_{i},\widehat{k},\widehat{p}]$ to
$1$. From the induction hypothesis, the entry
$D_{j}[\widehat{\mathrm{dl}}_{j},\widehat{S}_{j},k_{j},p_{j}]$ is set to $1$
for some values $k_{j}$ and $p_{j}$; in fact it is the case that
$k_{j}=\widehat{k}$ and $p_{j}=\widehat{p}$ as $V_{i}=V_{j}$. Since the
algorithm inspects all entries of the table $D_{i}$, it will eventually
consider the entry
$D_{i}[\widehat{\mathrm{dl}}_{i},\widehat{S}_{i},\widehat{k},\widehat{p}]$. By
trying all possible values for the forgotten vertex $u$, it will consider the
labelling $\widehat{\mathrm{dl}}_{j}$ of $X_{j}$. To finish the proof of this
direction, it remains to determine the relationship between $\widehat{S}_{i}$
and $\widehat{S}_{j}$.

  * •

Case $u\in V_{S}$. We have $X_{i}\cap V_{C}=X_{j}\cap V_{C}$ and thus
$\widehat{S}_{i}=\widehat{S}_{j}$.

  * •

Case $\widehat{\mathrm{dl}}(u)\in\\{1,\ldots,\varrho\\}$ and $u\in V_{C}$. If
the label of the forgotten client $u$ is finite, then it must be satisfied by
$\widehat{\mathrm{dl}}$ from the requirement that $\widehat{\mathrm{dl}}$
satisfies all vertices of $V_{i}\setminus X_{i}$. Thus
$\widehat{S}_{i}\cup\\{u\\}=\widehat{S}_{j}$.

  * •

Case $\widehat{\mathrm{dl}}(u)=\infty$ and $u\in V_{C}$. If the label of the
forgotten client $u$ is $\infty$, then it is ignored by
$\widehat{\mathrm{dl}}$. In this case we have
$\widehat{S}_{i}=\widehat{S}_{j}$.

For the opposite direction let $D_{i}[\mathrm{dl}_{i},S_{i},k_{i},p_{i}]$ be
an entry set to $1$ by the algorithm. Then it follows from the description of
the algorithm, that there is an entry
$D_{j}[\mathrm{dl}_{j},S_{j},k_{j},p_{j}]$ set to $1$ in the table of the
child $j$ where $\mathrm{dl}_{j}$ is an extension of $\mathrm{dl}_{i}$ to
$X_{j}$, $S_{j}\supseteq S_{i}$, $k_{i}=k_{j}$ and $p_{i}=p_{j}$. By the
induction hypothesis, there exists a distance labelling function
$\widehat{\mathrm{dl}}_{j}$ on $V_{j}$ which agrees with $\mathrm{dl}_{j}$ on
$X_{j}$, satisfies clients $S_{j}$ of $X_{j}$, has cost $k_{j}$ and penalty
$p_{j}$. We claim that $\widehat{\mathrm{dl}}_{j}$ also agrees with
$\mathrm{dl}_{i}$, satisfies clients $S_{i}$ of $X_{i}$, has cost $k_{i}$ and
penalty $p_{i}$. Since $\mathrm{dl}_{j}$ agrees with $\mathrm{dl}_{i}$ on
$X_{i}$ and $X_{i}\subseteq X_{j}$, $\widehat{\mathrm{dl}}_{j}$ agrees with
$\mathrm{dl}_{i}$. The property that every client of $S_{i}$ is satisfied by
$\widehat{\mathrm{dl}}_{j}$ follows from $S_{i}\subseteq S_{j}$,
$V_{i}=V_{j}$, and the fact that $\widehat{\mathrm{dl}}_{j}$ satisfies $S_{j}$
by the induction hypothesis. From $V_{i}=V_{j}$ it also follows that
$k_{i}=k_{j}$ and $p_{i}=p_{j}$.

##### Join node.

Let $i$ be a join node with children $j_{1}$ and $j_{2}$ where
$X_{i}=X_{j_{1}}=X_{j_{2}}$. Let $\mathrm{dl}_{i}$ be a distance labelling
function on $X_{i}$, then for each pair of true entries
$D_{j_{1}}[\mathrm{dl},S_{1},k_{1},p_{1}]$ and
$D_{j_{2}}[\mathrm{dl},S_{2},k_{2},p_{2}]$ we set to $1$ the entry

$D_{i}\left[\mathrm{dl}_{i},S_{1}\cup
S_{2},k_{1}+k_{2}-\lvert\mathrm{dl}_{i}^{-1}(0)\rvert,p_{1}+p_{2}-\lvert\mathrm{dl}_{i}^{-1}(\infty)\cap
V_{C}\rvert\right].$ (12)

We proceed to showing the correctness. It follows from the properties of nice
tree decompositions that $V_{i}=V_{j_{1}}\cup V_{j_{2}}$. Let
$\widehat{\mathrm{dl}}$ be a valid distance labelling function of $G[V_{i}]$
of cost $\widehat{k}$ and penalty $\widehat{p}$ such that all clients of
$V_{i}\setminus X_{i}$ with a finite label are satisfied. We denote by
$\widehat{S}_{i}$ the set of satisfied clients in $X_{i}$ and by
$\widehat{\mathrm{dl}}_{i}$ the restriction of $\widehat{\mathrm{dl}}$ to
$X_{i}$. Let $a\in\\{1,2\\}$, $\widehat{\mathrm{dl}}_{a}$ be the restriction
of $\widehat{\mathrm{dl}}$ to $V_{j_{a}}$, $\widehat{S}_{j_{a}}$ be the set of
clients of $X_{j_{a}}$ satisfied by $\widehat{\mathrm{dl}}_{a}$,
$\widehat{C}_{a}$ be the set of opened suppliers in $V_{j_{a}}$, and
$\widehat{O}_{a}$ be the set of outliers in $V_{j_{a}}$. Note that
$\widehat{\mathrm{dl}},\widehat{\mathrm{dl}}_{1}$ and
$\widehat{\mathrm{dl}}_{2}$ agree with each other on $X_{i}$. From the
induction hypothesis the entries
$D_{j_{a}}\left[\widehat{\mathrm{dl}}_{i},\widehat{S}_{j_{a}},\lvert\widehat{C}_{j_{a}}\rvert,\lvert\widehat{O}_{j_{a}}\rvert\right]$
are set to $1$. To show that
$\widehat{S}_{i}=\widehat{S}_{j_{1}}\cup\widehat{S}_{j_{2}}$, we use the
standard approach of showing
$\widehat{S}_{i}\supseteq\widehat{S}_{j_{1}}\cup\widehat{S}_{j_{2}}$ and
$\widehat{S}_{i}\subseteq\widehat{S}_{j_{1}}\cup\widehat{S}_{j_{2}}$. From
$V_{j_{1}}\subseteq V_{i}$ it trivially follows that
$\widehat{S}_{j_{a}}\subseteq\widehat{S}_{i}$. For a satisfied client
$v\in\widehat{S}_{i}$, we want to show that
$v\in\widehat{S}_{j_{1}}\cup\widehat{S}_{j_{2}}$. As $V_{i}=V_{j_{1}}\cup
V_{j_{2}}$, the neighbor $w$ which satisfies $v$ lies in $V_{j_{1}}\cup
V_{j_{2}}$. Hence it must be the case that $v$ is satisfied in at least in one
of $V_{j_{1}}$ or $V_{j_{2}}$ and thus $v$ is satisfied in at least one of
$\widehat{S}_{j_{1}}$ or $\widehat{S}_{j_{2}}$. It follows from Property 3 of
tree decompositions that if a vertex $w$ is simultaneously contained in a bag
of some node of the subtree rooted in $j_{1}$ and in a bag of some node of the
subtree rooted in $j_{2}$, then $w\in X_{i}$. This means that $V_{j_{1}}\cap
V_{j_{2}}\subseteq X_{i}$ and in particular
$\widehat{C}_{1}\cap\widehat{C}_{2}\subseteq X_{i}$ and
$\widehat{O}_{1}\cap\widehat{O}_{2}\subseteq X_{i}$. Since
$\widehat{\mathrm{dl}}$, $\widehat{\mathrm{dl}}_{1}$, and
$\widehat{\mathrm{dl}}_{2}$ agree with each other on $X_{i}$,
$\widehat{C}_{1}\cap X_{i}=\widehat{C}_{2}\cap X_{i}$ and $\widehat{O}_{1}\cap
X_{i}=\widehat{O}_{2}\cap X_{i}$. Using these facts we have
$\lvert\widehat{C}_{1}\rvert+\lvert\widehat{C}_{2}\rvert=\widehat{k}+\lvert\widehat{\mathrm{dl}}^{-1}(0)\cap
X_{i}\rvert$ and
$\lvert\widehat{O}_{1}\rvert+\lvert\widehat{O}_{2}\rvert=\widehat{p}+\lvert\widehat{\mathrm{dl}}^{-1}(\infty)\cap
X_{i}\cap V_{C}\rvert$, as every opened supplier and every outlier is counted
twice in $X_{i}$.

For the opposite direction, let $D_{i}[\mathrm{dl}_{i},S_{i},k_{i},p_{i}]$ be
an entry set to $1$ by the algorithm. From the description of the algorithm,
this means that there exist entries
$D_{j_{1}}[\mathrm{dl}_{i},S_{j_{1}},k_{j_{1}},p_{j_{1}}]$ and
$D_{j_{2}}[\mathrm{dl}_{i},S_{j_{2}},k_{j_{2}},p_{j_{2}}]$ set to $1$ where
$S_{j_{1}}$ and $S_{j_{2}}$ are subsets of $X_{i}$ (where
$X_{i}=X_{j_{1}}=X_{j_{2}}$ for a join node $i$). By the induction hypothesis,
for $a\in\\{1,2\\}$ there exists a valid distance labelling function
$\widehat{\mathrm{dl}}_{a}$ on $V_{j_{a}}$ which agrees with $\mathrm{dl}_{i}$
on $X_{j_{a}}$, satisfies clients $S_{j_{a}}\subseteq X_{j_{a}}$, and has cost
$\widehat{k}_{a}$ and penalty $\widehat{p}_{a}$. We claim that a function
$\mathrm{dl}$ which behaves as $\widehat{\mathrm{dl}}_{1}$ on $V_{j_{1}}$ and
as $\widehat{\mathrm{dl}}_{2}$ on $V_{j_{2}}$ has the desired properties. To
verify that $\mathrm{dl}$ is a function (and not a multifunction), we use the
fact that $V_{j_{1}}\cap V_{j_{2}}\subseteq X_{i}$. The algorithm requires
that $\widehat{\mathrm{dl}}_{1}$ and $\widehat{\mathrm{dl}}_{2}$ behave the
same on $X_{i}$, thus $\mathrm{dl}$ is indeed a function. We can prove the
remaining required properties, i.e. $S_{i}=S_{j_{1}}\cup S_{j_{2}}$,
$k_{i}=k_{j_{1}}+k_{j_{2}}-\lvert\mathrm{dl}_{i}^{-1}(0)\rvert$, and
$p_{i}=p_{j_{1}}+p_{j_{2}}$, identically as in the proof of the opposite
direction.

##### Running time.

The size of the table at each node is at most $(\varrho+2)^{\mathrm{tw}}\cdot
2^{\mathrm{tw}}\cdot(k+1)\cdot(p+1)$. In each introduce node $i$, we inspect
all table entries of its child $j$ and for each such child entry we
recalculate the set of satisfied vertices, suppliers with label $0$, and
ignored clients in time $\mathrm{tw}$. In each forget node $i$, for each table
entry of $i$ we inspect up to $\varrho+2$ entries in the table of the child
$j$. In each join node $i$, we try to combine all possible entries from its
children $j_{1}$ and $j_{2}$ which takes time $\lvert
D_{j_{1}}\rvert\cdot\lvert D_{j_{2}}\rvert\leq((\varrho+2)^{\mathrm{tw}}\cdot
2^{\mathrm{tw}}\cdot(k+1)\cdot(p+1))^{2}$. Overall, the running time of the
algorithm is at most
$\mathcal{O}^{*}((4(\varrho+2))^{\mathcal{O}(\mathrm{tw})})$. ∎

####  5.0.1 The approximation scheme.

Now we describe a parameterized approximation scheme based on the algorithm
from Theorem 5.1. We will need the following result by Chatterjee et al. [12].

######  Theorem 5.2 ([12])

Let $G$ be a graph. There exists an algorithm which, given a tree
decomposition $\mathcal{T}$ of $G$ such that $\mathcal{T}$ has $n$ nodes and
width $\mathrm{tw}$, produces a nice tree decomposition of $G$ with width at
most $4\mathrm{tw}+3$ and height $\mathcal{O}(\mathrm{tw}\cdot\log n)$ in time
$\mathcal{O}(\mathrm{tw}\cdot n)$.

Let us give an approximate version of the distance labelling problem for a
fixed error parameter $\varepsilon>0$. This is a generalization of the
approximate distance labelling used in the original algorithm [30]. Let
$(G,k,p)$ be a kSwO instance with edge lengths $d:E\to\bbbn$ and $\delta>0$
some appropriately chosen secondary parameter (we will eventually set
$\delta\approx\frac{\varepsilon}{\log n}$). Let
$\Sigma_{\varrho}=\\{(1+\delta)^{i}:i\in\bbbn,(1+\delta)^{i}\leq(1+\varepsilon)\varrho\\}$,
we define a  _$\delta$ -labelling function_ of $V$ as a function
$\mathrm{dl}_{\delta}:V\to\Sigma_{\varrho}\cup\\{0,\infty\\}$. We require that
only suppliers can have label $0$. A vertex $u$ is  _$\varepsilon$ -satisfied_
if $\mathrm{dl}_{\delta}(u)=0$ or if $u$ has a finite label and there exists
$v\in N(u)$ such that
$\mathrm{dl}_{\delta}(u)\geq\mathrm{dl}_{\delta}(v)+\frac{d(u,v)}{1+\varepsilon}$.
Given a $\delta$-labelling function $\mathrm{dl}_{\delta}$, if every client is
either $\varepsilon$-satisfied or has label $\infty$, then we say that
$\mathrm{dl}_{\delta}$ is _valid_. We define the  _cost_ of such a function
$\mathrm{dl}_{\delta}$ as $\lvert\mathrm{dl}_{\delta}^{-1}(0)\rvert$ and its
_penalty_ as $\lvert\mathrm{dl}_{\delta}^{-1}(\infty)\cap V_{C}\rvert$. The
following lemma shows that given a $\delta$-labelling function of cost $k$ and
penalty $p$, we can produce a solution to the kSwO problem which opens $k$
centers, creates $p$ outliers and has cost $(1+\varepsilon)^{2}\varrho$.

###### Lemma 12

Let $\mathcal{I}=(G,k,p)$ be an instance of the kSwO problem. If there exists
a valid $\delta$-labelling function of $G$ with cost at most $k$ and penalty
at most $p$, then $\mathcal{I}$ has a feasible solution of cost
$(1+\varepsilon)^{2}\varrho$.

###### Proof

We select vertices with label $0$ as the solution $S$. The number of opened
suppliers is the cost of the function, hence we open at most $k$ suppliers. We
will show by induction on $i$ that if
$\mathrm{dl}_{\delta}(u)=(1+\delta)^{i}$, then
$\mathrm{dist}(u,S)\leq(1+\varepsilon)\mathrm{dl}_{\delta}(u)$. In the base
case let $u$ be an $\varepsilon$-satisfied vertex with
$\mathrm{dl}_{\delta}(u)=(1+\delta)$. Then there exists a neighbor $v\in N(u)$
with
$\mathrm{dl}_{\delta}(u)\geq\mathrm{dl}_{\delta}(v)+\frac{d(u,v)}{1+\varepsilon}$.
Since $d(u,v)>0$, it follows that
$\mathrm{dl}_{\delta}(u)>\mathrm{dl}_{\delta}(v)$ and the only possible
$\delta$-label less than $(1+\delta)$ is $0$, hence
$\mathrm{dl}_{\delta}(v)=0$. Then we have
$(1+\delta)\geq\frac{d(u,v)}{1+\varepsilon}$ which shows the base case as
$v\in S$. For the induction step, let $u$ be an $\varepsilon$-satisfied vertex
with $\mathrm{dl}_{\delta}(u)=(1+\delta)^{i+1}$. There exists a neighbor $v\in
N(u)$ such that
$\mathrm{dl}_{\delta}(u)\geq\mathrm{dl}_{\delta}(v)+\frac{d(u,v)}{1+\varepsilon}$.
As edge lengths are positive, we have
$\mathrm{dl}_{\delta}(u)>\mathrm{dl}_{\delta}(v)$ and using induction
hypothesis we receive $\mathrm{dist}(v,S)\leq\mathrm{dl}_{\delta}(v)$. By
triangle inequality we have $\mathrm{dist}(u,S)\leq
d(u,v)+\mathrm{dist}(v,S)\leq
d(u,v)+\mathrm{dl}_{\delta}(v)=(1+\varepsilon)\left(\frac{d(u,v)}{1+\varepsilon}+\mathrm{dl}_{\delta}(v)\right)\leq(1+\varepsilon)\mathrm{dl}_{\delta}(u)$.

Since all satisfied clients have a $\delta$-label at most
$(1+\varepsilon)\varrho$, all satisfied clients are at distance at most
$(1+\varepsilon)^{2}\varrho$ from $S$. The number of outliers is at most $p$
as the penalty of $\mathrm{dl}_{\delta}$ is at most $p$. ∎

The following two lemmas from [30], which they use for their EPAS for
$k$-Center, will be useful for us as well. The first lemma shows that adding
all missing edges between vertices of a single bag of length equal to their
shortest-path distance does not change the set of solutions. The original
formulation is for $k$-Center, however, their proof generalizes to kSwO
without any major modifications.

######  Lemma 13 ([30, Lemma 29])

Let $\mathcal{I}=(G,k,p)$ be a kSwO instance, $\mathcal{T}$ a tree
decomposition of $G$ and $u,v\in V$ two vertices which appear together in a
bag of $\mathcal{T}$ and $(u,v)\not\in E$. Let $G^{\prime}$ be the graph
obtained from $G$ by adding the edge $\\{u,v\\}$ with length
$\mathrm{dist}(u,v)$ and let $\mathcal{I}^{\prime}=(G^{\prime},k,p)$ be a kSwO
instance. Then $\mathcal{I}$ has a feasible solution of cost $\varrho$ if and
only if $\mathcal{I}^{\prime}$ does.

The second lemma shows that an algorithm with a running time in the form
$\mathcal{O}^{*}\left((\frac{\log n}{\varepsilon})^{\mathcal{O}(k)}\right)$ is
still an $\mathrm{FPT}$ algorithm.

######  Lemma 14 ([30, Lemma 1])

Let $\mathcal{A}$ be an algorithm for a parameterized problem with parameter
$k$ such that the running time of $\mathcal{A}$ is
$\mathcal{O}^{*}\left((\frac{\log n}{\varepsilon})^{\mathcal{O}(k)}\right)$.
Then the running time of $\mathcal{A}$ can be bounded by
$\mathcal{O}^{*}\left((\frac{k}{\varepsilon})^{\mathcal{O}(k)}\right)$.

We are ready to prove Theorem 4.1. The proof follows the proof of the original
algorithm, cf. [30, Theorem 31]. The main obstacle lies in bounding the
accumulated error during the execution of the algorithm. The original proof
heavily relies on the properties of the algorithm they present for $k$-Center.
Hence, we will have to modify their proof to work with the algorithm we give
for kSwO.

######  Proof (Theorem 4.1)

Our algorithm will follow along the same lines as the algorithm in Theorem
5.1. The major difference is that instead of distance labelling functions we
consider $\delta$-labelling functions for some $\delta$ we specify later and
instead of satisfiability we use $\varepsilon$-satisfiability.

Recall that
$\Sigma_{\varrho}=\\{0\\}\cup\\{(1+\delta)^{i}:i\in\bbbn,(1+\delta)^{i}\leq(1+\varepsilon)\varrho\\}\cup\\{\infty\\}$.
For each node $i\in V(T)$ we define a table

$D^{\delta}_{i}\colon\left((X_{i}\to\Sigma_{\varrho})\times 2^{X_{i}\cap
V_{C}}\times\\{0,\ldots,k\\}\times\\{0,\ldots,p\\}\right)\to\\{0,1\\}.$ (13)

We may refer to value $1$ in the dynamic programming table as  _true_ and to
value $0$ as _false_. Recall that our definitions of a $\delta$-labelling
allows only suppliers to have label $0$. For a node $i\in V(T)$, a
$\delta$-labelling function $\mathrm{dl}_{\delta}\colon
X_{i}\to\Sigma_{\varrho}$, a subset of clients $S\subseteq 2^{X_{i}\cap
V_{C}}$, and integers $k_{i}$ and $p_{i}$ where $0\leq k_{i}\leq k$ and $0\leq
p_{i}\leq p$, the value of an entry
$D^{\delta}_{i}[\mathrm{dl}_{\delta},S,k_{i},p_{i}]$ is $1$ if and only if
there exists a $\delta$-labelling of $G[V_{i}]$ which agrees with
$\mathrm{dl}_{\delta}$ on $X_{i}$, satisfies clients $((V_{i}\setminus
X_{i})\cup S)\cap V_{C}$, has cost $k_{i}$ and penalty $p_{i}$.

For the rest of the proof, we denote by $n$ the number of nodes of the tree
decomposition $\mathcal{T}$ provided on input. We start by preprocessing the
graph using Theorem 5.2 and Lemma 13. We obtain a tree decomposition
$\mathcal{T}^{\prime}$ of the input graph of width $4\mathrm{tw}+3$ and height
$H$ where $H\in\mathcal{O}(\mathrm{tw}\cdot\log n)$. For every pair of
vertices $u,v$ which appear together in some bag of $\mathcal{T}^{\prime}$ we
have an edge with length at most their shortest-path distance. We define the
_height_ of a node of $\mathcal{T}^{\prime}$ inductively where the height of a
leaf node is $1$ and the height of any inner node is $1$ plus the maximum of
the heights of its children. Under this definition the root node has height
$H$ and all other bags have height less than $H$. We may refer to a height of
a bag by which we mean the height of the node corresponding to the bag.

We set
$\delta=\frac{\varepsilon}{2H}=\Omega\big{(}\frac{\varepsilon}{\mathrm{tw}\cdot\log
n}\big{)}$. Observe that this choice of $\delta$ gives for all $h\leq H$ that
$(1+\delta)^{h}\leq\left(1+\frac{\varepsilon}{2H}\right)^{H}\leq
e^{\varepsilon/2}\leq 1+\varepsilon$ for sufficiently small $\varepsilon$ (it
suffices to assume without loss of generality that $\varepsilon<\frac{1}{4}$).
The goal is to return a feasible solution of cost $(1+\varepsilon)^{2}\varrho$
if a feasible solution of cost $\varrho$ exists by producing a
$\delta$-labelling and invoking Lemma 12. The approximation ratio can then be
reduced to $1+\varepsilon$ by adjusting $\varepsilon$ appropriately.

We now present the dynamic programming procedure. It only differs from the
algorithm in Theorem 5.1 by considering $\delta$-labelling functions instead
of distance labelling functions and $\varepsilon$-satisfiability instead of
satisfiability.

  * •

Leaf node. For a leaf node $\ell$ we have $V_{\ell}=\emptyset$. Thus the only
true entry is $D^{\delta}_{\ell}[\mathrm{dl},\emptyset,0,0]$ where the domain
of $\mathrm{dl}$ is an empty set.

  * •

Introduce node. Let $i$ be an introduce node with a child node $j$, then
$X_{i}=X_{j}\cup\\{u\\}$ where $u\not\in X_{j}$. Let
$D^{\delta}_{j}[\mathrm{dl}^{\prime}_{\delta},S^{\prime},k_{j},p_{j}]$ be an
entry of the table of the child node $j$ with value $1$. We construct a
$\delta$-labelling function $\mathrm{dl}_{\delta}$ which agrees with
$\mathrm{dl}^{\prime}_{\delta}$ on $X_{j}$ and tries all possible values for
$u$. In particular the constructed $\delta$-labelling functions set
$\mathrm{dl}_{\delta}(u)$ to values $\Sigma_{\varrho}\setminus\\{0\\}$ and
additionally we try the label $0$ for $u$ if $u$ is a supplier. For such a
$\delta$-labelling function $\mathrm{dl}_{\delta}$ we compute $S$ to be the
set of satisfied vertices of $X_{i}$ as follows. We add the entire set
$S^{\prime}$ to $S$. We add $u$ to $S$ if there exists a neighbor $v\in N(u)$
so that
$\mathrm{dl}_{\delta}(u)\geq\mathrm{dl}_{\delta}(v)+\frac{d(u,v)}{1+\varepsilon}$.
Finally, we add neighbors $w\in N(u)$ to $S$ for which it holds that
$\mathrm{dl}_{\delta}(w)\geq\mathrm{dl}_{\delta}(u)+\frac{d(u,w)}{1+\varepsilon}$.
If $\mathrm{dl}_{\delta}(u)=0$ and $k_{j}\leq k-1$, then we set the entry
$D^{\delta}_{i}[\mathrm{dl}_{\delta},S,k_{j}+1,p_{j}]$ to $1$. If
$\mathrm{dl}_{\delta}(u)\in\Sigma_{\varrho}\setminus\\{0,\infty\\}$, then we
set the entry $D^{\delta}_{i}[\mathrm{dl}_{\delta},S,k_{j},p_{j}]$ to $1$. If
$\mathrm{dl}_{\delta}(u)=\infty$, $u\in V_{C}$, and $p_{j}\leq p-1$, then we
set the entry $D^{\delta}_{i}[\mathrm{dl}_{\delta},S,k_{j},p_{j}+1]$ to $1$.
If $\mathrm{dl}_{\delta}(u)=\infty$ and $u\in V_{S}$, then we set the entry
$D^{\delta}_{i}[\mathrm{dl}_{\delta},S,k_{j},p_{j}]$ to $1$.

  * •

Forget node. Let $i$ be a forget node where $X_{i}=X_{j}\setminus\\{u\\}$ and
$u\in X_{j}$. For any $\delta$-labelling function $\mathrm{dl}_{\delta}$ of
$X_{i}$ we denote by $L_{c}(\mathrm{dl}_{\delta})$ the set of functions which
extend $\mathrm{dl}_{\delta}$ by assigning labels
$\Sigma_{\varrho}\setminus\\{0,\infty\\}$ to $u$, by
$L_{s}(\mathrm{dl}_{\delta})$ the set of functions which extend
$\mathrm{dl}_{\delta}$ by assigning labels $\Sigma_{\varrho}$ to $u$, and by
$L_{\infty}(\mathrm{dl}_{\delta})$ the extension of $\mathrm{dl}_{\delta}$
which assigns label $\infty$ to $u$. Let $S$ be any subset of clients of
$X_{i}$, $k_{i}\in\\{0,\ldots,k\\}$, and $p_{i}\in\\{0,\ldots,p\\}$. If $u$ is
a supplier, then we set

$D^{\delta}_{i}[\mathrm{dl}_{\delta},S,k_{i},p_{i}]=\bigvee_{\mathrm{dl}^{\prime}_{\delta}\in
L_{s}(\mathrm{dl}_{\delta})}D^{\delta}_{j}[\mathrm{dl}^{\prime}_{\delta},S,k_{i},p_{i}].$
(14)

If $u$ is a client, then we set

$\begin{split}D^{\delta}_{i}[\mathrm{dl}_{\delta},S,k_{i},p_{i}]=&\left(\bigvee_{\mathrm{dl}^{\prime}_{\delta}\in
L_{c}(\mathrm{dl}_{\delta})}D^{\delta}_{j}[\mathrm{dl}^{\prime}_{\delta},S\cup\\{u\\},k_{i},p_{i}]\right)\vee\\\
&\vee
D^{\delta}_{j}[L_{\infty}(\mathrm{dl}_{\delta}),S,k_{i},p_{i}].\end{split}$
(15)

  * •

Join node. Let $i$ be a join node with children $j_{1}$ and $j_{2}$ where
$X_{i}=X_{j_{1}}=X_{j_{2}}$. Let $\mathrm{dl}_{\delta}$ be a
$\delta$-labelling function on $X_{i}$. Then for each pair of true entries
$D^{\delta}_{j_{1}}[\mathrm{dl}_{\delta},S_{1},k_{1},p_{1}]$ and
$D^{\delta}_{j_{2}}[\mathrm{dl}_{\delta},S_{2},k_{2},p_{2}]$ we set to $1$ the
entry

$D_{i}\left[\mathrm{dl}_{\delta},S_{1}\cup
S_{2},k_{1}+k_{2}-\lvert\mathrm{dl}_{\delta}^{-1}(0)\rvert,p_{1}+p_{2}-\lvert\mathrm{dl}_{\delta}^{-1}(\infty)\cap
V_{C}\rvert\right].$ (16)

To establish correctness of the algorithm, there are two tasks we need to
accomplish. First, we need to show that for any bag $X_{i}$ we have
$D^{\delta}_{i}[\mathrm{dl}_{\delta},S,k_{i},p_{i}]=1$ if and only if there
exists a $\delta$-labelling of $G[V_{t}]$ which agrees with
$\mathrm{dl}_{\delta}$ on $X_{i}$, satisfies clients $((V_{i}\setminus
X_{i})\cup S)\cap V_{C}$ aside from those clients with label $\infty$, and has
cost $k_{i}$ and penalty $p_{i}$. The proof of this equivalence is done
similarly to the proof of correctness of Theorem 5.1. The only difference is
that we need to consider $\delta$-labelling functions and
$\varepsilon$-satisfiability instead of distance labelling and satisfiability
respectively. Hence we omit this part of the proof. Using Lemma 12, we obtain
a solution to the input kSwO instance of cost $(1+\varepsilon)^{2}\varrho$.

It is more interesting to prove the following statement: we would like to show
that if there exists a solution of cost $\varrho$, then there exists a
$\delta$-labelling which is going to be found by the algorithm. The main
difficulty of proving this statement is that the converse of Lemma 12 does not
hold for any choice of $\delta$. In the remainder suppose there exists a
distance labelling $\mathrm{dl}\colon
V\to\\{0,\ldots,\varrho\\}\cup\\{\infty\\}$ which encodes a solution to the
instance as in the proof of Lemma 11.

Let $X_{i}$ be a bag of the decomposition of height $h$ and $S$ the vertices
of $V_{i}$ satisfied by $\mathrm{dl}$ including suppliers. We are going to
show that there always exists $\mathrm{dl}_{\delta}\colon
X_{i}\to\Sigma_{\varrho}$, $S_{\delta}\supseteq S$ and values $k_{i}$ and
$p_{i}$ such that
$D^{\delta}_{i}[\mathrm{dl}_{\delta},S_{\delta},k_{i},p_{i}]=1$,
$k_{i}\leq\lvert\mathrm{dl}^{-1}(0)\rvert$,
$p_{i}\leq\lvert\mathrm{dl}^{-1}(\infty)\cap V_{C}\rvert$ and for all $u\in
X_{i}$ we have
$\mathrm{dl}_{\delta}(u)\in\left[\frac{\mathrm{dl}(u)}{(1+\delta)^{h}},(1+\delta)^{h}\mathrm{dl}(u)\right]$.

We prove this claim by induction on the height of a bag. This property
trivially holds for empty leaf bags in the base case. For the induction step,
consider a node at height $h+1$. In the case of forget and join bags, if we
assume that the desired property holds for their children, then it follows
that it holds for them as well since
$\mathrm{dl}_{\delta}(u)\in\left[\frac{\mathrm{dl}(u)}{(1+\delta)^{h}},(1+\delta)^{h}\mathrm{dl}(u)\right]$
implies
$\mathrm{dl}_{\delta}(u)\in\left[\frac{\mathrm{dl}(u)}{(1+\delta)^{h+1}},(1+\delta)^{h+1}\mathrm{dl}(u)\right]$.

It remains to prove the property for introduce nodes. Let $i$ be an introduce
node with child $j$ where $X_{i}=X_{j}\cup\\{u\\}$, $u\not\in X_{j}$. We
cannot use the approach for proving the desired property we used for join and
forget nodes. For the introduced vertex $u$ the induction hypothesis
$\mathrm{dl}_{\delta}(u)\in\left[\frac{\mathrm{dl}(u)}{(1+\delta)^{h}},(1+\delta)^{h}\mathrm{dl}(u)\right]$
does not apply when $\mathrm{dl}(u)$ is finite since $u\not\in V_{j}$. Let
$S\subseteq X_{i}$ be the set of vertices (including suppliers) satisfied by
$\mathrm{dl}$ in $V_{i}$ and similarly let $S^{\prime}\subseteq X_{j}$ be the
set of satisfied vertices in $V_{j}$. We claim that at least one of the
following must be true:

###### Case 1

$\mathrm{dl}(u)=0$.

###### Case 2

$S=S^{\prime}\cup\\{u\\}$.

###### Case 3

$u\not\in S$ and $\mathrm{dl}(u)<\infty$.

###### Case 4

$\mathrm{dl}(u)=\infty$.

Suppose for contradiction that $\mathrm{dl}(u)\in\\{1,\ldots,\varrho\\}$ and
$S\supseteq S^{\prime}\cup\\{u,v_{1}\\}$ where $v_{1}\in X_{i}\setminus
S^{\prime}$. If $v_{1}$ is satisfied in $X_{i}$ but not in $X_{j}$, then the
sole cause of this fact is that $v_{1}$ is satisfied by $u$ as the labels of
its neighbors aside from $u$ remain the same between $X_{i}\cap N(v_{1})$ and
$X_{j}\cap N(v_{1})$. Thus we have
$\mathrm{dl}(v_{1})\geq\mathrm{dl}(u)+d(v_{1},u)$. Since $u$ is a satisfied
vertex and $\mathrm{dl}(u)\in\\{1,\ldots,\varrho\\}$, there exists a vertex
$v_{2}\in X_{j}$ such that $\mathrm{dl}(u)\geq\mathrm{dl}(v_{2})+d(u,v_{2})$.
Together we have
$\mathrm{dl}(v_{1})\geq\mathrm{dl}(v_{2})+d(v_{2},u)+d(u,v_{1})\geq\mathrm{dl}(v_{2})+d(v_{1},v_{2})$
where the last inequality holds from the preprocessing using Lemma 13.
However, the last inequality shows that $v_{1}\in S^{\prime}$ which is a
contradiction.

We therefore need to establish that for each of the four cases above, the
algorithm produces an entry
$D^{\delta}_{i}[\mathrm{dl}_{\delta},S_{\delta},k_{i},p_{i}]$ with $S\subseteq
S_{\delta}$, $k_{i}\leq\lvert\mathrm{dl}^{-1}(0)\cap V_{i}\rvert$,
$p_{i}\leq\lvert\mathrm{dl}^{-1}(\infty)\cap V_{i}\cap V_{C}\rvert$, and
$\mathrm{dl}_{\delta}(u)$ which is at most a factor $(1+\delta)^{h}$ apart
from $\mathrm{dl}(u)$. Assume by the induction hypothesis that there exists an
entry
$D^{\delta}_{j}[\mathrm{dl}_{\delta}^{\prime},S_{\delta}^{\prime},k_{j},p_{j}]$
with value $1$ for some $S_{\delta}^{\prime}\supseteq S^{\prime}$,
$k_{j}\leq\lvert\mathrm{dl}^{-1}(0)\cap V_{j}\rvert$,
$p_{j}\leq\lvert\mathrm{dl}^{-1}(\infty)\cap V_{j}\cap V_{C}\rvert$ and
$\mathrm{dl}_{\delta}^{\prime}$ which has $(\forall v\in
X_{j})\left(\mathrm{dl}_{\delta}^{\prime}(v)\in\left[\frac{\mathrm{dl}(v)}{(1+\delta)^{h-1}},(1+\delta)^{h-1}\mathrm{dl}(v)\right]\right)$.

  * Case 1

If $\mathrm{dl}(u)=0$, the algorithm considers a $\delta$-labelling function
$\mathrm{dl}_{\delta}$ which agrees with $\mathrm{dl}_{\delta}^{\prime}$ on
$X_{j}$ and sets $\mathrm{dl}_{\delta}(u)=0$. Since the entry
$D^{\delta}_{j}[\mathrm{dl}_{\delta}^{\prime},S_{\delta}^{\prime},k_{j},p_{j}]$
has value $1$, the algorithm sets the entry
$D^{\delta}_{i}[\mathrm{dl}_{\delta},S_{\delta},k_{j}+1,p_{j}]$ to $1$ for
some $S_{\delta}$. We claim that $S\subseteq S_{\delta}$. To see this, let
$v\in S\setminus S^{\prime}$. Then $v$ must be satisfied by $u$ and we have
$\mathrm{dl}(v)\geq\mathrm{dl}(u)+d(u,v)$. From the induction hypothesis,
$\mathrm{dl}(u)=0$, and $(1+\delta)^{h-1}\leq 1+\varepsilon$, we have
$\mathrm{dl}_{\delta}(v)\geq\frac{\mathrm{dl}(v)}{(1+\delta)^{h-1}}\geq\frac{d(u,v)}{1+\varepsilon}$.
This shows that every vertex $v\in S\setminus S^{\prime}$ is satisfied in
$X_{i}$.

  * Case 2

Assume that $\mathrm{dl}(u)\not\in\\{0,\infty\\}$ and $u\in S$. Then there
must exist a vertex $v$ which satisfies $u$, that is
$\mathrm{dl}(u)\geq\mathrm{dl}(v)+d(u,v)$. Let
$r=(1+\delta)^{h-1}\mathrm{dl}(u)$. The algorithm considers a
$\delta$-labelling function $\mathrm{dl}_{\delta}$ which agrees with
$\mathrm{dl}_{\delta}^{\prime}$ on $X_{j}$ and sets
$\mathrm{dl}_{\delta}(u)=(1+\delta)^{\lceil\log_{1+\delta}r\rceil}$. Using
$(1+\delta)^{h-1}\leq 1+\varepsilon$ we have
$\mathrm{dl}_{\delta}(u)\geq(1+\delta)^{h-1}\mathrm{dl}(u)\geq(1+\delta)^{h-1}(\mathrm{dl}(v)+d(u,v))\geq\mathrm{dl}_{\delta}(v)+\frac{d(u,v)}{1+\varepsilon}$.
Hence the algorithm correctly adds $u$ to $S_{\delta}^{\prime}$ to obtain
$S_{\delta}\supseteq S$. Moreover we have the required upper bound as well
since

$\mathrm{dl}_{\delta}(u)=(1+\delta)^{\lceil\log_{1+\delta}r\rceil}\leq(1+\delta)^{\log_{1+\delta}((1+\delta)^{h-1}\mathrm{dl}(u))+1}\leq(1+\delta)^{h}\mathrm{dl}(u).$
(17)

  * Case 3

Consider the case when $S\setminus S^{\prime}\neq\emptyset$, otherwise there
is nothing to prove. Let $v\in S\setminus S^{\prime}$, then $v$ must be
satisfied by $u$, that is $\mathrm{dl}(v)\geq\mathrm{dl}(u)+d(u,v)$. Let
$r=\frac{\mathrm{dl}(u)}{(1+\delta)^{h}}$. The algorithm considers a
$\delta$-labelling function $\mathrm{dl}_{\delta}$ which agrees with
$\mathrm{dl}_{\delta}^{\prime}$ on $X_{j}$ and sets
$\mathrm{dl}_{\delta}(u)=(1+\delta)^{\lceil\log_{1+\delta}r\rceil}$. Using the
induction hypothesis and $(1+\delta)^{h-1}\leq 1+\varepsilon$, we have

$\mathrm{dl}_{\delta}(v)\geq\frac{\mathrm{dl}(v)}{(1+\delta)^{h-1}}\geq\frac{\mathrm{dl}(u)}{(1+\delta)^{h-1}}+\frac{d(u,v)}{1+\varepsilon}\geq\mathrm{dl}_{\delta}(u)+\frac{d(u,v)}{1+\varepsilon}.$
(18)

Hence the algorithm extends $S_{\delta}^{\prime}$ by adding all elements of
$S\setminus S^{\prime}$ to create the set $S_{\delta}$. Moreover we have the
required upper bound as well since

$\mathrm{dl}_{\delta}(u)=(1+\delta)^{\lceil\log_{1+\delta}r\rceil}\leq(1+\delta)^{\log_{1+\delta}\frac{\mathrm{dl}(u)}{(1+\delta)^{h}}+1}\leq\frac{\mathrm{dl}(u)}{(1+\delta)^{h-1}}.$
(19)

  * Case 4

The algorithm considers a $\delta$-labelling function $\mathrm{dl}_{\delta}$
which agrees with $\mathrm{dl}_{\delta}^{\prime}$ on $X_{j}$ and sets
$\mathrm{dl}_{\delta}(u)=\infty$. Since a vertex with label $\infty$ cannot
satisfy a neighbor by definition, we have $S_{\delta}=S_{\delta}^{\prime}$.
The desired bound on $\mathrm{dl}_{\delta}(u)$ for $u\in X_{i}$ follows
trivially.

We conclude that whenever a feasible solution of cost $\varrho$ exists to the
input instance, we are able to recover from the root bag of the dynamic
programming table a solution of cost $(1+\varepsilon)^{2}\varrho$ with at most
$k$ centers and at most $p$ outliers. In particular, there exists an entry in
the dynamic programming table of the root bag
$D_{r}[\mathrm{dl}_{\delta},X_{r}\cap V_{C},k_{r},p_{r}]$ where
$\mathrm{dl}_{\delta}$ is a $\delta$-labelling of $X_{r}$ where for all $u\in
X_{r}$ we have
$\mathrm{dl}_{\delta}(u)\leq(1+\delta)^{H}\mathrm{dl}(u)\leq(1+\varepsilon)\varrho$,
$k_{r}\leq k$ and $p_{r}\leq p$.

It remains to bound the running time of the algorithm. We have
$\lvert\Sigma_{\varrho}\rvert=\mathcal{O}(\log_{1+\delta}\varrho)=\mathcal{O}\left(\frac{\log\varrho}{\log(1+\delta)}\right)=\mathcal{O}\left(\frac{\log\varrho}{\delta}\right)$
where we use the fact that $\ln(1+\delta)\approx\delta$ for sufficiently small
$\delta$ (that is, sufficiently large $n$). By setting
$\delta=\Omega\left(\frac{\varepsilon}{\mathrm{tw}\cdot\log n}\right)$ and
assuming $k,p\leq\lvert V(G)\rvert$, we get a running time
$\mathcal{O}^{*}\left((\mathrm{tw}\cdot\frac{\log
n}{\varepsilon})^{\mathcal{O}(\mathrm{tw})}\right)$. Using Lemma 14, this is
an FPT algorithm with running time
$\mathcal{O}^{*}\left((\mathrm{tw}/\varepsilon)^{\mathcal{O}(\mathrm{tw})}\right)$.
∎

##  6 Open Problems

We conclude with the following open problems. The algorithms given by Theorems
1.2 and 1.3 have the number of outliers in the base of the exponent. Is it
possible to remove the outliers from the set of parameters? An improvement of
Theorem 1.1 would be to show that the hardness is preserved in the case of
planar graphs. It may be of interest that Planar Capacitated Dominating Set is
$\mathrm{W[1]}$-hard when parameterized by solution size [9]. Goyal and
Jaiswal [25] have shown that it is possible to 2-approximate CkC when the
parameter is only $k$, and that this result is tight. An improvement of
Theorem 1.1 would be to show that this lower bound is tight in low highway
dimension graphs. Finally, we ask whether there exists a problem which admits
an EPAS in low highway dimension graphs but we cannot approximate in low
doubling dimension graphs, i.e. the converse of Theorems 1.1 and 1.2.

## References

  * [1] Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway Dimension and Provably Efficient Shortest Path Algorithms. Journal of the ACM (JACM) 63(5), 41:1–41:26 (2016)
  * [2] Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.F.: Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. In: Charikar, M. (ed.) Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010. pp. 782–793. SIAM (2010)
  * [3] Ahmadi-Javid, A., Seyedi, P., Syam, S.S.: A survey of healthcare facility location. Computers & Operations Research 79, 223–263 (2017)
  * [4] An, H., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., Svensson, O.: Centrality of trees for capacitated k-center. Mathematical Programming 154(1-2), 29–53 (2015)
  * [5] Bast, H., Funke, S., Matijevic, D.: Transit ultrafast shortest-path queries with linear-time preprocessing. 9th DIMACS Implementation Challenge (2006)
  * [6] Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In Transit to Constant Time Shortest-Path Queries in Road Networks. In: Proceedings of the Nine Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, Louisiana, USA, January 6, 2007. SIAM (2007)
  * [7] Becker, A., Klein, P.N., Saulpic, D.: Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland. LIPIcs, vol. 112, pp. 8:1–8:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
  * [8] Blum, J.: Hierarchy of Transportation Network Parameters and Hardness Results. In: Jansen, B.M.P., Telle, J.A. (eds.) 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany. LIPIcs, vol. 148, pp. 4:1–4:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
  * [9] Bodlaender, H.L., Lokshtanov, D., Penninkx, E.: Planar Capacitated Dominating Set Is _W_[1]-Hard. In: Chen, J., Fomin, F.V. (eds.) Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers. Lecture Notes in Computer Science, vol. 5917, pp. 50–60. Springer (2009)
  * [10] Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The Non-Uniform _k_ -Center Problem. ACM Trans. Algorithms 16(4), 46:1–46:19 (2020)
  * [11] Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Kosaraju, S.R. (ed.) Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA. pp. 642–651. ACM/SIAM (2001)
  * [12] Chatterjee, K., Ibsen-Jensen, R., Pavlogiannis, A.: Optimal tree-decomposition balancing and reachability on low treewidth graphs. https://research-explorer.app.ist.ac.at/record/5427 (2014), accessed: 2021-05-13
  * [13] Cohen-Addad, V., Feldmann, A.E., Saulpic, D.: Near-linear Time Approximation Schemes for Clustering in Doubling Metrics. J. ACM 68(6), 44:1–44:34 (2021)
  * [14] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)
  * [15] Cygan, M., Hajiaghayi, M., Khuller, S.: LP Rounding for k-Centers with Non-uniform Hard Capacities . In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012. pp. 273–282. IEEE Computer Society (2012)
  * [16] Cygan, M., Kociumaka, T.: Constant Factor Approximation for Capacitated k-Center with Outliers . In: Mayr, E.W., Portier, N. (eds.) 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France. LIPIcs, vol. 25, pp. 251–262. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
  * [17] Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated Domination and Covering: A Parameterized Perspective. In: Grohe, M., Niedermeier, R. (eds.) Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5018, pp. 78–90. Springer (2008)
  * [18] Edmonds, J., Karp, R.M.: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM 19(2), 248–264 (1972)
  * [19] Feder, T., Greene, D.H.: Optimal Algorithms for Approximate Clustering. In: Simon, J. (ed.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA. pp. 434–444. ACM (1988)
  * [20] Feldmann, A.E.: Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs. Algorithmica 81(3), 1031–1052 (2019)
  * [21] Feldmann, A.E., Fung, W.S., Könemann, J., Post, I.: A (1+$\epsilon$)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. SIAM J. Comput. 47(4), 1667–1704 (2018)
  * [22] Feldmann, A.E., Karthik C. S., Lee, E., Manurangsi, P.: A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms 13(6), 146 (2020)
  * [23] Feldmann, A.E., Marx, D.: The Parameterized Hardness of the k-Center Problem in Transportation Networks. Algorithmica 82(7), 1989–2005 (2020)
  * [24] Feldmann, A.E., Saulpic, D.: Polynomial time approximation schemes for clustering in low highway dimension graphs. J. Comput. Syst. Sci. 122, 72–93 (2021)
  * [25] Goyal, D., Jaiswal, R.: Tight FPT Approximation for Constrained k-Center and k-Supplier (2021), https://arxiv.org/abs/2110.14242
  * [26] Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded Geometries, Fractals, and Low-Distortion Embeddings. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings. pp. 534–543. IEEE Computer Society (2003)
  * [27] Harris, D.G., Pensyl, T.W., Srinivasan, A., Trinh, K.: A Lottery Model for Center-Type Problems With Outliers . ACM Trans. Algorithms 15(3), 36:1–36:25 (2019)
  * [28] Hochbaum, D.S., Shmoys, D.B.: A Best Possible Heuristic for the _k_ -Center Problem. Math. Oper. Res. 10(2), 180–184 (1985)
  * [29] Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3), 533–550 (1986)
  * [30] Katsikarelis, I., Lampis, M., Paschos, V.T.: Structural parameters, tight bounds, and approximation for (k, r)-center. Discret. Appl. Math. 264, 90–117 (2019)
  * [31] Lampis, M.: Parameterized Approximation Schemes Using Graph Widths. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. Lecture Notes in Computer Science, vol. 8572, pp. 775–786. Springer (2014)
  * [32] Talwar, K.: Bypassing the Embedding: Algorithms for Low Dimensional Metrics. In: Babai, L. (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. pp. 281–290. ACM (2004)
  * [33] Vazirani, V.V.: Approximation algorithms. Springer (2001)
  * [34] Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press (2011)