# A Subquadratic Time Algorithm for the Weighted $k$-Center Problem on Cactus
Graphs

Binay Bhattacharya  Simon Fraser University, Burnaby, Canada  Sandip Das
Indian Statisitical Institute, Kolkata, India  Subhadeep Ranjan Dev  Indian
Statisitical Institute, Kolkata, India

###### Abstract

The weighted $k$-center problem in graphs is a classical facility location
problem where we place $k$ centers on the graph, which minimize the maximum
weighted distance of a vertex to its nearest center. We study this problem
when the underlying graph is a cactus with $n$ vertices and present an
$O(n\log^{2}n)$ time algorithm for the same. This time complexity improves
upon the $O(n^{2})$ time algorithm by Ben-Moshe et al. [2], which is the
current state-of-the-art.

##  1 Introduction

The facility location problem is a classical problem in operations research
which has been well studied in both the graph and geometry settings. In graph,
the vertices have some kind of demand, and the edges have some associated
length. The length on the edges correspond to the distance between its two end
vertices. The objective is to identify a certain number of locations on the
edges and vertices of the graph where we can place facilities. The facilities
are placed such that they satisfy the demands on the vertices of the graph and
also minimize a certain predefined objective function.

In the _weighted $k$-center problem_ the objective is to place $k$ facilities
which minimize the maximum weighted distance between a vertex and its nearest
facility. Kariv and Hakimi [12] introduced this problem in 1979 and showed it
to be NP-hard for general graphs. In fact, they proved a much stronger
statement where they showed that the problem is NP-hard on planar graphs of
maximum degree 3. However, the problem is shown to have efficient polynomial
runtime when either the graph class is restricted or there is some bound on
$k$. For example, in trees, Wang and Zhang [13] recently showed that the
weighted $k$-center problem can be solved in $O(n\log n)$ time, where $n$ is
the number of vertices in the tree. If $k$ is a constant, Bhattacharya et al.
[3] presented an optimal $O(n)$ time solution for the problem on trees. For
cactus, the current state of the art is an $O(n^{2})$ time algorithm by Ben-
Moshe et al. [2]. When $k$ is restricted to be 1 or 2 then the runtime for
cactus comes down to $O(n\log n)$ and $O(n\log^{3}n)$ time respectively [4].
For partial $p$-trees, Bhattacharya and Shi [5] showed that the weighted
$k$-center problem can be solved in $O(n^{k}\log^{2p}n)$ time, when the
facilities are restricted to be placed only on the vertices.

The algorithm of Wang and Zhang [13] for the weighted $k$-center problem on
trees uses Frederickson’s parametric search technique [7] to bring down the
runtime from $O(n\log n+k\log^{2}n\log(n/k))$ [1] to $O(n\log n)$. We
generalize Frederickson’s technique to present an $O(n\log^{2}n)$ time
algorithm for the problem. This is the first time that such a generalization
could be achieved for a graph class other than trees and is the first
subquadratic time algorithm for the problem. The feasibility test is the
decision version of the problem where given a cost $\lambda$, the test returns
whether the optimal cost (not known) is at most $\lambda$ or not. We have also
proposed an algorithm for the feasibility test with respect to the weighted
$k$-center problem, which runs in optimal $O(n)$ time.

The rest of the paper is organized as follows. In Section 2, we provide a
formal definition of the weighted $k$-center problem and the tree
representation of a cactus. We present some results on circular arc graphs
which we use in the later sections. In Section 3, we present our algorithm for
the feasibility test. For any input $\lambda$, the test determines whether
$\lambda\geq\lambda^{*}$ or not, where $\lambda^{*}$ is the optimal cost of
the weighted $k$-center problem. In Section 4, we prove some properties on
linear arrangements whose results we use in Section 5. In Section 5, we define
a cactus stem which is basically a subgraph of the cactus and a generalization
of the (path) stem as defined in Frederickson [7]. We then present an
$O(n\log^{2}n)$ time algorithm to solve the weighted $k$-center problem on the
cactus stem. We also show another technique with which we can get an $O(n\log
n+kn\log n)$ time algorithm. In Section 6, we present our $O(n\log^{2}n+kn\log
n)$ time algorithm for cacti. Finally we conclude in Section 7.

##  2 Preliminaries

###  2.1 Problem definition

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$ with $|V(G)|=n$.
We say $G$ is a _cactus_ if no two cycles of $G$ share a common edge. Each
vertex $v\in V(G)$ is associated with a non-negative weight $w(v)$ and each
edge $e\in E(G)$ is associated with a positive length $l(e)$. We interpret $e$
as a line segment of length $l(e)$ so that any point $x$ on $e$ can be
referred to. The set of all points on all edges of $G$ is denoted by $A(G)$.
For any two points $x,y\in A(G)$, the distance between $x$ and $y$, denoted by
$d_{G}(x,y)$, is the length of the shortest path between them in $G$. We omit
the subscript $G$ if it is evident. For a point $x\in A(G)$ and a vertex $v\in
V(G)$, the _weighted distance_ between the point $x$ and the vertex $v$ is
equal to $w(v)\cdot d(x,v)$. Given a set of points $X$, the _cost_ of covering
the vertices of $G$ by $X$ is given by the expression

$\max_{v\in V(G)}\left\\{\min_{x\in X}\left\\{w(v)\cdot
d(x,v)\right\\}\right\\}$

The objective of the _weighted $k$-center_ problem in $G$ is to find a set of
$k$ points $X$ such that the cost of covering $V(G)$ is minimized. This cost
is also called the _optimal cost_ of the weighted $k$-center problem in $G$.

We say a point (or a center) $x\in A(G)$ _covers_ a vertex $v\in V(G)$ with
cost $\lambda,$ if $w(v)\cdot d(x,v)\leq\lambda$. Extending this definition we
say a set of centers $X$ covers $V(G)$ with cost $\lambda$ if for all vertices
$v\in V(G)$ its nearest center in $X$ covers $v$ with cost $\lambda$. We
sometimes do not explicitly mention $\lambda$ if it is well understood.

###  2.2 Tree representation of a cactus

Given a cactus $G$, a vertex of $G$ is a called a _graft_ if it does not
belong to any cycle of $G$. It is called a _hinge_ if it belongs to a cycle of
$G$ and has degree at least 3. Each of the remaining vertices, if any, belongs
to exactly one cycle of $G$.

We transform $G$ into a new graph $T$, where the nodes of $T$, $V(T)$,
represent either grafts, hinges or cycles of $G$. If a node $t_{i}\in V(T)$
represents a cycle of $G$ then we add an edge to every node $t_{j}\in V(T)$
which represents a hinge of that cycle. If $t_{i},t_{j}\in V(T)$ both do not
represent a cycle then they are adjacent if and only if the vertices of $G$
that they represent are adjacent.

Observe that two nodes of $V(T)$ representing a graft and a cycle of $G$,
respectively, are never adjacent. Since $G$ is a cactus, the graph $T$ thus
formed is a tree. We call $T$ the _tree representation_ of $G$ [2]. See Figure
1 for an illustration.

(a) A cactus $G$.  (b) Tree representation $T$ of $G$ rooted $t_{0}$. For all
$t\in V(T)$, the vertex $t$ represents is mentioned inside brackets.

Figure 1: The associate vertex of $t_{0}$ is $v_{0}$ and that of $t_{4}$ and
$t_{5}$ are both $v_{4}$.

Let $t_{r}\in V(T)$ be an arbitrary leaf node that we designate as the root of
$T$. This establishes a parent child relation on the nodes in $V(T)$. We now
map each node $t\in V(T)$ to a vertex $v\in V(G)$. We call $v$ the _associate
vertex_ of $t$.

For each $t_{i}\in V(T)$ which represents either a graft or a hinge $v_{i}\in
V(G)$, we assign $v_{i}$ as the associate vertex of $t_{i}$. For each
$t_{j}\in V(T)$ which represents a cycle of $G$, let $t_{j}^{\prime}$ be its
parent. Since $t_{j}$ represents a cycle, $t_{j}^{\prime}$ will always
represent a hinge of $G$. The associate vertex of $t_{j}$ is set as the
associate vertex of $t_{j}^{\prime}$. If $t_{j}$ represent a cycle of $G$ and
is also the root ($t_{j}=t_{r}$), we arbitrarily select a vertex of that cycle
and set it as the associate vertex of $t_{j}$. We call the the associate
vertex of $t_{r}$, say $v_{r}$, the root of $G$.

######  Lemma 1 (Ben-Moshe et al. [2]).

Given a cactus $G$ with $|V(G)|=n$, its tree representation $T$ can be found
out in $O(n)$ time.

###  2.3 Circular arcs

A _circular arc_ is the arc of a circle between a pair of distinct points. In
this section, we describe some operations on a set of circular arcs. Let $C$
be a set of $m$ circular arcs. We assume the midpoints of all arcs of $C$ to
be distinct and sorted in the clockwise direction. Let
$c_{1},c_{2},\ldots,c_{m}$ be the given sorted order of $C$. For $c_{i}\in
C,i<m$, $c_{i+1}$ is called the _clockwise neighbour_ of $C$. For $c_{m}$,
$c_{0}$ is its clockwise neighbour. The _counterclockwise neighbour_ is
defined analogously.

We say an arc $c\in C$ is a _super arc_ if there exists another arc
$c^{\prime}\in C$ which it completely contains, i.e. $c\supset c^{\prime}$. We
now prove the following.

######  Lemma 2.

All super arcs in $C$ can be removed in $O(m)$ time.

###### Proof.

Mark all arcs in $C$ as not visited. Arbitrarily select a pair of consecutive
arcs $a,b\in C$. Note that $b$ is the clockwise neighbor of $a$. While $a$ is
not marked visited we repeat the following steps.

If $a$ is contained in $b$, replace $b$ by its clockwise neighbor and remove
old $b$ from $C$. Else, mark $a$ as visited and update both $a$ and $b$ to
their respective clockwise neighbors.

Repeat the entire process once more in the counterclockwise direction.

The above steps remove all super arcs in $C$. Since, all arcs in $C$ are
traversed once in the clockwise direction and once in the counterclockwise
direction, the algorithm takes $O(m)$ time. ∎∎

The pseudocode for the algorithm of Lemma 2 is presented as Algorithm 1.

Algorithm 1 Remove Super Arcs

1:Mark all arcs in $C$ as unvisited

2:Let $a\in C$

3:Set $b\leftarrow$ the clockwise neighbor of $a$

4:while $a$ has not be marked visited do

5: if $a\subset b$ then

6: Set $b^{\prime}\leftarrow$ the clockwise neighbor of $b$

7: Remove $b$ from $C$

8: Set $b\leftarrow b^{\prime}$

9: else

10: Mark $a$ as visited

11: Set $a\leftarrow b$

12: Set $b\leftarrow$ the clockwise neighbor of $b$

13: end if

14:end while

15:Repeat the entire process once more in the counterclockwise direction

A set of circular arcs is called _proper_ if it does not contain any super
arcs. For the remaining part of this section, we consider $C$ to be a set of
proper circular arcs. The _minimum piercing set_ $\chi$ of $C$ is a set of
points of minimum cardinality such that each arc of $C$ contains some point of
$\chi$. The cardinality of $\chi$ is called the _piercing number_ of $C$. Hsu
et al. [11] showed that the maximum independent set of a set of $m$ circular
arcs can be found in $O(m)$ time. The same technique can be used to show the
following result.

######  Lemma 3 (Hsu et al. [11]).

The piercing set of $C$ can be found in linear time when the midpoint of the
arcs in $C$ are given in sorted order.

Each arc $c\in C$ has two endpoints. Starting from the interior of $c$, the
endpoint encountered first in a clockwise traversal is the _clockwise
endpoint_ of $c$. The other endpoint is the _counterclockwise endpoint_ of
$c$. The _clockwise next_ of $c$ is the arc $c^{\prime}$ which is encountered
first in a clockwise traversal starting at the clockwise endpoint of $c$ and
which does not intersect $c$. We similarly define the _counterclockwise next_
of $c$. See Figure 2 for reference.

Figure 2: For the circular arc $c_{1}$, its clockwise neighbour is $c_{2}$,
its clockwise next is $c_{3}$ and for say $q=3$ its clockwise $q$-next is
$c_{8}$.

Since the endpoints of $C$ are given to us in sorted order, we make the
following claim.

######  Lemma 4.

The clockwise (counterclockwise) next of all arcs in $C$ can be found in
$O(m)$ time.

###### Proof.

Mark all arcs in $C$ as visited. Arbitrarily select an arc $a\in C$ and set
$b\leftarrow a$. While $a$ is not marked visited repeat the following.

If $a$ intersect $b$, update $b$ to its clockwise neighbour. Else, mark $a$ as
visited and set $b$ as the clockwise neighbour of $a$. Update $a$ to its
clockwise neighbour.

The above steps set the clockwise next for all arcs in $C$ in $O(m)$ time. The
counterclockwise next of all arcs can be found similarly. ∎∎

The pseudocode for the algorithm of Lemma 4 is presented as Algorithm 2. The
algorithm to find all counterclockwise nexts of the arcs of $C$ is similar.

Algorithm 2 Clockwise Next

1:Mark all arc in $C$ as not visited

2:Let $a\in C$

3:Set $b\leftarrow a$

4:while $a$ is not marked visited do

5: if $a\cap b\neq\varnothing$ then

6: Set $b\leftarrow$ the clockwise neighbour of $b$

7: else

8: Set $b$ as the clockwise next of $a$

9: Mark $a$ as visited

10: Set $a\leftarrow$ the clockwise neighbour of $a$

11: end if

12:end while

For any positive integer $q$, let $[q]$ denote the set $\\{1,2,\ldots,q\\}$.
We now define the _clockwise $q$-next_ of an arc $c_{0}\in C$. Let
$c_{0},c_{1},\ldots,c_{q}$ be a sequence of circular arcs of $C$ such that for
any $i\in[q]$, $c_{i}$ is the clockwise next of $c_{i-1}$. The arc $c_{q}$
then is called the clockwise $q$-next of $c_{0}$. Note that, for any,
$i\in[q]$, the arc $c_{i}$ is the clockwise $i$-next of $c_{0}$. The
counterclockwise $q$-next of $c$ is defined similarly. See Figure 2 for
reference.

######  Lemma 5.

The clockwise (counterclockwise) $q$-next of all arcs of $C$ can be found in
$O(m)$ time.

###### Proof.

The pseudocode for Lemma 5 is presented as Algorithm 3. The algorithm uses the
compatibility forest data structure for intervals in Gavruskin et al. [10] by
extending it to circular arcs and appropriately naming it the compatibility
graph data structure.

Let $G_{C}$ represent the clockwise compatibility graph of $C$ which is a
graph with vertices for each arc of $C$ and an edge from $a$ to $b$, $a,b\in
C$, if $b$ is the clockwise next of $a$. The graph $G_{C}$ can be disconnected
with each connected component having exactly one directed cycle. Note that
there are also no other undirected cycle in that component.

A careful implementation of Algorithm 3 will result in an $O(m)$ time
algorithm. The algorithm for the counterclockwise case is similar. ∎∎

Algorithm 3 Clockwise $q$-Next

1:Initialize all arcs of $C$ as unvisited

2:for each connected component $G^{\prime}$ of $G$ do

3: Let $r$ be an arc on the directed cycle of $G^{\prime}$

4: Remove the edge connecting $r$ to its clockwise next to convert
$G^{\prime}$ into a tree $T^{\prime}$ rooted at $r$

5: Set $a\leftarrow r$

6: Initialize a dequeue $Q$ of size $q$ such that the $i^{\text{th}}$ element
in $Q$ is the clockwise $i$-next of $a$

7: while $r$ is not marked visited do

8: if $a$ has an unvisited child $b$ then

9: Update $Q$ by inserting $a$ as its first element and deleting its last
element

10: Set $a\leftarrow b$

11: else

12: Let $b$ be the last element in $Q$

13: Set $b$ as the clockwise $q$-next of $a$ and marking $a$ visited

14: Update $Q$ by removing its first element and inserting the clockwise next
of $b$ as its last element

15: Set $a\leftarrow$ the parent of $a$

16: end if

17: end while

18:end for

##  3 Feasibility Test

In this section, we present an algorithm which solves the decision version of
the weighted $k$-center problem in time linear in the size of the cactus. The
problem is commonly referred to as the _feasibility test_ in literature. Given
a cactus network $G$, let $\lambda^{*}\in\mathbb{R}_{\geq 0}$ be the optimal
cost of the weighted $k$-center problem in $G$. For an input
$\lambda\in\mathbb{R}_{\geq 0}$, the feasibility test asks whether
$\lambda\geq\lambda^{*}$, or not. Note that the optimal cost $\lambda^{*}$ is
an unknown value. If $\lambda\geq\lambda^{*}$, then we say $\lambda$ is
feasible, otherwise, $\lambda<\lambda^{*}$ and we say $\lambda$ is infeasible.

For a given $\lambda$, our algorithm works by placing a minimum number of
centers $X$, such that every vertex in $G$ is covered by some center in $X$
with cost $\lambda$. If $|X|\leq k$, then $\lambda$ is feasible; otherwise
$|X|>k$, and $\lambda$ is infeasible. The algorithm uses the tree
representation $T$ of $G$ in order to fix a processing order on the vertices
of $G$. Recall that $T$ is rooted at the node $t_{r}$. We process the nodes of
$T$ in a bottom-up order, visiting the leaves first, and then visiting the
nodes whose children have been processed.

Figure 3: The subgraphs $T_{t}$ and $G_{t}$. Vertex $v$ and $v_{1}$ in $V(G)$
are the associate of $t$ and $t_{1}$ in $V(T)$, respectively. Node $t_{1}$ is
a child of $t$, $t\in V(T)$ represents the cycle $H$ of $G$, and
$X_{t}=\\{x_{1},x_{2},x_{3}\\}$.

For $t\in V(T)$, let $T_{t}$ denote the subtree of $T$ rooted at $t$ and let
$G_{t}$ denote the subgraph of $G$ that $T_{t}$ represents. For each node
$t\in V(T)$, we store two values $\operatorname{close}(t)$ and
$\operatorname{cover}(t)$, defined as follows.

Consider an intermediate step in our feasibility test algorithm where all
vertices in $G_{t}$ have already been processed. The algorithm may have placed
some centers inside $G_{t}$. Let these centers be represented by the set
$X_{t}$. The _uncovered_ vertices of $G_{t}$ are those vertices which cannot
be covered by $X_{t}$ with cost $\lambda$.

Let $v_{t}\in V(G)$ be the associate vertex of $t\in V(T)$. The function
$\operatorname{cover}(t)$ represents the maximum distance that a center can be
placed outside $G_{t}$ from $t$, that covers all uncovered vertices of $G_{t}$
with cost $\lambda$. Let $V^{\prime}\subseteq V(G_{t})$ be the uncovered
vertices of $G_{t}$. We define $\operatorname{cover}(t)$ as follows.

$\displaystyle\operatorname{cover}(t)=\begin{cases}\min\left\\{\lambda/w(v)-d(v,v_{t})\mid\forall
v\in V^{\prime}\right\\}&\text{ if }V^{\prime}\neq\varnothing\\\ \infty&\text{
otherwise }\end{cases}$

The function $\operatorname{close}(t)$ stores the distance of the closest
center inside $G_{t}$ from $v_{t}$. We define $\operatorname{close}(v)$ as
follows.

$\displaystyle\operatorname{close}(t)=\begin{cases}\min\left\\{d(x,v_{t})\mid\forall
x\in X_{t}\right\\}&\text{ if }X_{t}\neq\varnothing\\\ \infty&\text{ otherwise
}\end{cases}$

Recall that we traverse the nodes of $T$ bottom-up. We also maintain a
variable $count$, which counts the number of centers placed till now. Let $t$
be the node of $T$ that we are currently at and let $v$ be its associate
vertex. In Section 3.1 and 3.2 we show how to place centers inside $G_{t}$
depending on whether $t$ represents a hinge/graft or a cycle of $G$.

###  3.1 $t$ represents a hinge or a graft of $G$

Let $V_{t}\subseteq V(T)$ be the set of children of $t$. For each $t_{i}\in
V_{t}$, let $v_{i}$ be its corresponding vertex.

Let $V_{1}\subseteq V_{t}$, be such that $\forall t_{i}\in V_{1}$,
$\operatorname{cover}(t_{i})<d(v_{i},v_{t})$. Observe that for all such
$t_{i}\in V_{1}$, its is necessary to place a center on the edge
$(v_{i},v_{t})$ in order to cover the remaining uncovered vertices in
$G_{t_{i}}$. We do so by placing a center on the edge $(v_{t},v_{i})$ at a
distance $\operatorname{cover}(t_{i})$ from $v_{i}$ and incrementing $count$
by one. Since all vertices in $T_{t_{i}}$ are now covered, we set
$\operatorname{cover}(t_{i})$ to $\infty$.

As per definition, we now set $\operatorname{close}(t)$ as the minimum of all
distances of all centers placed in $G_{t}$, from $v_{t}$. Let $x$ be such a
center i.e. $x$ is closest to $v_{t}$. If $G_{t}$ has no centers placed, we
set $\operatorname{close}(t)$ to $\infty$.

Now, let $V_{2}\subseteq V_{t}\setminus V_{1}$ be such that $\forall t_{j}\in
V_{2}$, $\operatorname{cover}(t_{j})\geq
d(v_{t},v_{j})+\operatorname{close}(t)$. Observe that for all such $t_{j}\in
V_{2}$, all vertices in $G_{t_{j}}$ are either covered by the centers placed
inside $G_{t_{j}}$ or by the center $x$, if it exists. Therefore, we set
$\operatorname{cover}(t_{j})$ as $\infty$.

Finally, we update $\operatorname{cover}(t)$. We define the parameter $\delta$
as

$\delta=\min\\{\operatorname{cover}(t_{i})-d(v_{t},v_{i})\mid\text{for all
child }t_{i}\text{ of }t\\}$

If $\operatorname{close}(t)\leq\frac{\lambda}{w(v_{t})}$ then we set
$\operatorname{cover}(t)=\delta$, otherwise
$\operatorname{cover}(t)=\min\\{\lambda/$ $w(v_{t}),\delta\\}$.

###  3.2 $t$ represents a cycle of $G$

Let $H$ be the cycle of $G$ that $t$ represents and let $m=|V(H)|$. For a
vertex $v_{j}\in V(H)$, let $\operatorname{near}(v_{j})$ be the distance of
the nearest center in $G_{t}$ to $v_{j}$. The definition of
$\operatorname{near}(\cdot)$ is similar to that of
$\operatorname{close}(\cdot)$. Where $\operatorname{close}(\cdot)$ is defined
on the nodes in $V(T)$, $\operatorname{near}(\cdot)$ instead is define on the
vertices of the cycles in $G$. Observe that the only information required to
compute $\operatorname{near}(v_{j}),\forall v_{j}\in V(H)$ is
$\operatorname{close}(t_{i}),\forall t_{i}\in V_{t}$. Therefore, it is not
difficult to show that $\forall v_{j}\in V(H),\operatorname{near}(v_{j})$ can
be computed in $O(m)$ time.

If $v_{j}\neq v_{t}$ then $v_{j}$ is uncovered if
$\operatorname{near}(v_{j})>\operatorname{cover}(t_{j})$, where $t_{j}\in
V(T)$ represents $v_{j}$. If $v_{j}=v_{t}$ or is not a hinge then $v_{j}$ is
uncovered if $\operatorname{near}(v_{j})>\lambda/w(v_{j})$. Our objective is
to cover all the uncovered vertices in $H$ by placing zero or more centers in
$H$ and at most one outside $G_{t}$.

We convert this problem of placing centers in $H$ to an equivalent piercing
set problem on a set of circular arcs $C$ as follows. For $i\in[m]$, if
$v_{i}$ is a hinge and if $v_{i}\neq v_{t}$, let $t_{i}\in V(T)$ be the node
that represents $v_{i}$. We set $l_{i}=2\times\operatorname{cover}(t_{i})$.
Otherwise, we set $l_{i}=2\lambda/w(v_{i})$. We insert into $C$ a circular arc
of length $l_{i}$ centered at $v_{i}$.

Our objective is to place a set of piercing points so that the overall number
of centers placed is minimum. Let $C^{\prime}\subseteq C$ be the subset of
circular arcs which do not intersect $v_{t}$. Let $q$ and $q^{\prime}$ be the
size of the minimum piercing set of $C$ and $C^{\prime}$, respective. Observe
that $q-1\leq q^{\prime}\leq q$. If $q^{\prime}=q-1$, then instead of placing
a center $x$ at $v_{t}$, it can be shifted outside $G_{t}$, within a
permissible distance.

We therefore find a set of piercing points $\chi$ such that either (a) all
uncovered vertices of $H$ are covered by $\chi$, and $\exists x\in\chi$ which
is placed as close as possible to $v_{t}$; (b) not all uncovered vertices of
$H$ are covered by $\chi$ and one more center $x$ is needed to be placed
outside $G_{t}$ to cover them. In the later case, the $\chi$ is selected such
that $x$ can be placed as far away as possible from $v_{t}$. If
$q^{\prime}=q$, then Case (a) follows, otherwise $q^{\prime}=q-1$ and Case (b)
follows. Given $H$ in cyclic order, we show how to compute the set $\chi$ in
$O(m)$ time.

Figure 4: The set $\chi(c_{1})$ for $q$/$q^{\prime}$ = 5.

####  3.2.1 Case (a)

In this case, we need to find a minimum piercing set $\chi$ of $C$ such that
one of the piercing points $x\in\chi$ is closest to $v_{t}$. We check for all
possible configurations of $\chi$ and chose the one with the closest point to
$v_{t}$. Let $c_{1}$ be the first arc in the clockwise direction from $v_{t}$
which does not overlap with it. Let $c_{j}$ be the clockwise next of $c_{1}$.
For each $c_{i}\in\\{c_{1},c_{2},\ldots,c_{j-1}\\}$, we construct a set of
piercing points $\chi(c_{j})$ as follows.

We place the first piercing point, $x_{1}$, at the counterclockwise endpoint
of $c_{i}$. We place the next piercing point, $x_{2}$, at the clockwise
endpoint of the clockwise neighbour of $c_{i}$, say $c_{i+i_{1}^{\prime}}$. We
place the next piercing point, $x_{3}$, at the clockwise endpoint of the
clockwise next of $c_{i+i_{1}^{\prime}}$, say $c_{i+i_{2}^{\prime}}$. We
continue placing points in this way and place the $q$-th piercing point
$x_{q}$ on the clockwise endpoint of the clockwise $(q-1)$-next of $c_{i}$,
say $c_{i+i_{q-1}^{\prime}}$. The set $\chi(c_{i})$ is a valid minimum
piercing set of $C$ if the clockwise next of $c_{i+i^{\prime}_{q-1}}$ overlaps
with $x_{1}$.

Note that for any $c_{i}\in\\{c_{1},c_{2},\ldots,c_{j-1}\\}$ the closest point
of $\chi(c_{i})$ to $v_{t}$ is either $x_{1}$ or $y_{q}$. Therefore, we are
happy with only computing the first and the $q$-th piercing point for each
$\chi(c_{i})$, which can be done in $O(1)$ time. We select $\chi$ as one of
the $\chi(c_{i})$ which is a valid piercing set and which has a point closest
to $v_{t}$. We compute each point in $\chi$ and place a center in $H$ at its
corresponding position. We increment $count$ by $q$ and update
$\operatorname{close}(t)$ and $\operatorname{cover}(t)$ accordingly.

####  3.2.2 Case (b)

In this case, we find a set of $q^{\prime}$ centers on $H$, such that the
center outside $G_{t}$, covering the remaining uncovered vertices in $G_{t}$
through $v_{t}$, can be as far away as possible from $v_{t}$. For each
$c_{i}\in\\{c_{1},c_{2},\ldots,c_{j-1}\\}$, we construct a set of piercing
points $\chi(c_{j})$ as shown earlier where $q$ is replaced by $q^{\prime}$.

As noted earlier, for any $c_{i}\in\\{c_{1},c_{2},\ldots,c_{j-1}\\}$ the
closest point of $\chi(c_{i})$ to $v_{t}$ is either $x_{1}$ or
$x_{q^{\prime}}$. Therefore, we are happy with only computing the first and
the $q^{\prime}$-th piercing point for each $\chi(c_{i})$, which can be done
in $O(1)$ time.

Let $c_{i-i^{\prime}_{0}}$ be the counterclockwise next of $c_{i}$ and
$c_{i+i^{\prime}_{q^{\prime}}}$ the clockwise next of
$c_{i+i^{\prime}_{q^{\prime}-1}}$ and let $v_{1}$ and $v_{2}$ be the vertices
of $H$ that they respectively represent. Let $V^{\prime}$ be the set of
centers in $G_{t}$ that are uncovered after placing the centers corresponding
to $\chi(c_{i})$. Then the distance of the farthest center from $v_{t}$ which
covers the remaining uncovered vertices of $G_{t}$ from outside is given by
$\min\\{\alpha(v_{1})-d(v_{1},v_{t}),\alpha(v_{2})-d(v_{2},v_{t})\\}$, where
$\alpha(v_{l})$ ($l=\\{1,2\\}$) is $\operatorname{cover}(v_{l})$, if $v_{l}$
is a hinge, and $\lambda/v_{l}$, otherwise. Let us denote this value as the
_cost_ of $\chi(c_{i})$.

We select $\chi$ as one of the $\chi(c_{i})$ which has the largest cost. We
compute each point in $\chi$ and place a center in $H$ at its corresponding
position. We increment $count$ by $q^{\prime}$ and update
$\operatorname{close}(t)$ and $\operatorname{cover}(t)$ accordingly. If
$t=t_{r}$, we place one more center at $v_{r}$ and increment $count$ by 1.

###  3.3 Time complexity

######  Theorem 1.

The feasibility test for the weighted $k$-center problem on cactus takes
$O(n)$ time, where $n$ is the number of vertices in the cactus.

###### Proof.

We traverse each node of $T$ only once. If the node $t$ represents either a
hinge or a graft, then the time required to process it is linear in the number
of children of $t$. Otherwise, $t$ represents a cycle, and we convert our
problem to a problem on circular arcs. This step is again linear in the number
of vertices in the cycle. Finally, finding $\chi,\operatorname{close}(t)$ and
$\operatorname{cover}(t)$ also take time linear in the number of vertices in
the cycle. Therefore, the running time of the entire algorithm is $O(n)$. ∎∎

##  4 Parametric Pruning on Paths

Let $L$ be a set of $m$ lines in $\mathbb{R}^{2}$ and let $I$ represent the
set of $n\choose 2$ pairwise intersection points of the lines in $L$. Consider
a feasibility test, similar to the one define in Section 3, which takes as
input a value $\gamma$ and returns _feasible_ if $\gamma\geq\gamma^{*}$, where
$\gamma^{*}$ is a predefined threshold. It returns _infeasible_ otherwise.

Let $p_{1}$ is the highest point in $I$ whose $y$-coordinate value is
infeasible and let $p_{2}$ be the lowest point in $I$ whose $y$-coordinate
value is feasible. We have the following result by Chen and Wang [6].

######  Lemma 6 (Chen and Wang [6]).

Given $L$, both $p_{1}$ and $p_{2}$ can be found in $O\left((m+\tau)\log
m\right)$, where $\tau$ is the running time of the feasibility test.

Let $P$ be a path of size $m$ with weights on its vertices and lengths on its
edges as shown in Section 1. For $u,v\in V(P)$, let $\operatorname{cost}(u,v)$
represent the cost of covering $u$ and $v$ by a single center in $A(P)$ and
let $\operatorname{l-cost}(u,v)$ represent the cost of covering $u$ by a
center placed at $v$. Let
$R_{0}(P)=\\{\operatorname{l-cost}(u,v)\mid\forall(u,v)\in V(P)\times
V(P)\\}$, $R_{1}(P)=\\{\operatorname{cost}(u,v)\mid\forall(u,v)\in V(P)\times
V(P)\\}$ and $R(P)=R_{0}(P)\cup R_{1}(P)$.

Let $v_{0}\in V(P)$ be the leftmost vertex of $P$. For each vertex $v_{i}\in
V(P)$, we place a point $q_{i}$ on the $x$-axis of an $xy$-coordinate system
at $x$-coordinate $d(v_{0},v_{i})$. We place for every vertex $v_{i}\in V(P)$,
three lines $l^{+}_{i},l^{-}_{i}$ and $l^{\infty}_{i}$, with slopes
$+w(v_{i}),-w(v_{i})$ and $\infty$ (vertical line), respectively, at point
$q_{i}$. Let $L_{P}=\left\\{l^{+}_{i},l^{-}_{i},l^{\infty}_{i}\mid\forall
v_{i}\in V(P)\right\\}$ and let $I_{P}$ represent the set of pairwise
intersection points of the lines in $L_{P}$.

Figure 5: Representing values of $R_{0}(P)\cup R_{2}(P)$ in $\mathbb{R}^{2}$.

Observe that all values in $R(P)$ are represented as the $y$-value of the
points in $I_{P}$. See Figure 5 for reference. Therefore, with respect to a
feasibility test with predefined threshold $\gamma^{*}$, we can use Lemma 6 to
find $\lambda_{1},\lambda_{2}\in\mathbb{R}_{\geq 0}$ such that
$\lambda_{1}<\gamma^{*}\leq\lambda_{2}$ and no value in $R(P)$ lies inside the
range $(\lambda_{1},\lambda_{2})$. The same result can be achieved if instead
of a single path we have multiple paths. Given multiple paths
$P_{1},P_{2},\ldots,P_{l}$ we concatenate the paths by joining their end
points sequentially to get a path $\hat{P}$. We can then perform the same
operations on this resultant path to get
$\lambda_{1},\lambda_{2}\in\mathbb{R}_{\geq 0}$ such that
$\lambda_{1}<\gamma^{*}\leq\lambda_{2}$ and
$\forall\lambda\in\bigcup_{i=1}^{l}R(P_{i}),\lambda\notin(\lambda_{1},\lambda_{2})$.
We therefore make the following claim.

######  Lemma 7.

Given a collection of path networks $P_{1},P_{2},\ldots,P_{l}$, and a
feasibility test with threshold $\gamma^{*}$, we can find $\lambda_{1}$ and
$\lambda_{2}$ in $O((m+\tau)\log m)$ where $m$ is the size of $\hat{P}$ and
$\tau$ is the running time of the feasibility test.

##  5 $k$-Center on Cactus Stems

In this section, we define a _cactus stem_ , which is a generalization of the
(path) stem defined by Frederickson [7] for trees and present two algorithm to
compute the weighted $k$-center on it. Let $S^{\prime}$ be a cactus whose tree
representation is a path $P^{\prime}$. Assume the nodes of $P^{\prime}$ to be
ordered from left to right.

The structure of $S^{\prime}$ is an alternating sequence of paths and cycles.
Let $P_{1},C_{1},P_{2},C_{2},\ldots,P_{m},C_{m}$ be the left to right ordering
of this sequence with respect to the left to right ordering of $P^{\prime}$,
where $P_{i}$ and $C_{j}$ represent a path and a cycle of $S^{\prime}$,
respectively. Note that the path $P_{1}$ and cycle $C_{m}$ may not exist.

We call a vertex a _pendant vertex_ if its degree is 1. Let $S$ be the graph
generated from $S^{\prime}$ by attaching any number of pendant vertices to the
vertices in $V(S^{\prime})$. We call $S$ a _cactus stem_. For this section we
assume $|V(S)|=n$.

Let $s$ and $t$ be the leftmost and rightmost nodes of $P^{\prime}$ and let
$g_{0}$ and $h_{0}$ be their respective associate vertices in $S^{\prime}$. We
call $g_{0}$ and $h_{0}$ the _leftmost_ and _rightmost_ vertices of $S$,
respectively. Let $g_{i}$ and $h_{i}$ represent the left and right hinges of a
cycle $C_{i}$ in $S$. If the left hinge of $C_{1}$ does not exist then we set
$g_{1}$ as $g_{0}$. Similarly, if the right hinge of cycle $C_{m}$ does not
exist we set $h_{m}$ as $h_{0}$.

The _minor hemisphere_ of $C_{i}$ is the shortest path between $g_{i}$ and
$h_{i}$ in $C_{i}$. The _major hemisphere_ of $C_{i}$ is the other path
between $g_{i}$ and $h_{i}$ in $C_{i}$. If both paths are of the same length,
then we arbitrarily select one of them as the major hemisphere and the other
as the minor hemisphere. See Figure 6.

Figure 6: A cactus stem.

A vertex $u\in V(S)$ is said to be to the _left_ of $C_{i}$ if no path between
$u$ and $g_{0}$ passes through $C_{i}$. Similarly, a vertex $v\in V(S)$ is
said to be to the _right_ of $C_{i}$ if no path between $v$ and $h_{0}$ passes
through $C_{i}$. Let $\hat{C}_{i}$ be the graph formed by attaching all
pendant vertices adjacent to $V(C_{i})$ to $C_{i}$. Observe that $u,v\notin
V(\hat{C}_{i})$.

Recall that $A(S)$ represents the set of all points on all edges of $S$. For
$x,y\in A(S)$, let $\pi_{xy}$ denote a shortest path between $x$ and $y$ in
$S$. For $u,v\in V(S)$, let $x\in A(S)$ be such that $w(u)\cdot
d(x,u)=w(v)\cdot d(x,v)$ and for any two shortest paths $\pi_{xu}$ and
$\pi_{xv}$ in $S$, $\pi_{xu}\cap\pi_{xv}=\varnothing$. For such a triple
$(u,v,x)$, we define $\operatorname{cost}(u,v,x)$ as the cost of covering $u$
and $v$ by a center placed at $x$ i.e. $\operatorname{cost}(u,v,x)=w(u)\cdot
d(x,u)=w(v)\cdot d(x,v)$. We define $R_{S}$ to be the set of all possible
values of $\operatorname{cost}(u,v,x)$.

Let $X^{*}\subset A(S)$ be a set of $k$ optimal centers of the cactus stem $S$
with respect to the weight $k$-center problem and let $\lambda^{*}$ be its
optimal cost. We have the following lemma.

######  Lemma 8.

There exists a triple $(u,v,x)$ such that
$\lambda^{*}=\operatorname{cost}(u,v,x)$.

###### Proof.

Since $\lambda^{*}$ is the optimal cost, their exists a center $x\in X^{*}$
that determines $\lambda^{*}$. Let $u\in V(S)$ be such that $w(u)\cdot
d(x,u)=\lambda^{*}$ and the closest center to $u$ in $X^{*}$ is $x$. Since $x$
determines $\lambda^{*}$, $u$ always exists. But that alone is not enough to
determine $\lambda^{*}$ since we can move $x$ towards $u$ and reduce the
weighted distance of $x$ to $u$. Therefore, there exists another vertex $v\in
V(S)$, such that $w(v)\cdot d(x,v)=\lambda^{*}$. Also, no path $\pi_{ux}$ and
$\pi_{vx}$ overlap, since again $x$ can be moved towards a particular
direction which reduces the weighted distance of $x$ to both $u$ and $v$. ∎∎

We call the set $R_{S}$ the set of _candidate values_ of $\lambda^{*}$. Based
on $u,v$ and $x$ the candidate values in $R_{S}$ can be divided into the
following types.

  * type 1: $x$ does not lie inside any cycle of $S$,

  * type 2: $x$ lies on the minor hemisphere of some cycle $C_{i}$ in $S$ and

    * (a): $u$ and $v$ both belong to $V(\hat{C}_{i})$,

    * (b): either $u$ or $v$ belongs to $V(C_{i})$, but not both,

    * (c): neither $u$ nor $v$ belong to $V(\hat{C}_{i})$.

  * type 3: $x$ lies on the major hemisphere of some cycle $C_{j}$ in $S$ and

    * (a): $u$ and $v$ both belong to $V(\hat{C}_{j})$,

    * (b): either $u$ or $v$ belongs to $V(\hat{C}_{j})$, but not both,

    * (c): neither $u$ nor $v$ belong to $V(\hat{C}_{j})$.

In addition to $R_{S}$, we define another set of costs $R_{S}^{\prime}$ as the
set $\\{\operatorname{l-cost}(u,v)\mid\forall(u,v)\in V(S)\times V(S)\\}$. In
the following sections we present our algorithm to compute the weighted
$k$-center of $S$. The algorithm works in two stages. In Stage 1, we look at
all types of candidate values in $R_{S}$ except type 3(c) as defined above. In
Stage 2, we check for all candidate values in $R_{S}$ of type 3(c).

###  5.1 Stage 1

For a cycle $C_{i}$ of $S$, let $A_{i}$ represent its minor hemisphere and
$B_{i}$ its major hemisphere. For a given cactus stem $S$, let $S^{\prime}$ be
the graph left after removing all pendant vertices of $S$. See Figure 7.

Figure 7: The graph $S^{\prime}$ assuming $S$ to be the graph represented in
Figure 6.

We convert $S^{\prime}$ into a tree $T_{S^{\prime}}$ by removing $B_{i}$ from
each cycle $C_{i}$ in $S^{\prime}$ and attaching a path to $g_{i}$ and $h_{i}$
as shown in Figure 8. Note that Figure 8 only shows the overall structure of
$T_{S^{\prime}}$ and some vertices are not depicted. The tree $T_{S}$ is
generated by attaching all pendant vertices of $S$ into their respective
locations in $T_{S^{\prime}}$. See Figure 9.

Figure 8: The structure of $T_{S^{\prime}}$. Figure 9: The tree $T_{S}$.

Based on the vertices in $T_{S}$ we generate points on $x$-axis of an
$xy$-coordinate system as follows. Fix two points $p_{0}$ and $q_{0}$ with
respect to $g_{0}$ and $h_{0}$ arbitrarily, such that $p_{0}$ is to the left
of $q_{0}$ and the distance between them is $d_{T_{S}}(g_{0},g_{0})$. For each
vertex $u_{i}\in V(T_{S^{\prime}})$, we place a point $p_{i}$ to the right of
$p_{0}$ such that the distance between them is $d_{T_{S}}(g_{0},u_{i})$, and a
point $q_{i}$ to the left of $q_{0}$ such that the distance between them is
$d_{T_{S}}(u_{i},h_{0})$. For each vertex $v_{j}\in V(T_{S})\setminus
V(T_{S^{\prime}})$, attached to a vertex $u_{j^{\prime}}\in
V(T_{S^{\prime}})$, we place four points: one each to the left of
$p_{j^{\prime}}$ and $q_{j^{\prime}}$ and one each to their right, at a
distance $d_{T_{S}}(u_{j},v_{j^{\prime}})$. See Figure 10 for reference. We
denote by $P_{S}$ the path represented by the left to right ordering of the
points placed.

Figure 10: Some of the vertices of $S^{\prime}$ mapped to a real line
$\mathbb{R}$.

Since, a single vertex of $S$ is represented by a constant number of nodes in
$P_{S}$ we have $|V(P_{S})|=O(n)$. Recall that
$R_{0}(P_{S})=\\{\operatorname{l-cost}(u,v)\mid\forall(u,v)\in V(P_{S})\times
V(P_{S})\\}$ and $R_{1}(P_{S})=\\{\operatorname{cost}(u,v)\mid\forall(u,v)\in
V(P_{S})\times V(P_{S})\\}$. Notice that $R_{0}(P_{S})=R_{S}^{\prime}$ and
$R_{1}(P_{S})$ contains all types of candidate values of $R_{S}$ except type
3(c). We can use Lemma 7 and the feasibility test of Section 3 to find
$\lambda_{1}$ and $\lambda_{2}$ such that
$\lambda_{1}<\lambda^{*}\leq\lambda_{2}$ and no value in $R_{0}(P_{S})\cup
R_{1}(P_{S})$ lies inside the range $(\lambda_{1},\lambda_{2})$. This step
takes $O(n\log n)$ time since in our case both $m$ and $\tau$ equals $O(n)$.
We can therefore make the following claim.

######  Theorem 2.

$\lambda^{*}=\lambda_{2}$ is the optimal cost of the $k$-center problem in $S$
if $\lambda^{*}$ is not a type 3(c) candidate value of $R_{S}$. This cost can
be computed in $O(n\log n)$ time, where $n$ is the size of the $S$.

######  Definition 1.

The _$\lambda$ -cover_ of a vertex $v\in V(S)$, denoted by
$\Phi_{\lambda}(v)$, is defined as

$\Phi_{\lambda}(v)=\\{y\in A(S)\mid w(v)\times d(y,v)\leq\lambda\\}.$

The subscript $\lambda$ from $\Phi_{\lambda}(\cdot)$ is usually omitted if
$\lambda=\lambda^{*}$.

Figure 11: Visualization of various definition.

The region $\Phi_{\lambda}(v)$ can also be defined as all possible location in
$S$ where a center can be placed with weighted distance to $v$ at most
$\lambda$.

######  Definition 2.

A point $y\in A(S)$ is an _endpoint_ of $\Phi_{\lambda}(v)$ if $w(v)\times
d(y,v)=\lambda$. Again, the subscript $\lambda$ is usually omitted if
$\lambda=\lambda^{*}$.

The endpoints of $\Phi_{\lambda}(v)$ are all possible location in $S$ where a
center can be placed with weighted distance to $v$ equal to $\lambda$. See
Figure 11 for reference. We have the following results.

######  Lemma 9.

For $u\in V(S)$ and $e\in E(S)$, $\Phi(u)$ has exactly one endpoint on $e$ if
and only if $\Phi_{\lambda}(u)$ has exactly one endpoint on $e$, for any
$\lambda\in(\lambda_{1},\lambda_{2})$.

###### Proof.

Let an endpoint of $\Phi(u)$ lie on the edge $e=(u_{e},v_{e})\in
E(S),u_{e},v_{e}\in V(S)$. Note that the values
$\operatorname{l-cost}(u,u_{e})$ and $\operatorname{l-cost}(u,v_{e})$ both
belong to $R_{S}^{\prime}$ and therefore, do not lie in the range
$(\lambda_{1},\lambda_{2})$. Let us assume, without loss of generality, that
$\operatorname{l-cost}(u,u_{e})\leq\operatorname{l-cost}(u,v_{e})$.

Since, $\Phi(u)$ has exactly one endpoint on $e$, we have
$\operatorname{l-cost}(u,u_{e})<\lambda^{*}<\operatorname{l-cost}(u,v_{e})$.
This implies that for any $\lambda\in(\lambda_{1},\lambda_{2})$,
$\operatorname{l-cost}(u,u_{e})<\lambda<\operatorname{l-cost}(u,v_{e})$ and
therefore $\Phi_{\lambda}(u)$ also has exactly one endpoint on $e$. The other
direction can be proved similarly. ∎∎

######  Lemma 10.

For any two vertices $u,v\in V(S)$, let $e\in E(S)$ be an edge such that it
does not belong to the major hemisphere of any cycle of $S$ in between $u$ and
$v$. The regions $\Phi(u)$ and $\Phi(v)$ overlap on $e$ if and only if
$\Phi_{\lambda}(u)$ and $\Phi_{\lambda}(v)$ overlap on $e$, for all
$\lambda\in(\lambda_{1},\lambda_{2})$.

###### Proof.

Let $e=(u_{e},v_{e})$, where $u_{e},v_{e}\in V(S)$. Let $\alpha^{*}$ denote
the overlapping region of $\Phi(u)$ and $\Phi(v)$ on $e$. Similarly, let
$\alpha$ denote the overlapping region of $\Phi_{\lambda}(u)$ and
$\Phi_{\lambda}(v)$ on $e$. We need to show that $\alpha^{*}$ is nonempty if
and only if $\alpha$ is nonempty.

If $\alpha$ is empty then either $\Phi(u)$ or $\Phi(v)$ does not intersect
$e$. Let us assume it is $\Phi(u)$. Then,
$\operatorname{l-cost}(u,u_{e}),\operatorname{l-cost}(u,v_{e})\leq\lambda^{*}$.
Since, $\operatorname{l-cost}(u,u_{e})$,
$\operatorname{l-cost}(u,v_{e})\notin(\lambda_{1},\lambda_{2})$ this implies
$\operatorname{l-cost}(u,u_{e})$, $\operatorname{l-cost}(u,v_{e})\leq\lambda$,
for any $\lambda\in(\lambda_{1},\lambda_{2})$. Therefore $\alpha$ is empty.

If $\alpha^{*}$ is nonempty and contains $u_{e}$ then
$\operatorname{l-cost}(u,u_{e}),\operatorname{l-cost}(v,u_{e})\geq\lambda^{*}$.
Since, $\operatorname{l-cost}(u,u_{e})$,
$\operatorname{l-cost}(v,u_{e})\notin(\lambda_{1},\lambda_{2})$ this implies
$\operatorname{l-cost}(u,u_{e})$, $\operatorname{l-cost}(v,u_{e})\geq\lambda$,
for any $\lambda\in(\lambda_{1},\lambda_{2})$. Therefore, $\alpha$ is also
nonempty and contains $u_{e}$. The same can be proved with respect to the
vertex $v_{e}$.

If $\alpha^{*}$ is nonempty and does not contain either $u_{e}$ or $v_{e}$
then, there exists a point $y_{e}\in\alpha^{*}$ such that $w(u)\cdot
d(u,y_{e})=w(v)\cdot d(y_{e},v)$ and for any two shortest paths $\pi_{y_{e}u}$
and $\pi_{y_{e}v}$ in $S$, $\pi_{y_{e}u}\cap\pi_{y_{e}v}=\varnothing$. This
implies that $\operatorname{cost}(u,v,y_{e})\in R(S)$. Since, $e$ does not
belong to the major hemisphere of any cycle of $S$ in between $u$ and $v$,
$\operatorname{cost}(u,v,y_{e})$ is not a type 3(c) candidate value, as
defined earlier, and so does not lie in the range $(\lambda_{1},\lambda_{2})$.
Since $y_{e}\in\alpha^{*}$, $\operatorname{cost}(u,v,y_{e})\geq\lambda^{*}$,
which in turn implies for any $\lambda\in(\lambda_{1},\lambda_{2})$,
$\operatorname{cost}(u,v,y_{e})\geq\lambda$. Therefore, $\alpha$ is also
nonempty and contains $y_{e}$. ∎∎

###  5.2 Stage 2

Now we show how to find $\lambda^{*}$ if it is a type 3(c) candidate value of
$R_{S}$. First we present a straightforward algorithm with running time
$O(n^{2}\log n)$. Later in Section 5.3 and 5.4 we present two techniques by
which we can improve the running time of this algorithm further.

For each cycle $C_{i}$ of $S$ we construct a path $P_{C_{i}}$ as follows.
Recall that $g_{i}$ and $h_{i}$ are the left and right hinge vertices of
$C_{i}$, respectively. For each vertex $u_{j}$ to the left of $C_{j}$, we
place a point $p_{j}$ at the $x$-axis of an $xy$-coordinate system with
$x$-coordinate $-d(u_{j},g_{i})$. Similarly, for each vertex $v_{j^{\prime}}$
to the right of $C_{i}$, we place a point $q_{j^{\prime}}$ on the $x$-axis at
the $x$-coordinate $\Delta_{i}+d(h_{i},v_{j^{\prime}})$, where $\Delta_{i}$ is
the length of the major hemisphere of $C_{i}$. The left to right ordering of
these points represent the path $P_{C_{i}}$.

Notice that the set $R^{\prime}=\bigcup_{i}R(P_{C_{i}})$ contains all type
3(c) candidate values of $R_{S}$. Therefore we can use Lemma 7 to find
$\lambda_{1}^{\prime}$ and $\lambda_{2}^{\prime}$ such that
$\lambda_{1}^{\prime}<\lambda^{*}\leq\lambda_{2}^{\prime}$ and no value in
$R^{\prime}$ lies inside the range
$(\lambda_{1}^{\prime},\lambda_{2}^{\prime})$. We update the previous
$\lambda_{1}$ and $\lambda_{2}$ values to
$\lambda_{1}\leftarrow\max\\{\lambda_{1},\lambda_{1}^{\prime}\\}$ and
$\lambda_{2}\leftarrow\min\\{\lambda_{2},\lambda_{2}^{\prime}\\}$. Since now
no value in $R_{S}$ lies inside the range $(\lambda_{1},\lambda_{2})$, we have
$\lambda^{*}=\lambda_{2}$.

Let $\hat{P}$ represent the concatenation of the paths $P_{C_{i}}$, for all
cycles $C_{i}$ in $S$. Since each path $P_{C_{i}}$ can be of size $O(n)$, the
size of $\hat{P}$ can be $O(n^{2})$, and the running time of our algorithm is
$O(n^{2}\log n)$.

###  5.3 An Improvement to Stage 2

One idea to improve the running time of Stage 2 is to not search for
$\lambda^{*}$ over all possible type 3(c) candidate values but over the onces
which are absolutely necessary. We achieve this by performing a feasibility
test on $S$ and placing the centers optimally. Whenever we are unsure of the
placement of a new center, we perform an additional feasibility test.

We perform the feasibility test on $S$ by first choosing a
$\lambda\in(\lambda_{1},\lambda_{2})$ (from Stage 1). The test processes the
vertices of $S$ from left to right. At any intermediate step, the feasibility
test may place centers on $S$. If the centers are placed on edges which do not
belong to the major hemisphere of any cycle of $S$ then we continue to place
those centers. This is because if any such center $x_{i}$ determines the
optimal cost $\lambda^{*}$, then that cost does not belong to the range
$(\lambda_{1},\lambda_{2})$, since then $\lambda^{*}$ is not a type 3(c)
candidate value. Therefore, the vertices covered by $x_{i}$ will remain the
same in the optimal case.

If the centers are placed on edges which do belong to the major hemisphere of
some cycle $C_{j}$ of $S$, then we perform some extra steps. Let $x_{l}$ be
such a center. There is a possibility that $x_{l}$ determines the optimal cost
$\lambda^{*}$. Let $u^{*},v^{*}\in V(S)$ be two critical vertices of $x_{l}$
i.e. $\operatorname{cost}(u^{*},v^{*},x_{l})=\lambda^{*}$. The value
$\operatorname{cost}(u^{*},v^{*},x_{l})$ is a type 3(c) candidate value if
neither $u^{*}$ nor $v^{*}$ belong to $V(\hat{C}_{j})$. This implies that
$\operatorname{cost}(u^{*},v^{*},x_{l})$ may lie inside the range
$(\lambda_{1},\lambda_{2})$, and we cannot provide the same guarantees as we
did for the previous case. We therefore try to further reduce the range
$(\lambda_{1},\lambda_{2})$ as follows.

We generate the path $P_{C_{j}}$ as mentioned earlier and use Lemma 7 to find
$\lambda_{1}^{\prime}$ and $\lambda_{2}^{\prime}$ such that
$\lambda_{1}^{\prime}<\lambda^{*}\leq\lambda_{2}^{\prime}$ and no value in
$R(P_{C_{j}})$ lies inside the range
$(\lambda_{1}^{\prime},\lambda_{2}^{\prime})$. We update the previous
$\lambda_{1}$ and $\lambda_{2}$ values to
$\lambda_{1}\leftarrow\max\\{\lambda_{1},\lambda_{1}^{\prime}\\}$ and
$\lambda_{2}\leftarrow\min\\{\lambda_{2},\lambda_{2}^{\prime}\\}$.

This ensures that
$\operatorname{cost}(u,v,x_{l})\notin(\lambda_{1},\lambda_{2})$ for any
$u,v\in V(S)$. We update our choice of $\lambda$ to the new range
$(\lambda_{1},\lambda_{2})$ and continue placing centers using our feasibility
test algorithm. The center $x_{l}$ placed after this step will ensure that the
vertices which covered by it will remain same in the optimal case. We continue
the process until all $k$ centers have been placed. We make the following
claims.

######  Lemma 11.

After completion of Stage 2, $\lambda^{*}=\lambda_{2}$.

###### Proof.

The only type 3(c) candidate values of $R(S)$ that we need to consider are
$\operatorname{cost}(u,v,x)$, where $x$ lies on the major hemisphere of a
cycle where our feasibility test wants to place a center. Since after
completion of Stage 2 no such value lies inside the range
$(\lambda_{1},\lambda_{2})$, therefore $\lambda_{2}=\lambda^{*}$. ∎∎

######  Lemma 12.

The time required by Stage 2 is at most $O(kn\log n)$.

###### Proof.

Whenever a center needs to be placed on the major hemisphere of some cycle
$C_{j}$ of $S$ we generate the path $P_{C_{j}}$ and compute appropriate
$\lambda_{1}^{\prime}$ and $\lambda_{2}^{\prime}$. Similar to Stage 1, this
step takes $O(n\log n)$ time since $|V(P_{C_{j}})|=O(n)$. Since we are placing
$k$ centers in $S$, such a step can repeat at most $k$ time. Therefore, the
running time is $O(kn\log n)$. ∎∎

###  5.4 Further Improving Stage 2

####  5.4.1 Preliminaries

Consider a feasibility test on $S$ with $\lambda=\lambda^{*}$ and root
$h_{0}$, the rightmost vertex of $S$. Let $X^{*}\subset A(S)$ be the set of
$k$ centers placed by the feasibility test. The set $X^{*}$ is an optimal
solution to the weighted $k$-center problem in $S$.

Since we assume $\lambda^{*}$ to be a type 3(c) candidate value of $R_{S}$,
there exists $u^{*},v^{*}\in V(S)$ and $x^{*}\in X^{*}$, such that
$\lambda^{*}=\operatorname{cost}(u^{*},v^{*},x^{*})$. Also, $x^{*}$ lies on
the major hemisphere of some cycle $C_{i^{*}}$ and $u^{*},v^{*}\notin
V(\hat{C}_{i^{*}})$. We consider the triplet $(u^{*},v^{*},x^{*})$ for which
$C_{i^{*}}$ is the leftmost possible cycle of $S$.

We assume $\Phi(u^{*})$ and $\Phi(v^{*})$ to completely cover the minor
hemisphere of cycle $C_{i^{*}}$ as shown in Figure 12 and show some
properties.

Figure 12: The $\lambda$-regions of $u$ and $v$ where
$\lambda=\operatorname{cost}(u,v,x)$.

Arguing similar to the proof of Lemma 9 we can show that $\Phi(v)$, for some
$v\in V(S)$, completely covers the minor hemisphere of a cycle $C_{i}$ of $S$
if and only if $\Phi_{\lambda_{2}}(v)$ also covers it completely.

######  Definition 3.

A _twig_ is any pendant (degree one) vertex $u$, adjacent to a vertex $v$, for
which $v\notin\Phi(u)$, $u,v\in V(S)$.

A twig is any pendant vertex $u$ of $S$ for which a center $x$ placed at its
adjacent vertex has a weighted distance of more than $\lambda^{*}$ from $u$.
Arguing similar to the proof of Lemma 9 we can also show that $u$ is a twig if
$v\notin\Phi_{\lambda_{2}}(u)$.

######  Definition 4.

A vertex $u$ is a _free_ vertex if $\Phi(u)\cap\Phi(v)=\varnothing$, for all
twigs $v$ in $V(S)$.

A free vertex is any vertex of $S$ which cannot be simultaneously covered
along with a twig by a single center. For reference, see Figure 11.

######  Definition 5.

The _$\lambda$ -intersection_ of a cycle $C_{i}$, denoted by
$\Theta_{\lambda}(C_{i})$, is defined as

$\Theta_{\lambda}(C_{i})=\bigcap_{v\in V^{\prime}_{i}}\Phi_{\lambda}(v),$

where $V_{i}^{\prime}$ represent the set of all free vertices in
$V(\hat{C}_{i})$. Again, the subscript $\lambda$ from
$\Theta_{\lambda}(\cdot)$ is omitted if $\lambda=\lambda^{*}$.

Figure 13: $\lambda^{*}$-intersection of $C_{i}$.

See Figure 13 for reference. We are now ready to make the following claims.

######  Lemma 13.

For vertex $u^{*}$ and cycle $C_{i^{*}}$ the following two conditions hold:
_(a)_ $\Phi(u^{*})\cap\Theta(C_{i^{*}})\neq\varnothing$ and _(b)_
$h_{i^{*}}\notin\Theta(C_{i^{*}})$.

###### Proof.

First we show that all vertices in $V_{i^{*}}^{\prime}$ are covered by the
center $x^{*}$. Let us assume that there is one more center $x^{\prime}$
covering some vertices in $V_{i^{*}}^{\prime}$ which are uncovered by $x^{*}$.
Since all vertices in $V_{i^{*}}^{\prime}$ are non-twig vertices, $x^{\prime}$
can be placed on $C_{i^{*}}$ (and not inside any of its incident edges). But
$\Phi(u)\cup\Phi(v)$ completely overlaps with all of $C_{i^{*}}$ and as a
result $x^{\prime}$ will also cover either $u^{*}$ or $v^{*}$. This implies
that $\operatorname{cost}(u^{*},v^{*},x^{*})$ will not determine
$\lambda^{*}$, which is a contradiction.

Since all vertices in $V_{i^{*}}^{\prime}$ and the vertex $u^{*}$ are covered
by $x^{*}$, this implies that $\Theta(C_{i^{*}})$ is non-empty and intersects
with $\Phi(u^{*})$ which proves our first condition. If $\Theta(C_{i^{*}})$
contains $h_{i^{*}}$ then the feasibility test would have placed $x^{*}$ on
$h_{i^{*}}$ instead of on the major hemisphere of $C_{i^{*}}$. This would lead
to $\operatorname{cost}(u^{*},v^{*},x^{*})$ not being a type 3(c) candidate
value, another contradiction. This proves our second condition. ∎∎

######  Lemma 14.

No cycle $C_{j}$ between $u^{*}$ and $C_{i^{*}}$ satisfies both conditions of
Lemma 13 simultaneously.

###### Proof.

Let us assume there exists a cycle $C_{j}$, in between vertex $u^{*}$ and
cycle $C_{i^{*}}$ which satisfies both conditions of Lemma 13 simultaneously.
Since $u^{*}$ is covered by $x^{*}$ which is to the right of $C_{j}$, all
vertices in $V_{j}^{\prime}$ are either covered by $x^{*}$ or by at most one
center placed on $C_{j}$. This condition holds because $\Theta(C_{j})$ is non-
empty and $V_{j}$ has no twigs.

If all vertices in $V_{j}^{\prime}$ are covered by $x^{*}$ then
$h_{j}\in\Theta(C_{j})$, which is a contradiction. If
$h_{j}\notin\Theta(C_{j})$, then one center say $x^{\prime}$ needs to be
placed on $C_{j}$ to cover the vertices in $V_{j}^{\prime}$. But since
$\Phi(u^{*})$ intersects $\Theta(C_{j})$ the feasibility test, while
processing $C_{j}$, will place $x^{\prime}$ in such a way that it also covers
$u^{*}$. This is a contradiction since
$\operatorname{cost}(u^{*},v^{*},x^{*})$ will not determine $\lambda^{*}$
then. ∎∎

From Lemma 13 and 14 we can make the following observation.

######  Observation 1.

Let $u,v\in V(S)$ and $x$ belongs to the major hemisphere of a cycle $C_{i}$
such that $\Phi(u)$ completely overlaps with the minor hemisphere of $C_{i}$.
We consider only those type 3(c) candidate values $\operatorname{cost}(u,v,x)$
where $C_{i}$ is the first cycle to the right of $u$ which satisfies both
conditions in Lemma 13.

Consider an $xy$-coordinate system $\mathbb{R}^{2}$. For each vertex $v_{i}\in
V(S)$, we place a point $p_{i}$ on the $x$-axis of $\mathbb{R}^{2}$ at the
$x$-coordinate $d(v_{i},h_{0})$. For each such point $p_{i}$ we place a line
$l_{i}$ on it with slope $w(v_{i})$. Let $L_{S}$ be the set of these lines. We
have the following definition.

######  Definition 6.

The _rank_ of a vertex $v_{i}\in V(S)$ is the respective position of line
$l_{i}$ in a left to right ordering of the intersections of all lines in
$L_{S}$ with the horizontal line $y=\lambda^{*}$.

Note that the ranks of the vertices do not change if we replace $\lambda^{*}$
with $\lambda_{2}$.

Let $u,v\in V(S)$ be such that
$\operatorname{rank}(u)\leq\operatorname{rank}(v)$. Let $C_{i}$ be a cycle to
the right of both $u$ and $v$. From the definition of rank we have the
following observation.

######  Observation 2.

$\Phi(u)\cap\mathcal{A}(C_{i})\subseteq\Phi(v)\cap\mathcal{A}(C_{i})$.

####  5.4.2 Finding the first cycle.

We present an algorithm to find for each vertex $v\in V(C)$ the first cycle to
its right which satisfies Lemma 13, if it exists. Let $\mathcal{C}$ be the set
of cycles in $S$ ordered from left to right. We compute
$\Theta_{\lambda_{2}}(C_{i})$ for all cycle $C_{i}$ in $\mathcal{C}$. We
remove from $\mathcal{C}$ any cycle $C_{j}$ for which either
$\Theta_{\lambda_{2}}(C_{j})=\varnothing$ or
$h_{j}\in\Theta_{\lambda_{2}}(C_{j})$. This is because for any point $x\in
A(C_{j})$ a type 3(c) candidate value $\operatorname{cost}(u,v,x)$ will never
satisfy Lemma 13.

We process the vertices in $V(S)$ with increasing rank and perform the
following step. Let $v_{i}$ be the vertex we are currently processing. Find
the leftmost cycle $C_{j}\in\mathcal{C}$ which is to the right of $u_{i}$. If
no cycle exists we skip $u_{i}$ and continue to the next higher ranked vertex.
This implies that no cycle exists to the right of $u_{i}$ which satisfies
Lemma 13.

If cycle $C_{j}$ exists, then we check if
$\Phi_{\lambda_{2}}(u_{i})\cap\Theta_{\lambda_{2}}(C_{j})\neq\varnothing$. If
the condition holds, we correctly identify $C_{j}$ as the first vertex to the
right of $u_{i}$ which satisfies Lemma 13. We continue to the next higher
ranked vertex.

Otherwise, if the condition is not satisfied, we remove $C_{j}$ from
$\mathcal{C}$. This is because from Observation 2, for any vertex $v_{j}$ with
$\operatorname{rank}(v_{j})\geq\operatorname{rank}(v_{i})$,
$\Phi_{\lambda_{2}}(u_{i})\cap\Theta_{\lambda_{2}}(C_{j})=\varnothing$. We
continue to the next cycle in $\mathcal{C}$ to the right of $C_{j}$. We stop
when either $\mathcal{C}$ is empty or when all vertices in $V(S)$ have been
processed.

When a vertex is successfully mapped to a cycle we charge the operation on the
vertex and when a cycle is unsuccessfully compared for mapping with a vertex
we charge the operation on the cycle. Since, each vertex and cycle is charged
exactly once the running time of this procedure is $O(n\log n)$. The $\log n$
factor comes in since we have to identify the first cycle in $\mathcal{C}$ to
the right of a particular vertex which takes $O(\log n)$ time.

####  5.4.3 The improved algorithm.

Here is the final algorithm which improves upon the running time of Stage 2
considerably. Consider an $xy$-coordinate system $\mathbb{R}^{2}$. For each
vertex $v_{i}\in V(S)$, we place a point $p_{i}$ on the $x$-axis of
$\mathbb{R}^{2}$ at a distance of $d(v_{i},h_{0})$ to the left of the origin.
Again, for each vertex $v_{i}\in V(S)$, let $C_{j_{1}}$ be the first cycle to
the right of $v_{i}$ which satisfies Lemma 13 and let $C_{j_{2}}$ be the cycle
to the right of $v_{i}$ where $\Phi(v_{i})$ has an endpoint on its minor
hemisphere. We place points $p_{j_{1}^{\prime}}$ and $p_{j_{2}^{\prime}}$ on
the $x$-axis at a distance of
$d(v_{i},g_{j_{1}})+\Delta_{j_{1}}+d(h_{j_{1}},h_{0})$ and
$d(v_{i},g_{j_{2}})+\Delta_{j_{2}}+d(h_{j_{2}},h_{0})$ to the left of the
origin, respectively, where $\Delta_{i}$ is the length of the major hemisphere
of cycle $C_{i}$.

Let $P_{S}^{\prime}$ be the path formed by a left to right ordering of these
points. We can make the following observation.

######  Observation 3.

Every relevant type 3(c) candidate value of $R_{S}$ is included in
$R(P_{S}^{\prime})$.

Therefore, using Lemma 7, we can find $\lambda_{1}^{\prime}$ and
$\lambda_{2}^{\prime}$ such that (a)
$\lambda_{1}^{\prime}<\lambda^{*}\leq\lambda_{2}$, and (b) no relevant type
3(c) candidate value is inside the range
$(\lambda_{1}^{\prime},\lambda_{2}^{\prime})$. Finally we update
$\lambda_{1}\leftarrow\max\\{\lambda_{1},\lambda_{1}^{\prime}\\}$ and
$\lambda_{2}\leftarrow\min\\{\lambda_{2},\lambda_{2}^{\prime}\\}$. Since we
have exhausted all candidate values of $\lambda^{*}$,
$\lambda^{*}=\lambda_{2}$. Since the size of $P_{S}^{\prime}$ is $O(n)$ we
have the following theorem.

######  Theorem 3.

The weighted $k$-center problem on a cactus stem of size $n$ can be solved in
$O(n\log n)$ time.

##  6 The Main Algorithm

We are now ready to present our algorithm for the $k$-center problem on the
cactus $G$. Initialize $\lambda_{1}\leftarrow 0$ and
$\lambda_{2}\leftarrow\infty$. Let $G^{\prime}$ be the graph formed by
removing all pendant vertices from $G$ and let $T$ be its tree representation.
Note that $t_{r}$ (a leaf node) and its associate vertex $v_{r}$ represent the
roots of $T$ and $G$, respectively.

######  Definition 7.

A _maxpath_ of a rooted tree is any subpath in the tree whose end nodes are
either of degree 1, or 3, or more, and whose internal nodes are of degree 2. A
_leaf maxpath_ is any maxpath of which contains a leaf of the tree (other than
the root).

For each leaf maxpath $\pi_{i}$ of $T$, we do the following. Let
$t_{1},t_{2},\ldots,t_{m}$ be the nodes in $\pi_{i}$ such that $t_{1}$ is a
leaf. If $t_{m}$ represents a cycle of $G$, then we set $\pi_{i}^{\prime}$ to
path $\pi_{i}$ with node $t_{m}$ removed; otherwise $\pi_{i}^{\prime}$ is same
as $\pi_{i}$. Let $S^{\prime}_{i}$ be the subgraph of $G$ that
$\pi_{i}^{\prime}$ represents and let $S_{i}$ be the graph formed by attaching
all pendant vertices of $G$ adjacent to $S^{\prime}_{i}$ to it. If
$\pi_{i}^{\prime}$ contains the node $t_{m}$, then $t_{m}$ is either a graft
or a hinge. Let $v_{m}\in V(G)$ be the associate vertex of $t_{m}$. We do not
include the pendant vertices adjacent to $v_{m}$ in $S_{i}$. We call $S_{i}$ a
_leaf cactus stem_ of $G$. See Figures 14 and 15 for reference.

Figure 14: The nodes from $t_{1}$ to $t_{7}$ represent a leaf maxpath
$\pi_{i}$ of $T$. The subpath $\pi_{i}^{\prime}$ is from $t_{1}$ to $t_{6}$,
as $t_{7}$ represents $C_{7}$. The subgraph $S_{i}^{\prime}$ is from $v_{1}$
to $v_{6}$. Figure 15: The leaf cactus stems $S_{1},S_{2}$ and $S_{3}$ of $G$
with root $v_{r}$.

For all leaf cactus stems $S_{i}$, we perform Stage 1 and Stage 2 of Section
5. For Stage 1, we generate $P_{S_{i}}$ for each $S_{i}$. We use Lemma 7 to
find the corresponding $\lambda_{1}^{\prime}$ and $\lambda_{2}^{\prime}$
values. For stage 2, we can process each $S_{i}$ sequentially to find the
updated $\lambda_{1}^{\prime}$ and $\lambda_{2}^{\prime}$ values. It can be
showed that $\lambda_{1}^{\prime}<\lambda^{*}\leq\lambda_{2}^{\prime}$ and no
value in $\bigcup_{i}R_{S_{i}}$ lies inside the range
$(\lambda_{1}^{\prime},\lambda_{2}^{\prime})$. We update $\lambda_{1}$ and
$\lambda_{2}$ to
$\lambda_{1}\leftarrow\max\\{\lambda_{1},\lambda_{1}^{\prime}\\}$ and
$\lambda_{2}\leftarrow\min\\{\lambda_{2},\lambda_{2}^{\prime}\\}$.

We now do a feasibility test on $G$ by choosing a
$\lambda\in(\lambda_{1},\lambda_{2})$. Let $X$ be the set of centers placed by
the feasibility test. This defines a partition on $G$ where each vertex is
associated with its nearest center. By our definition of $\lambda_{1}$ and
$\lambda_{2}$, for each cactus stem $S_{i}$ in $G$, the partition defined by
$X$ on $S_{i}$ is the same as that defined by an optimal set of centers
$X^{*}$. This property was extensively exploited by Frederickson et al. [8] in
the design of their optimal algorithm. We process each leaf cactus stem
$S_{i}$ of $G$ and convert it into a pendant vertex of $G$ as follows.

Let $h\in V(S_{i})$ be the vertex through which $S_{i}$ is connected to the
rest of the graph $G$. Let $x_{h}\in X$ be the center closest to $h$ and let
$V^{\prime}\subseteq V(S)$ be the set of vertices for which $x_{h}$ is the
nearest center. We replace $S$ by a pendant vertex $h^{\prime}$ attached to
$h$ such that $h^{\prime}=\arg\min_{v}\\{\lambda/w(v)-d(h,v)\mid\forall v\in
V^{\prime}\\}$ and set the length of the edge $(h,h^{\prime})$ to
$d(h,h^{\prime})$. Let $X_{S_{i}}\subseteq X$ be the set of centers placed in
$S_{i}$. Since $\lambda\in(\lambda_{1},\lambda_{2})$, the vertices in
$V(S_{i})\setminus V^{\prime}$ will also be covered by
$X_{S_{i}}\setminus\\{x_{h}\\}$ in the optimal case. Therefore, we can be
certain that these centers should also be included in the optimal set.

We decrement from $k$ the number of centers thus placed i.e.
$|X_{S_{i}}\setminus\\{x_{h}\\}|$. We continue the process recursively in the
new cactus until a single cactus stem remains. We can compute the weighted
$k$-center in this last stem by using the algorithm in Section 5. We have the
following result.

######  Theorem 4.

The weighted $k$-center problem on a cactus $G$ can be solved in
$O(n\log^{2}n)$ time, where $n$ is the number of vertices of $G$.

###### Proof.

In each iteration, performing the steps of Stage 1 and Stage 2 takes $O(n\log
n)$ time. Moreover, in every iteration, all leaf cactus stems of the graph get
reduced to a pendant vertex. This may result in new cactus stems becoming leaf
cactus stems. However, the number of such new cactus stems can be at most half
of the number of previous leaf cactus stems. This results in at most $O(\log
n)$ many iterations. Therefore, the total time taken by our algorithm over all
iterations is $O(n\log^{2}n)$. ∎∎

##  7 Conclusion

In this paper we presented an $O(n\log^{2}n)$ time algorithm to solve the
weighted $k$-center problem in a cactus of size $n$. We adapt and use
Frederickson and Johnson’s [9] parametric search technique, generalized by
Wang and Zhang [13], to achieve our result. In their papers they had also
shown how to iteratively optimize the feasibility test algorithm to achieve a
sublinear running time. It is worth pursuing to adapt this idea to find a
faster feasibility test algorithm for our problem. This has the potential of
further reducing the running time of our algorithm by a factor of $\log n$
which we believe will be optimal.

## References

  * [1] Aritra Banik, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda, and Zhao Song.  The $p$-center problem in tree networks revisited.  In 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016.
  * [2] Boaz Ben-Moshe, Binay Bhattacharya, Qiaosheng Shi, and Arie Tamir.  Efficient algorithms for center problems in cactus networks.  Theoretical Computer Science, 378(3):237–252, 2007.
  * [3] Binay Bhattacharya, Sandip Das, and Subhadeep Ranjan Dev.  The weighted $k$-center problem in trees for fixed $k$.  In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [4] Binay Bhattacharya, Mordecai J Golin, Yuya Higashikawa, Tsunehiko Kameda, and Naoki Katoh.  Improved algorithms for computing $k$-sink on dynamic flow path networks.  In Workshop on Algorithms and Data Structures, pages 133–144. Springer, 2017.
  * [5] Binay Bhattacharya and Qiaosheng Shi.  Improved algorithms to network $p$-center location problems.  Computational Geometry, 47(2):307–315, 2014.
  * [6] Danny Z Chen and Haitao Wang.  A note on searching line arrangements and applications.  Information Processing Letters, 113(14-16):518–521, 2013.
  * [7] Greg N Frederickson.  Optimal algorithms for tree partitioning.  In Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, pages 168–177, 1991.
  * [8] Greg N Frederickson.  Parametric search and locating supply centers in trees.  In Workshop on Algorithms and Data Structures, pages 299–319. Springer, 1991.
  * [9] Greg N Frederickson and Donald B Johnson.  Finding $k$th paths and $p$-centers by generating and searching good data structures.  Journal of Algorithms, 4(1):61–80, 1983.
  * [10] Alexander Gavruskin, Bakhadyr Khoussainov, Mikhail Kokho, and Jiamou Liu.  Dynamic algorithms for monotonic interval scheduling problem.  Theoretical Computer Science, 562:227–242, 2015.
  * [11] Wen-Lian Hsu and Kuo-Hui Tsai.  Linear time algorithms on circular-arc graphs.  Information Processing Letters, 40(3):123–129, 1991.
  * [12] Oded Kariv and S Louis Hakimi.  An algorithmic approach to network location problems. I: The $p$-centers.  SIAM Journal on Applied Mathematics, 37(3):513–538, 1979.
  * [13] Haitao Wang and Jingru Zhang.  An $O(n\log n)$-time algorithm for the $k$-center problem in trees.  In 34th International Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.