# Balancing graph Voronoi diagrams with one more vertex

Guillaume Ducoffe  National Institute for Research and Development in
Informatics, Romania University of Bucharest, Romania

###### Abstract

Let $G=(V,E)$ be a graph with unit-length edges and nonnegative costs assigned
to its vertices. Being given a list of pairwise different vertices
$S=(s_{1},s_{2},\ldots,s_{p})$, the prioritized Voronoi diagram of $G$ with
respect to $S$ is the partition of $G$ in $p$ subsets
$V_{1},V_{2},\ldots,V_{p}$ so that, for every $i$ with $1\leq i\leq p$, a
vertex $v$ is in $V_{i}$ if and only if $s_{i}$ is a closest vertex to $v$ in
$S$ and there is no closest vertex to $v$ in $S$ within the subset
$\\{s_{1},s_{2},\ldots,s_{i-1}\\}$. For every $i$ with $1\leq i\leq p$, the
load of vertex $s_{i}$ equals the sum of the costs of all vertices in $V_{i}$.
The load of $S$ equals the maximum load of a vertex in $S$. We study the
problem of adding one more vertex $v$ at the end of $S$ in order to minimize
the load. This problem occurs in the context of optimally locating a new
service facility (e.g., a school or a hospital) while taking into account
already existing facilities, and with the goal of minimizing the maximum
congestion at a site. There is a brute-force algorithm for solving this
problem in ${\cal O}(nm)$ time on $n$-vertex $m$-edge graphs. We prove a
matching time lower bound for the special case where $m=n^{1+o(1)}$ and $p=1$,
assuming the so called Hitting Set Conjecture of Abboud et al. On the positive
side, we present simple linear-time algorithms for this problem on cliques,
paths and cycles, and almost linear-time algorithms for trees, proper interval
graphs and (assuming $p$ to be a constant) bounded-treewidth graphs.

Keywords: graph Voronoi diagrams; facility location problems; HS-hardness;
graph algorithms.

##  1 Introduction

For undefined graph terminology, see [7]. All graphs considered are finite,
simple (they are loopless and have no multiple edges), connected and with
unit-length edges. Let $G=(V,E)$ be a graph. Throughout the paper, let $n=|V|$
and $m=|E|$. The distance between two vertices $u$ and $v$ is the minimum
number of edges on a $uv$-path. We denote this distance by $d_{G}(u,v)$, or
simply $d(u,v)$ if $G$ is clear from the context. Being given a vertex $v$ and
a vertex subset $S=\\{s_{1},s_{2},\ldots,s_{p}\\}$, let also
$d(v,S)=\min_{1\leq i\leq p}d(v,s_{i})$ denote the distance between $v$ and
$S$. A Voronoi diagram of $G$ with respect to $S$ is any partition
$V_{1},V_{2},\ldots,V_{p}$ of $V$ such that, for every $i$ with $1\leq i\leq
p$, for every vertex $v$ with $v\in V_{i}$, $d(v,s_{i})=d(v,S)$. This
terminology originates from Computational Geometry, where the Voronoi diagram
is a well-studied data structure [3]. An example of graph Voronoi diagram is
given in Fig. 1. We stress that in general, a Voronoi diagram is not uniquely
defined, due to the possible existence of vertices $v$ such that
$d(v,s_{i})=d(v,s_{j})=d(v,S)$, for some $i$ and $j$ with $1\leq i<j\leq p$.

$\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}\mathbf{s_{3}}\mathit{(s_{3})}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbf{s_{1}}\mathit{(s_{1})}$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}u\mathit{(s_{2})}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}v\mathit{(s_{1})}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}w\mathit{(s_{1})}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}x\mathit{(s_{1})}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}y\mathit{(s_{1})}$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{s_{2}}\mathit{(s_{2})}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}z\mathit{(s_{1})}$
Figure 1: A graph Voronoi diagram with respect to three vertices
$s_{1},s_{2},s_{3}$. For each vertex of the graph, the corresponding vertex of
$S$ is indicated in brackets. Since $d(s_{1},u)=d(s_{2},u)$, this diagram is
not unique.

To our best knowledge, Mehlorn was amongst the first to introduce the concept
of graph Voronoi diagrams, which he used in the design of an approximation
algorithm for the Steiner Tree problem [22]. Erwig further pursued the study
of these objects, of which he presented some new algorithmic applications
[13]. Since then, graph Voronoi diagrams have appeared as a building block of
even more algorithms [9, 11, 16]. In [23], Okabe et al. introduced generalized
network Voronoi diagrams, of which graph Voronoi diagrams are special cases.
Other variations such as furthest color Voronoi diagrams were considered in
[20]. We only consider graph Voronoi diagrams in what follows.

Hakimi and Labbé introduced graph Voronoi diagrams, which they called Voronoi
partitions, as a location-theoretic concept [18]. We build on their previous
work and terminology. Specifically, being given a vertex subset
$S=\\{s_{1},s_{2},\ldots,s_{p}\\}$, and a Voronoi diagram
$V_{1},V_{2},\ldots,V_{p}$ of $G$ with respect to $S$, we call sites the
vertices in $S$, and we call territories the subsets $V_{i}$, with $1\leq
i\leq p$, of this partition. For concreteness, we may regard the sites in $S$
as locations of service facilities such as schools or hospitals. With this
interpretation in mind, every territory is the service area of some facility.
Several optimization criteria can be considered for these territories. Being
given some measure $\mu:V\times 2^{V}\to\mathbb{R}_{\geq 0}$ and a nonnegative
integer $p$, the $\mu$-Voronoi $p$-Center problem is the problem of minimizing
$\max_{1\leq i\leq p}\mu(s_{i},V_{i})$ amongst all possible graph Voronoi
diagrams with respect to $p$ sites. For instance, if
$\mu(s_{i},V_{i})=\max_{v\in V_{i}}d(v,s_{i})$, then this is the classical
$p$-Center problem. Throughout the paper, let some function
$\pi:V\to\mathbb{R}_{\geq 0}$ assign nonnegative costs to the vertices. We
call $p$-Balance the $\mu_{\pi}$-Voronoi $p$-Center problem for the measure
$\mu_{\pi}$ such that $\mu_{\pi}(s_{i},V_{i})=\sum_{v\in V_{i}}\pi(v)$. For
concreteness, we may regard $\mu_{\pi}(s_{i},V_{i})$, which we call the load
of site $s_{i}$, as the population size in a service area. We call our
objective function $\max_{1\leq i\leq p}\mu_{\pi}(s_{i},V_{i})$ the load of
the Voronoi diagram. The $p$-Balance problem is NP-hard if $p$ is part of the
input [19]. Interestingly, the NP-hardness reduction in [19] outputs instances
of the problem such that if there exists a graph Voronoi diagram with load at
most some value $q$, then there always exist $p$ sites minimizing the load
such that every vertex is at minimal distance of exactly one site. This
implies that the difficulty of this problem does not come from the non-
uniqueness of a Voronoi diagram.

In practice, we must account for the location of existing service facilities
in order to optimally locate a new one. As a starter, let us consider the
following problem (which is not quite yet what we study in the paper). We are
given a subset $S$ of sites, and the goal is to compute a new site $v$, with
$v\notin S$, and a Voronoi diagram with respect to $S\cup\\{v\\}$ such that
the load is minimized. This problem is NP-hard even if $S$ is a singleton and
$G$ is a complete graph. Indeed, in this situation we can select any vertex
$v\notin S$ as the new site, but the difficulty consists in computing an
optimal graph Voronoi diagram. The load of any such diagram must be at least
$\pi(G)/2$, where $\pi(G)$ is the sum of the cost of all vertices. Moreover,
deciding whether there exists a solution with load $\pi(G)/2$ is equivalent to
the well-known Partition problem [14]. In order to circumvent this negative
result, we show that it is enough to force the Voronoi diagram to be uniquely
defined. More precisely, motivated by the practical need to minimally
reorganize the diagram after inserting a new site, we follow Erwig’s
suggestion to prioritize the sites [13]. That is,
$S=(s_{1},s_{2},\ldots,s_{p})$ is a list, and every vertex $v$ must be
assigned to its first closest site in the list. Formally, for every $i$ with
$1\leq i\leq p$, we have $v\in V_{i}$ if and only if $d(v,s_{i})=d(v,S)$ and
$d(v,s_{j})>d(v,S)$ for every $j$ with $1\leq j<i$. We call it the prioritized
Voronoi diagram, or simply the Voronoi diagram of $G$ with respect to $S$, and
we denote it in what follows by $\mathbf{Vor}(G,S)$. Other conditions could be
also considered. For instance, one could add every vertex $v$ to the
territories of all its closest sites in $S$, which is actually what Hakimi et
al. did in [19]. However, having a vertex partition is important in some
practical scenarios (e.g., a student attends to only one school). Furthermore,
we stress that most results in the paper do not really depend on which
condition we choose (a notable exception being the hardness result of Theorem
2.8).

For every $i$ with $1\leq i\leq p$, we denote by $\ell_{\pi}(s_{i},S)$ the
load of site $s_{i}$ in $\mathbf{Vor}(G,S)$. The load of $\mathbf{Vor}(G,S)$
is denoted by $L_{\pi}(S)$. To our best knowledge, the following problem has
not been considered before:

######  Problem 1 (Balanced Vertex).

Input: A graph $G=(V,E)$; A cost function $\pi:V\to\mathbb{R}_{\geq 0}$; A
list $S=(s_{1},s_{2},\ldots,s_{p})$ of pairwise different vertices. Output: A
vertex $v\in V\setminus S$ such that $L_{\pi}(S+v)$ is minimized, where
$S+v=(s_{1},s_{2},\ldots,s_{p},v)$.

Closest to our work is the one-round Voronoi game on graphs [4]. In the latter
two-player game, Player $1$ first selects a subset $S$ of sites with some
fixed cardinality. Then, Player $2$ must select a $k$-set $S^{\prime}$ of new
sites, with $S^{\prime}\cap S=\emptyset$, in order to maximize the cumulative
load of all $k$ sites in $S^{\prime}$ in the graph Voronoi diagram with
respect to $S^{\prime}+S$ (the new sites in $S^{\prime}$ have higher priority
than the former sites in $S$). By contrast, in our problem we aim at
minimizing the load at any site, and we also account for the load of all
former sites in $S$ and not just for the load of the new site. Furthermore,
the new site is given the least priority.

#### Our contributions.

We initiate the complexity study of the Balanced Vertex problem.

On general $n$-vertex $m$-edge graphs, the problem can be solved in ${\cal
O}(nm)$ time by brute force, simply by considering each vertex $v\notin S$
(Theorem 2.5). We prove a matching time lower bound assuming the so-called
Hitting Set Conjecture (Theorem 2.8). The latter was introduced in [1] by
Abboud et al. as a way to explain our lack of progress toward computing faster
either the radius or the median of a graph. Since then, to our best knowledge,
broader implications of the Hitting Set Conjecture have not been investigated.
Our work makes a step in this direction. A better-studied conjecture, that is
implied by the Hitting Set Conjecture and by the Strong Exponential Time
Hypothesis, is the so called Orthogonal Vectors Conjecture [25]. We leave as
an open problem whether we can prove a quadratic time lower bound for the
Balanced Vertex problem assuming this conjecture.

In the second and longest part of the paper, we break the quadratic barrier
for Balanced Vertex on several graph classes, with either some tree-like or
path-like underlying structure. For that, we adapt tools for fast distance
computation, one of them being the orthogonal range query framework of Cabello
and Knauer [10], in order to compute the load $\ell_{\pi}(v,S+v)$ of every
potential new site $v\notin S$. If there are constantly many sites in $S$,
then the latter is sufficient in order to solve Balanced Vertex. Indeed, by
computing $\ell_{\pi^{\prime}}(v,S^{\prime}+v)$ for all sublists $S^{\prime}$
of size one, and for some actualized cost functions $\pi^{\prime}$, we can
also compute the load $\ell_{\pi}(s,S+v)$ of every former site $s\in S$, and
therefore we can compute $L_{\pi}(S+v)$. We detail this approach in Sec. 3.3,
where it is applied to bounded treewidth graphs (Theorem 3.12). However,
solving Balanced Vertex for an arbitrary (possibly nonconstant) number of
sites looks more challenging. For $n$-node trees, we combine a standard but
rather intricate dynamic programming approach with centroid decomposition, so
as to derive an ${\cal O}(n\log{n})$-time algorithm (Theorem 3.8). The running
time can be improved to ${\cal O}(n\log{|S|})$ (see Remark 2). Our second main
contribution in this part is for proper interval graphs, for which we get an
${\cal O}(m+n\log{n})$-time algorithm (Theorem 3.16). This result is derived
from prior works on distance labeling schemes for this class of graphs [15].

#### Organization of the paper.

Basic results about the Balanced Vertex problem, along with a polynomial-time
algorithm for solving it and a matching conditional time lower bound, are
presented in Sec. 2. Faster algorithms for special graph classes are presented
in Sec. 3. We conclude the paper in Sec. 4 with some open questions and
perspectives.

#### Additional notations and terminology.

Let $G=(V,E)$ be a graph. The open neighbourhood of a vertex $v$ is denoted in
what follows by $N_{G}(v)=\\{u\in V\mid uv\in E\\}$. We denote by
$N_{G}[v]=N_{G}(v)\cup\\{v\\}$ its closed neighbourhood. The ball of center
$v$ and radius $k$ is denoted by $N_{G}^{k}[v]=\\{u\in V\mid d_{G}(u,v)\leq
k\\}$. For every vertices $u$ and $v$, let $I_{G}(u,v)=\\{w\in V\mid
d_{G}(u,v)=d_{G}(u,w)+d_{G}(w,v)\\}$ denote the metric interval between $u$
and $v$. Let $W_{G}(u,v)=\\{w\in V\mid d_{G}(u,w)<d_{G}(v,w)\\}$ contain all
vertices closer to $u$ than to $v$. In the same way, for a vertex subset $S$
(a vertex list, resp.), let $N_{G}(S)=\bigcup_{s\in S}N_{G}(s)\setminus S$ and
$N_{G}[S]=N_{G}(S)\cup S$ denote its open and closed neighbourhoods,
respectively. The subgraph induced by a subset $S$ is denoted by $G[S]$. For
every vertex subset $S$ (vertex list, resp.), let $Proj_{G}(v,S)=\\{s\in S\mid
d_{G}(v,s)=d_{G}(v,S)\\}$ be the metric projection of a vertex $v$ on $S$. We
sometimes omit the subscript if $G$ is clear from the context. A vertex list
$S=(s_{1},s_{2},\ldots,s_{p})$ such that $s_{i}\neq s_{j}$ for every $i,j$
with $1\leq i<j\leq p$ is called in what follows a proper vertex list. We
denote the territories $V_{1},V_{2},\ldots,V_{p}$ of $\mathbf{Vor}(G,S)$ by
$\mathbb{T}(s_{1},S),\ldots,\mathbb{T}(s_{p},S)$. Finally, being given a cost
function $\pi:V\to\mathbb{R}_{\geq 0}$, the cost of a vertex subset $X$ is
defined as $\pi(X)=\sum_{x\in X}\pi(x)$.

##  2 The general case

We here consider the Balanced Vertex problem on general graphs. In Sec. 2.1,
we prove a few simple properties of prioritized Voronoi diagrams. We derive
from the latter a quadratic-time algorithm, in the number of edges, for
solving Balanced Vertex. This algorithm is presented in Sec. 2.2. In Sec. 2.3,
our quadratic running time is proved to be optimal assuming the Hitting Set
Conjecture.

###  2.1 Basic properties

We start the section with some easy results on the territories in a Voronoi
diagram. In particular, we prove the following relation between territories
and metric intervals.

######  Lemma 2.1.

Let $G=(V,E)$ be a graph and let $S=(s_{1},s_{2},\ldots,s_{p})$ be a proper
vertex list. For every vertex $v\in\mathbb{T}(s_{i},S)$, with $1\leq i\leq p$,
we have $I(v,s_{i})\subseteq\mathbb{T}(s_{i},S)$.

###### Proof.

Suppose by contradiction the existence of some vertex $u\in
I(v,s_{i})\setminus\mathbb{T}(s_{i},S)$. Let $j$, with $1\leq j\leq p$, such
that $u\in\mathbb{T}(s_{j},S)$. In particular, $d(u,S)=d(u,s_{j})\leq
d(u,s_{i})$. Note that $d(v,s_{j})\leq d(v,u)+d(u,s_{j})\leq
d(v,u)+d(u,s_{i})=d(v,s_{i})=d(v,S)$. Therefore, we must have
$d(u,s_{j})=d(u,s_{i})=d(u,S)$ and $d(v,s_{i})=d(v,s_{j})=d(v,S)$. However,
because $v\in\mathbb{T}(s_{i},S)$, $j>i$, thus contradicting that
$u\in\mathbb{T}(s_{j},S)$. ∎

We immediately deduce from Lemma 2.1 the following result about territories:

######  Corollary 2.2.

Let $G=(V,E)$ be a graph and let $S=(s_{1},s_{2},\ldots,s_{p})$ be a proper
vertex list. For every $i$ with $1\leq i\leq p$, $\mathbb{T}(s_{i},S)$ is a
connected subset.

We often use in our proofs the following structural description of the last
territory in a diagram. Similar but more complicated descriptions of the other
territories can be derived from this result.

######  Lemma 2.3.

Let $G=(V,E)$ be a graph and let $S=(s_{1},s_{2},\ldots,s_{p})$ be a proper
vertex list. For every vertex $v\notin S$, we have that
$\mathbb{T}(v,S+v)=\bigcup_{1\leq j\leq
p}\left(W(v,s_{j})\cap\mathbb{T}(s_{j},S)\right)$

###### Proof.

Let $j$ with $1\leq j\leq p$ be fixed. For every vertex
$u\in\mathbb{T}(s_{j},S)$, we have that $u\in\mathbb{T}(v,S+v)$ if and only if
$d(u,v)<d(u,S)=d(u,s_{j})$. The vertices that satisfy this inequality are
exactly those of $W(v,s_{j})$. ∎

###  2.2 A quadratic-time algorithm

We present our quadratic-time algorithm for solving Balanced Vertex. It is
based on the following observation that for every proper vertex list, we can
compute the prioritized Voronoi diagram in linear time.

######  Proposition 2.4.

Let $G=(V,E)$ be a graph and let $S=(s_{1},s_{2},\ldots,s_{p})$ be a proper
vertex list. We can compute $\mathbf{Vor}(G,S)$ in ${\cal O}(n+m)$ time.

###### Proof.

We run a BFS on $S$ (i.e., we consider all vertices in $S$ as being one
supervertex, on which we run a BFS). In doing so, we order the vertices $v\in
V\setminus S$ by nondecreasing distance to $S$. Then, we compute $r(v)$, for
every vertex $v$, so that:

$r(v)=\begin{cases}v\text{, if }v\in S\\\ \min\\{r(u)\mid u\in N(v)\
\text{and}\ d(u,S)=d(v,S)-1\\}\text{ otherwise.}\end{cases}$

We prove by induction on $d(v,S)$ that $r(v)$ is the unique site of $S$ such
that $v\in\mathbb{T}(r(v),S)$. This is straightforward if $v\in S$. Thus, from
now on we assume that $d(v,S)\geq 1$. For every $u\in N(v)$, if
$d(u,S)<d(v,S)$, then by the induction hypothesis we have $r(u)\in Proj(v,S)$.
By Lemma 2.1, the unique site $s_{i}\in S$ such that $v\in\mathbb{T}(s_{i},S)$
is contained in $\\{r(u)\mid u\in N(v)\ \text{and}\ d(u,S)=d(v,S)-1\\}$.
Therefore, $r(v)=s_{i}$. ∎

In order to solve Balanced Vertex, it is sufficient to compute all prioritized
Voronoi diagrams with one more site. We summarize our observations as follows.

######  Theorem 2.5.

We can solve Balanced Vertex in ${\cal O}(nm)$ time.

###### Proof.

For every vertex $v\in V\setminus S$, we compute $\mathbf{Vor}(G,S+v)$. By
Proposition 2.4, this computation takes ${\cal O}(n+m)$ time. Furthermore, we
can compute $L_{\pi}(S+v)$ in additional ${\cal O}(n)$ time if we scan each
territory of $\mathbf{Vor}(G,S+v)$ sequentially. The running time follows
since there are at most $n$ vertices $v$ to be considered. ∎

###  2.3 HS-hardness

Our main technical contribution in this section is a conditional time lower
bound for Balanced Vertex, which matches the quadratic running time of the
simple algorithm presented in Theorem 2.5. Our hardness result is based on the
following hypothesis.

######  Conjecture 1 (The Hitting Set Conjecture [1]).

There is no $\varepsilon>0$ such that for all $c\geq 1$, there is an algorithm
that given two lists $A,B$ of $n$ subsets of a universe $U$ of size at most
$c\log{n}$, can decide in ${\cal O}(n^{2-\varepsilon})$ time if there is a set
in the first list that intersects every set in the second list, i.e., a
“hitting set”.

In what follows, we call the triple $(A,B,U)$ a HS-instance. Two HS-instances
$(A,B,U)$ and $(A^{\prime},B^{\prime},U^{\prime})$ are called equivalent if
either both contain a hitting set or none of them does.

Insofar, the Hitting Set Conjecture has been understudied. We next present
reductions from arbitrary HS-instances to equivalent ones with some more
structure (Lemmas 2.6 and 2.7). The running times of these reductions are
roughly linear in the cumulative cardinalities of all subsets in the input,
which (since there are $2n$ such subsets and the universe has size ${\cal
O}(\log{n})$) is in ${\cal O}(n\log{n})$.

######  Lemma 2.6.

Every HS-instance $(A,B,U)$ can be reduced in ${\cal O}(n\log{n})$ time to
some equivalent HS-instance $(A^{\prime},B^{\prime},U^{\prime})$ with the
following additional property: every set in $B^{\prime}$ intersects at most
half of the sets in $B^{\prime}$.

###### Proof.

Let $(A_{0},B_{0},U_{0})$ and $(A_{1},B_{1},U_{1})$ be disjoint copies of
$(A,B,U)$. Let also $x_{0},x_{1}\notin U_{0}\cup U_{1}$. We set:

$\displaystyle A^{\prime}$ $\displaystyle=\\{a_{0}\cup U_{1}\mid a_{0}\in
A_{0}\\}\cup\\{a_{1}\cup U_{0}\mid a_{1}\in A_{1}\\},$ $\displaystyle
B^{\prime}$ $\displaystyle=\\{b_{0}\cup\\{x_{0}\\}\mid b_{0}\in
B_{0}\\}\cup\\{b_{1}\cup\\{x_{1}\\}\mid b_{1}\in B_{1}\\},$ $\displaystyle
U^{\prime}$ $\displaystyle=U_{0}\cup U_{1}\cup\\{x_{0},x_{1}\\}.$

The construction of $(A^{\prime},B^{\prime},U^{\prime})$ takes ${\cal
O}(n\log{n})$ time.

We can bipartition $B^{\prime}$ in two sublists
$B_{0}^{\prime},B_{1}^{\prime}$ such that, for every $i\in\\{0,1\\}$, all sets
in $B_{i}^{\prime}$ contain $x_{i}$ and are contained in
$U_{i}\cup\\{x_{i}\\}$. Since $U_{0}\cup\\{x_{0}\\}$ and
$U_{1}\cup\\{x_{1}\\}$ are disjoint, every set of $B^{\prime}$ intersects
exactly half of the sets of $B^{\prime}$. Furthermore, if $a\in A$ is a
hitting set for $(A,B,U)$, then let $a_{0},a_{1}$ be its copies in
$A_{0},A_{1}$. By construction, $a_{0}\cup U_{1}$ and $a_{1}\cup U_{0}$ are
hitting sets for $(A^{\prime},B^{\prime},U^{\prime})$. Conversely, let
$a^{\prime}\in A^{\prime}$ be a hitting set for
$(A^{\prime},B^{\prime},U^{\prime})$. By symmetry, we may assume to have
$a^{\prime}=a_{0}\cup U_{1}$, for some set $a_{0}\in A_{0}$. Since
$x_{0}\notin a^{\prime}$ and, for every set $b_{0}\in B_{0}$, $b_{0}\cap
U_{1}=\emptyset$, we must have $a_{0}$ is a hitting set for
$(A_{0},B_{0},U_{0})$. In particular, there is also a hitting set for
$(A,B,U)$. ∎

We only need to apply the following reduction with $\alpha=2,\ \beta=-1$ for
proving Theorem 2.8. However, the general case with $\alpha,\beta$ arbitrary
might be useful for future works on the Hitting Set Conjecture.

######  Lemma 2.7.

Let $\alpha,\beta$ be arbitrary integers so that $\alpha\geq 2$. Every HS-
instance $(A,B,U)$ can be reduced in ${\cal O}(n\log{n})$ time to some
equivalent HS-instance $(A^{\prime},B,U^{\prime})$ with the following
additional properties: for some $t={\cal O}(|U|)$, the universe $U^{\prime}$
has cardinality $\alpha\cdot t+\beta$, and every set in $A^{\prime}$ has
cardinality $t$.

###### Proof.

First, we reduce $(A,B,U)$ to some equivalent instance
$(A_{\text{tmp}},B,U_{\text{tmp}})$ so that all sets in $A_{\text{tmp}}$ have
equal cardinality. Then, we reduce $(A_{\text{tmp}},B,U_{\text{tmp}})$ to our
final HS-instance $(A^{\prime},B,U^{\prime})$.

In order to construct $(A_{\text{tmp}},B,U_{\text{tmp}})$, we start computing
the extreme cardinalities $\Delta=\max\\{|a|\mid a\in A\\}$ and
$\delta=\min\\{|a|\mid a\in A\\}$ of sets in $A$. Let
$U_{\text{dummy}}=\\{u_{1},u_{2},\ldots,u_{\Delta-\delta}\\}$ be a universe of
cardinality $\Delta-\delta$ that is disjoint from $U$. We set
$U_{\text{tmp}}=U\cup U_{\text{dummy}}$. For every set $a\in A$, we add in
$A_{\text{tmp}}$ the set $a\cup\\{u_{1},u_{2},\ldots,u_{\Delta-|a|}\\}$.

Let every set in $A_{\text{tmp}}$ have cardinality $\Delta$. In order to
construct $(A^{\prime},B^{\prime},U^{\prime})$, there are two different cases
to be considered.

  * •

Case $\alpha\cdot\Delta+\beta>|U_{\text{tmp}}|$. We complete $U_{\text{tmp}}$
with $\alpha\cdot\Delta+\beta-|U_{\text{tmp}}|$ new elements in order to
create $U^{\prime}$. The two lists are unchanged (i.e., we set
$A^{\prime}=A_{\text{tmp}}$, $B^{\prime}=B$).

  * •

Case $\alpha\cdot\Delta+\beta<|U_{\text{tmp}}|$. Let us write
$|U_{\text{tmp}}|-\alpha\cdot\Delta-\beta=q\cdot(\alpha-1)+r$ for some unique
$q\geq 0$ and $r\in\\{0,1,\ldots,\alpha-2\\}$. Let $X,Y$ be disjoint universes
of respective cardinalities $\alpha-1-r$ and $q+1$, both disjoint from
$U_{\text{tmp}}$. We set $U^{\prime}=U_{\text{tmp}}\cup X\cup Y$,
$A^{\prime}=\\{a\cup Y\mid a\in A_{\text{tmp}}\\}$, $B^{\prime}=B$. Doing so,
every set in $A^{\prime}$ has cardinality equal to $t=\Delta+q+1$, while the
universe $U^{\prime}$ has cardinality:

$\displaystyle|U_{\text{tmp}}|+|X|+|Y|$
$\displaystyle=\alpha\cdot\Delta+\beta+(|U_{\text{tmp}}|-\alpha\cdot\Delta-\beta)+(q+1)+(\alpha-1-r)$
$\displaystyle=\alpha\cdot\Delta+\beta+(q\cdot(\alpha-1)+r)+q+\alpha-r$
$\displaystyle=\alpha\cdot\Delta+\beta+q\cdot\alpha+\alpha$
$\displaystyle=\alpha\cdot(\Delta+q+1)+\beta$ $\displaystyle=\alpha\cdot
t+\beta$

In both cases, our construction ensures that every set in $A^{\prime}$ has
cardinality $\frac{|U^{\prime}|-\beta}{\alpha}$. ∎

We are now ready to combine both reductions in order to prove our main result
in this part.

######  Theorem 2.8.

Assuming Conjecture 1, there is no $\varepsilon>0$ such that for all $c\geq
1$, there is an algorithm that solves Balanced Vertex in ${\cal
O}(n^{2-\varepsilon})$ time on the $n$-vertex graphs with at most $cn\log{n}$
edges.

###### Proof.

Let $(A,B,U)$ be any HS-instance with the following properties:

  1. 1.

every set of $B$ intersects at most half of the sets in $B$;

  2. 2.

every set of $A$ has cardinality $\frac{|U|+1}{2}$.

We stress that every HS-instance can be reduced to an equivalent one with
these properties by applying the reductions of Lemma 2.6 and 2.7, in this
order. Intuitively, we identify the subsets of $A\cup B$ and the elements of
$U$ with vertices in some graph $G$ (to be defined later). We further define a
unique site $s$, which is close to every vertex in $A$ but distant to every
vertex in $B$. Therefore, in order to minimize the load, one should pick a new
site which is closer than $s$ to every vertex in $B$. At first glance, one may
think about picking some new site in $U$. However, the vertices in $U$ are
closer than $s$ to far too many vertices, thus making the load increase. The
first property above ensures that no vertex of $B$ should be picked either.
Therefore, we are left picking (if any) a vertex of $A$ that is close to every
vertex of $B$, a.k.a., a hitting set. Note that in general, the exact load
should also depend on the size of $U$ and the cardinality of the hitting set.
The second property above ensures that it is not the case for our reduction.

For convenience, in what follows let $t=\frac{|U|+1}{2}$ denote the
cardinality of every set in $A$. We may further assume that $t>2$ (otherwise,
we can detect a hitting set in ${\cal O}(n)$ time because there are ${\cal
O}(1)$ distinct sets in $A$). We construct a graph $G=(V,E)$ with
$2n+|U|+3=2(n+t+1)$ vertices, as follows:

  * •

$V=A\cup B\cup U\cup\\{s,x,y\\}$;

  * •

$U\cup\\{x,y\\}$ is a clique;

  * •

$N_{G}(s)=\\{x,y\\}$;

  * •

for every set $a\in A$, $N_{G}(a)=\\{y\\}\cup\\{u\in U\mid u\in a\\}$;

  * •

for every set $b\in B$, $N_{G}(b)=\\{u\in U\mid u\in b\\}$.

$a$$s$$x$$y$$A$$U$$B$ Figure 2: The reduction of Theorem 2.8. For clarity of
the picture, we omitted the edges between vertices of $U$ and the edges
between $U$ and $A\setminus\\{a\\}$, with $a$ some hitting set.

See Fig. 2 for an illustration. Let $S=(s)$ and let $\pi:V\to\mathbb{R}_{\geq
0}$ be the all-one function (i.e., $\pi(v)=1$ for every vertex $v$). Being
given a vertex $v\neq s$, let $S_{v}=(s,v)$. By Lemma 2.3,
$\mathbb{T}(v,S_{v})=W_{G}(v,s)$. We now compute the load of $S_{v}$ for every
vertex $v\neq s$:

  * •

Case $v=x$. We have $W(x,s)=U\cup\\{x\\}\cup B$. Then,
$L_{\pi}(S_{x})=\ell_{\pi}(x,S_{x})=n+1+|U|=n+2t$.

  * •

Case $v=y$. We have $W(y,s)=V\setminus\\{s,x\\}$. Then,
$L_{\pi}(S_{y})=\ell_{\pi}(y,S_{y})=2n+|U|+1=2(n+t)$.

  * •

Case $v\in U$. We have $U\cup B\subseteq W(v,s)$. Then,
$L_{\pi}(S_{v})=\ell_{\pi}(v,S_{v})\geq n+|U|=n+2t-1$.

  * •

Case $v\in B$. Since every vertex of $A$ is at distance at least two from
vertex $v$, $A\cap W(v,s)=\emptyset$. Furthermore, $|W(v,s)\cap B|\leq|B|/2$.
We also know that $s,x,y\notin W(v,s)$. As a result, we have
$L_{\pi}(S_{v})=\ell_{\pi}(s,S_{v})\geq|A|+|B|/2+3=3n/2+3$.

  * •

Case $v\in A$. We have $W(v,s)=\\{v\\}\cup\left(N_{G}(v)\cap
U\right)\cup\left(N_{G}^{2}[v]\cap B\right)$. Let us write
$k=|N_{G}^{2}[v]\cap B|$. In this situation, $\ell_{\pi}(v,S_{v})=k+t+1$ while
$\ell_{\pi}(s,S_{v})=2n-k+t+1$. In particular, $L_{\pi}(S_{v})$ is minimal if
and only if $k=n$, that is if and only if $v$ is a hitting set.

As a result, the existence of some vertex $v$ such that $L_{\pi}(S_{v})\leq
n+t+1$ is equivalent to that of a hitting set for $(A,B,U)$. ∎

######  Remark 1.

The hardness result of Theorem 2.8 holds for unit costs and $|S|=1$.

##  3 Almost linear-time algorithms

In this section, we break the quadratic barrier for Balanced Vertex on various
graph classes. We obtain a linear-time algorithm only for simple topologies,
see Sec. 3.1. Nevertheless, we achieve an almost linear-time computation on
trees (Sec. 3.2), proper interval graphs (Sec. 3.4) and bounded-treewidth
graphs with a constant number of sites (Sec. 3.3).

###  3.1 Simple cases

First, we present a complete dichotomy of the parameterized complexity of
Balanced Vertex if the parameter is the diameter of the graph. The graphs of
unit diameter are exactly the complete graphs. Being given a proper vertex
list $S$ in such graph, every vertex of $V\setminus S$ must belong to the
territory of the site in $S$ with the highest priority. We deduce from this
observation a simple linear-time algorithm for Balanced Vertex on complete
graphs.

######  Lemma 3.1.

We can solve Balanced Vertex in ${\cal O}(n)$ time if $G$ is a clique.

###### Proof.

Let $\Lambda=\pi(G)-\sum_{i=2}^{p}\pi(s_{i})$. It suffices to output a vertex
$v\notin S$ such that $\max\\{\pi(v),\Lambda-\pi(v)\\}$ is minimized. Indeed,
since $G$ is a clique we have the following for every vertex $v\notin S$:
$\mathbb{T}(s_{1},S+v)=V\setminus\\{s_{2},s_{3},\ldots,s_{p},v\\}=\mathbb{T}(s_{1},S)\setminus\\{v\\}$;
$\mathbb{T}(s_{i},S+v)=\\{s_{i}\\}=\mathbb{T}(s_{i},S)$ for every $i$ with
$2\leq i\leq p$; $\mathbb{T}(v,S+v)=\\{v\\}$. In particular, we have
$L_{\pi}(S+v)=\max\\{\pi(s_{i})\mid 2\leq i\leq
p\\}\cup\\{\pi(v),\Lambda-\pi(v)\\}$. ∎

We now generalize the simple idea behind Lemma 3.1 to the graphs of diameter
two.

######  Lemma 3.2.

We can solve Balanced Vertex in ${\cal O}(n+m)$ time if $G$ has diameter two.

###### Proof.

We compute $\mathbf{Vor}(G,S)$, which by Proposition 2.4 we can do in ${\cal
O}(n+m)$ time. Doing so, we can compute in ${\cal O}(n)$ time the values
$\ell_{\pi}(s_{i},S)$, for every $i$ with $1\leq i\leq p$. We can also compute
in ${\cal O}(n)$ time, for every $i$ with $1\leq i\leq p$, the value $\mu_{i}$
such that:

$\mu_{i}=\begin{cases}\max\\{\ell_{\pi}(s_{2},S),\ell_{\pi}(s_{3},S),\ldots,\ell_{\pi}(s_{p},S)\\}\
\text{if}\ i=1\\\ \max\\{\ell_{\pi}(s_{j},S)\mid
j\in\\{2,3,\ldots,p\\}\setminus\\{i\\}\\}\ \text{otherwise.}\end{cases}$

For every vertex $v\notin S$, let $s_{i}$ be the unique site of $S$ such that
$v\in\mathbb{T}(s_{i},S)$. Note that we can compute $s_{i}$ from
$\mathbf{Vor}(G,S)$ in ${\cal O}(1)$ time. We compute the value $\lambda(v)$
such that:

$\lambda(v)=\begin{cases}\max\left\\{\pi\left(N(v)\setminus
N[S]\right)+\pi(v),\ell_{\pi}(s_{1},S)-\pi\left(N(v)\setminus
N[S]\right)-\pi(v),\mu_{1}\right\\}\ \text{if}\ i=1\\\
\max\left\\{\pi\left(N(v)\setminus
N[S]\right)+\pi(v),\ell_{\pi}(s_{1},S)-\pi\left(N(v)\setminus
N[S]\right),\ell_{\pi}(s_{i},S)-\pi(v),\mu_{i}\right\\}\
\text{otherwise.}\end{cases}$

Since we precomputed all values $\mu_{1},\mu_{2},\ldots,\mu_{p}$, we can
compute the values $\lambda(v)$, for every $v\notin S$, in ${\cal O}(n+m)$
time, simply by scanning the neighbourhoods of every vertex. Finally, we
output a vertex $v\notin S$ such that $\lambda(v)$ is minimized. Indeed, we
claim that $\lambda(v)=L_{\pi}(S+v)$. This is because we assume the diameter
of $G$ to be two, and therefore $\mathbb{T}(s_{j},S)\subseteq N[s_{j}]$ for
every $j$ with $2\leq j\leq p$. In particular, we have:

$W_{G}(v,s_{j})\cap\mathbb{T}(s_{j},S)=\begin{cases}\\{v\\}\ \text{if}\
v\in\mathbb{T}(s_{j},S)\\\ \emptyset\ \text{otherwise.}\end{cases}$

In the former case, $\ell_{\pi}(s_{j},S+v)=\ell_{\pi}(s_{j},S)-\pi(v)$, while
in the latter case $\ell_{\pi}(s_{j},S+v)=\ell_{\pi}(s_{j},S)$. Furthermore,
$\mathbb{T}(v,S+v)=\\{v\\}\cup\left(N(v)\setminus N[S]\right)$, and so,
$\ell_{\pi}(v,S+v)=\pi\left(N(v)\setminus N[S]\right)+\pi(v)$. Finally,

$W_{G}(v,s_{1})\cap\mathbb{T}(s_{1},S)=\begin{cases}\\{v\\}\cup\left(N(v)\setminus
N[S]\right)\ \text{if}\ v\in\mathbb{T}(s_{1},S)\\\ N(v)\setminus N[S]\
\text{otherwise.}\end{cases}$

Altogether combined, we obtain as claimed that $\lambda(v)=L_{\pi}(S+v)$. ∎

We cannot extend Lemmas 3.1 and 3.2 any further because the graph constructed
in the proof of Theorem 2.8 has diameter three. Therefore, we can solve
Balanced Vertex in linear time if the diameter is at most two, while we cannot
solve this problem in truly subquadratic time if the diameter is at least
three.

Next, we consider paths and cycles. The problem becomes local, in the
following sense. Let us subdivide a path $G$ in maximal subpaths whose every
end is either a site of $S$ or one of the two ends of $G$. See Fig. 3 for an
illustration. Doing so, we can prove that there are at most two sites of $S$
whose territory may be modified upon inserting a new site $v$, namely, those
at the ends of the maximal subpath containing $v$. In particular, we can
compute the load $L_{\pi}(S+v)$, for every node $v\notin S$, by applying to
every maximal subpath a classical partial sum trick for vector problems.

$\pi$:$\lambda(i,j)$:$1$$19$$3$$5$$1$$1$$0$$2$$1$$1$$1$$4$$10$$1$$20$$23$$28$$2$$2$$3$$4$$5$$9$$s_{1}$$s_{3}$$s_{2}$$P_{1}$$P_{2}$$P_{3}$
Figure 3: Subdivision of a path $G$ in maximal subpaths with respect to the
sites in $S$.

######  Lemma 3.3.

We can solve Balanced Vertex in ${\cal O}(n)$ time if $G$ is a path.

###### Proof.

We first describe our algorithm. See Fig. 3 for an illustration.

  1. 1.

We compute $\mathbf{Vor}(G,S)$ and the loads $\ell_{\pi}(s_{j},S)$, for every
$j$ with $1\leq j\leq p$.

  2. 2.

Let $C_{1},C_{2},\ldots,C_{q}$ be the connected components of $G\setminus S$.
Note that we have $q\leq p+1$. For every $i$ with $1\leq i\leq q$, let
$S_{i}=N(C_{i})$, and let $P_{i}$ be the subpath induced by
$N[C_{i}]=C_{i}\cup S_{i}$. We stress that $|S_{i}|=2$, except maybe if
$i\in\\{1,q\\}$ for which we may have $|S_{i}|=1$.

  3. 3.

We consider each subpath $P_{i}$, with $1\leq i\leq q$, sequentially. In what
follows, let $P_{i}=(w_{0}^{i},w_{1}^{i},\ldots,w_{t_{i}-1}^{i})$.

     * •

We compute $\Lambda_{i}=\max_{s\in S\setminus S_{i}}\ell_{\pi}(s,S)$.

     * •

We compute $\lambda(i,j)=\sum_{k=0}^{j}\pi(w_{k}^{i})$, for every $k$ with
$0\leq k<t_{i}$.

Then, there are two different cases to be considered.

    1. (a)

Case $|S_{i}|=1$. Either $i=1,\ w_{0}^{1}\notin S_{1}$ or $i=q,\
w_{t_{q}-1}^{q}\notin S_{q}$. We observe that both subcases are symmetric up
to reverting the path $G$. Therefore, we assume without loss of generality
that $i=1,\ w_{0}^{1}\notin S_{1}$. In this situation, $w_{0}^{1}$ is the
leftmost end of path $G$, and $S_{1}=\\{w_{t_{1}-1}^{1}\\}$. For every $j$
with $0\leq j<t_{1}-1$, let
$j_{R}=\left\lceil\frac{t_{1}-1+j}{2}\right\rceil-1$. We compute:

$\Lambda(v)=\max\\{\Lambda_{1},\lambda(1,j_{R}),\ell_{\pi}(w_{t_{1}-1}^{1},S)-\lambda(1,j_{R})\\}$

    2. (b)

Case $|S_{i}|=2$. We first compute $j^{i}_{\lim}=\max\\{j\mid 0\leq
j<\ell_{i},\ w_{j}^{i}\in\mathbb{T}(w_{0}^{i},S)\\}$. Then, we consider each
node of $C_{i}$ sequentially. In what follows, let $j$ with $0<j<t_{i}-1$. Let
$j_{L}=\left\lfloor\frac{j}{2}\right\rfloor+1$, and let
$j_{R}=\left\lceil\frac{t_{1}-1+j}{2}\right\rceil-1$. We compute:

$\displaystyle\Lambda(v)=\max\\{$
$\displaystyle\Lambda_{i},\lambda(i,j_{R})-\lambda(i,j_{L}-1),$
$\displaystyle\ell_{\pi}(w_{0}^{i},S)-\lambda(i,j_{\lim}^{i})+\lambda(i,j_{L}-1),$
$\displaystyle\ell_{\pi}(w_{t_{i}-1}^{i},S)-\lambda(i,j_{R})+\lambda(i,j_{\lim}^{i})\\}$

  4. 4.

Finally, we output a node $v\notin S$ such that $\Lambda(v)$ is minimized.

Complexity. By Proposition 2.4, Step $1$ of the algorithm can be done in
${\cal O}(n)$ time. Step $2$ can be also done in ${\cal O}(n)$ time.
Furthermore, since we have $|S_{i}|\leq 2$ for every $i$ with $1\leq i\leq q$,
we can compute all values $\Lambda_{1},\Lambda_{2},\ldots,\Lambda_{q}$ in
${\cal O}(n)$ time, simply by keeping track of the $\max\\{3,p\\}$ nodes of
$S$ with maximum load. Let $i$ with $1\leq i\leq q$ be fixed. By dynamic
programming, we compute in ${\cal O}(t_{i})$ time the values $\lambda(i,j)$,
for every $j$ with $0\leq j\leq t_{i}-1$. Then, we can compute in ${\cal
O}(t_{i})$ time the values $\Lambda(v)$, for every $v\in C_{i}$, simply by
scanning once the path $P_{i}$ and performing ${\cal O}(1)$ operations for
each node. Since we have $\sum_{i=1}^{q}t_{i}={\cal O}(n)$, the total running
time for Step $3$ is also in ${\cal O}(n)$.

Correctness. Let $i$ be such that $1\leq i\leq q$, and let $v\in C_{i}$ be
arbitrary. We prove in what follows that $\Lambda(v)=L_{\pi}(S+v)$. First we
claim that $C_{i}\cup S_{i}\subseteq\bigcup\\{\mathbb{T}(s,S)\mid s\in
S_{i}\\}$. Indeed, suppose by contradiction that some node $u\in C_{i}$
belongs to $\mathbb{T}(s^{\prime},S)$, for some $s^{\prime}\in S\setminus
S_{i}$. The unique $us^{\prime}$-path intersects $S_{i}$, which by Lemma 2.1
implies that $\mathbb{T}(s^{\prime},S)\cap S_{i}\neq\emptyset$, a
contradiction. In the same way, we have $\mathbb{T}(v,S+v)\subseteq
C_{i}\subseteq\bigcup\\{\mathbb{T}(x,S+v)\mid x\in S_{i}\cup\\{v\\}\\}$. This
implies that for every $s\in S_{i}$ we have $\mathbb{T}(s,S+v)\setminus
C_{i}=\mathbb{T}(s,S)\setminus C_{i}$, while for every $s^{\prime}\in
S\setminus S_{i}$, we have
$\mathbb{T}(s^{\prime},S)=\mathbb{T}(s^{\prime},S+v)$. Hence, we obtain:

$\displaystyle L_{\pi}(S+v)$ $\displaystyle=\max\\{\ell_{\pi}(x,S+v)\mid x\in
S_{i}\cup\\{v\\}\\}\cup\\{\ell_{\pi}(s^{\prime},S+v)\mid s^{\prime}\in
S\setminus S_{i}\\}$
$\displaystyle=\max\\{\Lambda_{i}\\}\cup\\{\ell_{\pi}(x,S+v)\mid x\in
S_{i}\cup\\{v\\}\\}$

Clearly, $\mathbb{T}(v,S+v)=\\{u\in C_{i}\mid d(u,v)<d(u,S_{i})\\}$. Let $j$
with $0\leq j\leq t_{1}-1$ and $v=w_{j}^{i}$. There are two cases to be
considered:

  * •

Case $|S_{i}|=1$. By symmetry, we may further assume $i=1,\ w_{0}^{1}\notin
S_{1}$. Then, $C_{1}\subseteq\mathbb{T}(w_{t_{1}-1}^{1},S)$, and by Lemma 2.3
we have
$\mathbb{T}(v,S+v)=W(v,w_{t_{1}-1}^{1})=\\{w_{0}^{1},w_{1}^{1},\ldots,w_{j_{R}}^{1}\\}$.
In particular,
$\ell_{\pi}(v,S+v)=\sum_{k=0}^{j_{R}}\pi(w_{k}^{1})=\lambda(1,j_{R})$, and so
$\ell_{\pi}(w_{t_{1}-1}^{1},S+v)=\ell_{\pi}(w_{t_{1}-1}^{1},S)-\lambda(1,j_{R})$.

  * •

Case $|S_{i}|=2$. In this situation,
$\mathbb{T}(v,S+v)=\\{w_{j_{L}}^{i},w_{j_{L}+1}^{i},\ldots,w_{j_{R}}^{i}\\}$.
Therefore,
$\ell_{\pi}(v,S+v)=\sum_{k=j_{L}}^{j_{R}}\pi(w_{k}^{i})=\lambda(i,j_{R})-\sum_{k=0}^{j_{L}-1}\pi(w_{k}^{i})=\lambda(i,j_{R})-\lambda(i,j_{L}-1)$.
By the definition of $j_{\lim}^{i}$ we have $\mathbb{T}(w_{0}^{i},S)\cap
C_{i}=\\{w_{1}^{i},\ldots,w_{j_{\lim}^{i}}^{i}\\}$ while
$\mathbb{T}(w_{t_{i}-1}^{i},S)\cap
C_{i}=\\{w_{j_{\lim}^{i}+1}^{i},\ldots,w_{t_{i}-2}^{i}\\}$.

Furthermore, we claim that $j_{L}-1\leq j_{\lim}^{i}\leq j_{R}$. Indeed, let
us first assume that $j\leq j_{\lim}^{i}$. In particular, $j_{L}-1\leq j\leq
j_{\lim}^{i}$. For every $k$ with $j\leq k\leq j_{\lim}^{i}$, we have
$d(v,w_{k}^{i})<d(w_{t_{i}-1}^{i},w_{k}^{i})$, which follows from
$d(w_{0}^{i},w_{k}^{i})\leq d(w_{t_{i}-1}^{i},w_{k}^{i})$ and $v$ is on the
$w_{0}^{i}w_{k}^{i}$-path. Therefore, $j_{\lim}^{i}\leq j_{R}$. From now on,
we assume that $j_{\lim}^{i}<j$. In particular, $j_{\lim}^{i}<j_{R}$. For
every $k$ with $j_{\lim}^{i}<k\leq j$, we have
$d(v,w_{k}^{i})<d(w_{0}^{i},w_{k}^{i})$, which follows from
$d(w_{0}^{i},w_{k}^{i})\geq d(w_{t_{i}-1}^{i},w_{k}^{i})$ and $v$ is on the
$w_{t_{i}-1}^{i}w_{k}^{i}$-path. Therefore, $j_{L}\leq j_{\lim}^{i}+1$.

As a result,

$\displaystyle\ell_{\pi}(w_{0}^{i},S+v)$
$\displaystyle=\ell_{\pi}(w_{0}^{i},S)-\sum_{k=j_{L}}^{j_{\lim}^{i}}\pi(w_{k}^{i})$
$\displaystyle=\ell_{\pi}(w_{0}^{i},S)-\left(\lambda(i,j_{\lim}^{i})-\lambda(i,j_{L}-1)\right)$

and

$\displaystyle\ell_{\pi}(w_{t_{i}-1}^{i},S+v)$
$\displaystyle=\ell_{\pi}(w_{t_{i}-1}^{i},S)-\sum_{k=j_{\lim}^{i}+1}^{j_{R}}\pi(w_{k}^{i})$
$\displaystyle=\ell_{\pi}(w_{t_{i}-1}^{i},S)-\left(\lambda(i,j_{R})-\lambda(i,j_{\lim}^{i})\right)$

Overall, we proved that in both cases $\Lambda(v)=L_{\pi}(S+v)$. Therefore,
the algorithm is correct. ∎

Up to slight adjustments (e.g., in the special case where $|S|=1$), we can
directly apply to cycles our techniques for paths. We prove it below.

######  Lemma 3.4.

We can solve Balanced Vertex in ${\cal O}(n)$ time if $G$ is a cycle.

###### Proof.

Let us first assume that $p=|S|=1$. Let $(v_{0},v_{1},\ldots,v_{n-1})$ be a
cyclic ordering of the vertices, and let us assume without loss of generality
that $S=(v_{0})$. We compute by dynamic programming the values
$\lambda(j)=\sum_{k=0}^{j}\pi(v_{k})$, for every $j$ with $1\leq j<n$. It
takes ${\cal O}(n)$ time. By symmetry, we only consider in what follows the
vertices $v_{i}$ with $0<i\leq n/2$. In this situation, by Lemma 2.3,

$\mathbb{T}(v_{i},S+v_{i})=W(v_{i},v_{0})=\\{v_{\left\lfloor\frac{i}{2}\right\rfloor+1},v_{\left\lfloor\frac{i}{2}\right\rfloor+2},\ldots,v_{\left\lceil\frac{n-i}{2}\right\rceil-1}\\}.$

Let
$\ell_{i}=\lambda(\left\lceil\frac{n-i}{2}\right\rceil-1)-\lambda(\left\lfloor\frac{i}{2}\right\rfloor)$.
Note that $L_{\pi}(S+v_{i})=\max\\{\ell_{i},\pi(G)-\ell_{i}\\}$. Therefore, it
suffices to output a vertex $v_{i}$ with $1\leq i\leq n/2$ and such that
$\max\\{\ell_{i},\pi(G)-\ell_{i}\\}$ is minimized. The running time is in
${\cal O}(n)$.

From now on, we assume that $p=|S|>1$. We compute $\mathbf{Vor}(G,S)$ and the
loads $\ell_{\pi}(s_{j},S)$, for every $j$ with $1\leq j\leq p$. By
Proposition 2.4, this can be done in ${\cal O}(n)$ time. Let
$C_{1},C_{2},\ldots,C_{q}$ be the connected components of $G\setminus S$. For
every $i$ with $1\leq i\leq q$, let $S_{i}=N(C_{i})$, and let $P_{i}$ be the
subpath induced by $N[C_{i}]=C_{i}\cup S_{i}$. Note that the two vertices of
$S_{i}$ are the two ends of $P_{i}$. We are done applying the exact same
procedure for each subpath $P_{i}$ as in Lemma 3.3 (Step $3$ of the algorithm
for paths). The running time is in ${\cal O}(n)$. Correctness follows from the
exact same arguments as in the proof of Lemma 3.3, and it is even simpler
because the case $|S_{i}|=1$ cannot occur. ∎

###  3.2 Trees

We now address the case of general trees. Unlike for paths, the number of
former sites in $S$ whose territory is modified after insertion of a new site
may be arbitrarily large. See Fig. 4 for an illustration. Fortunately, we can
use centroid decomposition in order to compute, for every $v\notin S$, a set
of ${\cal O}(\log{n})$ nodes that are on the paths between $v$ and the
territories of all but ${\cal O}(\log{n})$ former sites in $S$. More
precisely, being given a tree $T$, we can summarize our strategy as follows:

  1. 1.

We compute a centroid, i.e. a node $c$ such that every connected component of
$T\setminus\\{c\\}$ contains at most $n/2$ nodes.

  2. 2.

We process the unique site $s_{i}\in S$ such that $c\in\mathbb{T}(s_{i},S)$
(see Lemma 3.5);

  3. 3.

We process all sites $s_{j}$ whose territories are on different connected
components of $T\setminus\\{c\\}$ than $v$ (see Lemmas 3.6 and 3.7);

  4. 4.

Finally, we recursively apply our strategy in order to process all remaining
sites whose territories are on the same connected component of
$T\setminus\\{c\\}$ as $v$.

$v$$\ldots$$s_{1}$$s_{2}$$s_{3}$$s_{4}$ Figure 4: Beginning of the
construction of a tree with $p$ former sites in $S$ and ${\cal O}(p^{2})$
nodes. There is a central path with $p$ nodes whose first node is $v$. Each
former site $s_{i}$, with $2\leq i\leq p$, is connected to the central path by
a path of length $3i+1$. The thick edges represent the paths between the new
site $v$ and every node in its territory. In particular, for every $i$ with
$2\leq i\leq p$, exactly one node is removed from the territory of $s_{i}$.

######  Lemma 3.5.

Let $s$ be an arbitrary node in a tree $T=(V,E)$. Let
$\pi:V\to\mathbb{R}_{\geq 0}$ be any cost function. We can compute
$\alpha(v)=\pi\left(W(v,s)\right)$, for every node $v\in V$, in ${\cal O}(n)$
time.

###### Proof.

We root $T$ at $s$. Then, we preprocess $T$ in ${\cal O}(n)$ time so that the
following holds for every node $v$:

  * •

We store $d_{T}(v,s)$ — the level of node $v$;

  * •

We store $\pi(T_{v})$ — the cost of all nodes in the subtree $T_{v}$ rooted at
$v$;

  * •

For every $i$ with $0\leq i\leq d_{T}(v,s)$, we can compute the $i^{th}$-level
ancestor of $v$ in ${\cal O}(1)$ time [5].

We consider each node $v\in V$ sequentially. Let $d_{T}(v,s)=2q+\varepsilon$,
with $\varepsilon\in\\{0,1\\}$. In this situation, $W(v,s)=T_{x}$, with $x$
the $(q+1)^{th}$-level ancestor of $v$. In particular, we can compute $x$, and
so, $\pi(T_{x})=\alpha(v)$, in ${\cal O}(1)$ time. Overall, the total running
time is in ${\cal O}(n)$. ∎

Let $c$ be an arbitrary cut-vertex in a tree $T$ (in our Theorem 3.8, this
node $c$ will always be a centroid of the tree). The next two lemmas allow us
to process, for all potential locations $v$ for a new site, all former sites
in $S$ whose territory is disconnected from $v$ in $T\setminus\\{c\\}$. In
particular, using Lemma 3.6 we can compute the cost of all nodes in those
territories that are closer to $v$ than to $S$ (and so, that would end up in
$v$’s territory). Using Lemma 3.7, we can compute the maximum load of those
sites in the Voronoi diagram of $T$ with respect to $S+v$.

######  Lemma 3.6.

Let $c$ be an internal node in a tree $T=(V,E)$, and let $S$ be a proper
vertex list. We can compute $\beta(v)=\sum\\{\pi(x)\mid c\in I(v,x)\
\text{and}\ d(x,v)<d(x,S)\\}$, for every node $v\in V\setminus\\{c\\}$, in
${\cal O}(n)$ time.

###### Proof.

Let us first describe our algorithm:

  1. 1.

In ${\cal O}(n)$ time, we compute $d(x,S)$ and $d(x,c)$ for every node $x$.

  2. 2.

For every $i$ with $0\leq i\leq n$, we compute $a[i]=\sum\\{\pi(x)\mid
d(x,c)+i<d(x,S)\\}$. For that, we start computing $b[j]=\sum\\{\pi(x)\mid
d(x,S)=d(x,c)+j\\}$, for every $j$ with $0\leq j\leq n$, simply by scanning
once all nodes $x$. Since $a[i]=\sum_{j>i}b[j]$, we are done in additional
${\cal O}(n)$ time by dynamic programming.

  3. 3.

We consider each connected component $C_{1},C_{2},\ldots,C_{q}$ of
$T\setminus\\{c\\}$ sequentially. Let $k$ with $1\leq k\leq q$ be fixed. For
every $i$ with $0\leq i\leq|C_{k}|$, we compute $a_{k}[i]=\sum\\{\pi(x)\mid
x\in C_{k},\ d(x,c)+i<d(x,S)\\}$. This can be done in ${\cal O}(|C_{k}|)$ time
by using the exact same approach as for the prior step of the algorithm.
Finally, for every node $v\in C_{k}$, we set:

$\beta(v)=a[d(v,c)]-a_{k}[d(v,c)].$

This can be computed in ${\cal O}(1)$ time per node of $C_{k}$, and therefore,
in ${\cal O}(|C_{k}|)$ time.

The total running time of the algorithm is in ${\cal O}(n)$. In order to prove
correctness of the algorithm, let $v\in V\setminus\\{c\\}$ be arbitrary. We
have $v\in C_{k}$ for some $k$ with $1\leq k\leq q$. For every node $x$, we
have $c\in I(x,v)$ if and only if $x\notin C_{k}$. Furthermore, in this
situation we have $d(x,v)<d(x,S)$ if and only $d(x,c)+d(c,v)<d(x,S)$. The sum
of the costs of all nodes $x$ such that $d(x,c)+d(c,v)<d(x,S)$ is exactly
$a[d(v,c)]$. In order to compute $\beta(v)$ from $a[d(v,c)]$, we need to
remove from the latter the sum of the costs of all such nodes $x$ with $x\in
C_{k}$, that is exactly $a_{k}[d(v,c)]$. ∎

######  Lemma 3.7.

Let $c$ be an internal node in a tree $T=(V,E)$, and let $S$ be a proper
vertex list. We can compute $\gamma(v)=\max\\{\ell_{\pi}(s,S+v)\mid
c\notin\mathbb{T}(s,S),\ c\in I(v,s)\\}$, for every node $v\in
V\setminus\\{c\\}$, in ${\cal O}(n)$ time.

###### Proof.

Let $C_{1},C_{2},\ldots,C_{q}$ be the connected components of
$T\setminus\\{c\\}$. For convenience, given any node $v$ with $v\neq c$, we
denote by $C(v)$ the unique component $C_{i}$ that contains $v$, for some $i$
with $1\leq i\leq q$. We denote by $S^{\prime}$ the sublist obtained from $S$
by erasing the unique site $s_{c}$ such that $c\in\mathbb{T}(s_{c},S)$. For
every $j$ with $0\leq j\leq n$, let us define, for every node $s\in
S^{\prime}$,

$\ell_{j}(s)=\ell_{\pi}(s,S)-\sum\\{\pi(x)\mid x\in\mathbb{T}(s,S)\
\text{and}\ d(x,s)>d(x,c)+j\\}.$

Intuitively, $\ell_{j}(s)$ would be the load of $s$ upon insertion of a new
node $v$, with $v\notin C(s)$ and $d(v,c)=j$. In particular, the following
holds for every node $v$, with $v\neq c$ and $d(v,c)=j$:
$\gamma(v)=\max\\{\ell_{j}(s)\mid s\in S^{\prime}\setminus C(v)\\}$.
Therefore, in order to compute $\gamma(v)$, for every node $v$ with $v\neq c$,
it suffices to compute the following information for every $j$ with $0\leq
j\leq n$:

  * •

a node $s_{j}$ maximizing $\ell_{j}(s_{j})$ within $S^{\prime}$;

  * •

a node $s_{j}^{\prime}$ maximizing $\ell_{j}(s_{j}^{\prime})$ within
$S^{\prime}\setminus C(s_{j})$.

For that, we first compute $\mathbf{Vor}(T,S)$, and the distances $d(x,S)$ and
$d(x,c)$ for every node $x$. By Proposition 2.4, this can be done in ${\cal
O}(n)$ time. We order the nodes $x$, with $x\neq c$, by nondecreasing values
$d(x,S)-d(x,c)$, which can also be done in ${\cal O}(n)$ time by using
counting sort. For every node $s\in S^{\prime}$, let
$\lambda(s)=\ell_{\pi}(s,S)$. Intuitively, at the end of each step $j$ of our
main procedure (presented next), we must have $\lambda(s)=\ell_{j}(s)$. We now
proceed as follows for every $j$ with $0\leq j\leq n$:

  * •

Case $j=0$ (first step). Let $X_{0}=\\{x\in V\setminus\\{c\\}\mid
d(x,S)>d(x,c)\\}$. We consider each node $x\in X_{0}$ sequentially. Let $s\in
S$ be such that $x\in\mathbb{T}(s,S)$. If $c\notin\mathbb{T}(s,S)$, then we
set $\lambda(s)=\lambda(s)-\pi(x)$. Finally, we compute a vertex $s_{0}$
($s_{0}^{\prime}$, resp.) that maximizes $\lambda(s_{0})$
($\lambda(s_{0}^{\prime})$, resp.) within $S^{\prime}$ (within
$S^{\prime}\setminus C(s_{0})$, resp.).

  * •

Case $j>0$. Let $X_{j}=\\{x\in V\setminus\\{c\\}\mid d(x,S)-d(x,c)=j\\}$. We
scan each node in $X_{j}$, computing along the way a subset $S_{j}$ of
relevant nodes in $S^{\prime}$. Initially, we set $S_{j}=\emptyset$. We
consider each node $x\in X_{j}$ sequentially. Let $s\in S$ be such that
$x\in\mathbb{T}(s,S)$. If $c\notin\mathbb{T}(s,S)$, then we add $s$ in
$S_{j}$, then we set $\lambda(s)=\lambda(s)+\pi(x)$. Finally, we compute a
vertex $s_{j}$ ($s_{j}^{\prime}$, resp.) that maximizes $\lambda(s_{j})$
($\lambda(s_{j}^{\prime})$, resp.) within $S_{j}\cup\\{s_{j-1}\\}$ (within
$\left(S_{j}\cup\\{s_{j-1},s_{j-1}^{\prime}\\}\right)\setminus C(s_{j})$,
resp.).

Step $0$ can be done in ${\cal O}(n)$ time. Furthermore, since we ordered all
nodes $x$ with $x\neq c$ by nondecreasing values $d(x,S)-d(x,c)$, all subsets
$X_{1},X_{2},\ldots,X_{n}$ can be computed in ${\cal O}(n)$ time. Being given
$X_{j}$, for some $j$ with $1\leq j\leq n$, Step $j$ can be done in ${\cal
O}(|X_{j}|+|S_{j}|)={\cal O}(|X_{j}|)$ time, provided we can compute in ${\cal
O}(1)$ time, for every $x\in X_{j}$ the unique $s\in S$ such that
$x\in\mathbb{T}(s,S)$. That is indeed the case because we precomputed
$\mathbf{Vor}(T,S)$. Overall, the running time is in ${\cal
O}(\sum_{j}|X_{j}|)={\cal O}(|X_{0}|)={\cal O}(n)$.

In order to prove correctness of the algorithm, we prove (as claimed above)
that at the end of each step $j$, we have $\lambda(s)=\ell_{j}(s)$, for every
$s\in S^{\prime}$. We prove it by induction on $j$. If $j=0$, then at the end
of step $0$ we have:

$\displaystyle\lambda(s)$ $\displaystyle=\ell_{\pi}(s)-\sum\\{\pi(x)\mid x\in
X_{0}\cap\mathbb{T}(s,S)\\}$ $\displaystyle=\ell_{\pi}(s)-\sum\\{\pi(x)\mid
x\in\mathbb{T}(s,S),\ d(x,S)>d(x,c)\\}$
$\displaystyle=\ell_{\pi}(s)-\sum\\{\pi(x)\mid x\in\mathbb{T}(s,S),\
d(x,s)>d(x,c)\\}$ $\displaystyle=\ell_{0}(s)$

From now on, we assume that $j>0$. By the induction hypothesis, we have
$\lambda(s)=\ell_{j-1}(s)$ before we start step $j$. Therefore, at the end of
step $j$ we have:

$\displaystyle\lambda(s)$ $\displaystyle=\ell_{j-1}(s)+\sum\\{\pi(x)\mid x\in
X_{j}\cap\mathbb{T}(s,S)\\}$ $\displaystyle=\ell_{j-1}(s)+\sum\\{\pi(x)\mid
x\in\mathbb{T}(s,S),\ d(x,S)=d(x,c)+j\\}$
$\displaystyle=\ell_{\pi}(s)-\sum\\{\pi(x)\mid x\in\mathbb{T}(s,S),\
d(x,s)>d(x,c)+j-1\\}+\sum\\{\pi(x)\mid x\in\mathbb{T}(s,S),\
d(x,S)=d(x,c)+j\\}$ $\displaystyle=\ell_{\pi}(s)-\sum\\{\pi(x)\mid
x\in\mathbb{T}(s,S),\ d(x,s)>d(x,c)+j\\}$ $\displaystyle=\ell_{j}(s)$

Finally, we need to prove the maximality of the selected nodes
$s_{j},s_{j}^{\prime}$ at each step $j$. We also prove it by induction on $j$.
This is straightforward if $j=0$ because we consider all nodes of $S^{\prime}$
(of $S^{\prime}\setminus C(s_{0})$, resp.) in order to compute $s_{0}$
($s_{0}^{\prime}$, resp.). From now on, we assume that $j>0$. Suppose by
contradiction the existence of some node $s\in S^{\prime}$, with $s\neq s_{j}$
and $\lambda_{j}(s)>\lambda_{j}(s_{j})$. In particular, $s\notin S_{j}$, which
implies $\lambda_{j}(s)=\lambda_{j-1}(s)$. But then, by induction on $j$,

$\displaystyle\lambda_{j}(s)=\lambda_{j-1}(s)\leq\lambda_{j-1}(s_{j-1})\leq\lambda_{j}(s_{j-1})\leq\lambda_{j}(s_{j}).$

A contradiction. We can prove similarly as above that $s_{j}^{\prime}$
maximizes $\ell_{j}(s_{j}^{\prime})$ within $S^{\prime}\setminus C(s_{j})$. ∎

We are now ready to prove the main result in this subsection:

######  Theorem 3.8.

We can solve Balanced Vertex in ${\cal O}(n\log{n})$ time for trees.

###### Proof.

Let $T=(V,E)$ be an $n$-node tree, let $\pi$ be any nonnegative cost function
and let $S$ be a proper vertex list. We consider a more general problem, where
every node $v\notin S$ is further assigned nonnegative values
$\lambda(v),\Lambda(v)$ (initially, both values equal $0$). Intuitively, we
account for sites and territories in a supertree of $T$ but not in the tree
$T$ that we are currently considering. Let us define:

$R(v)=\max\\{\ell_{\pi}(v,S+v)+\lambda(v),\Lambda(v)\\}\cup\\{\ell_{\pi}(s,S+v)\mid
s\in S\\}.$

Our algorithm in what follows compute all values $R(v)$, for every $v\notin
S$. We may assume $S\neq\emptyset$ (otherwise,
$R(v)=\max\\{\lambda(v)+\pi(T),\Lambda(v)\\}$ for every node $v$). If
$V\setminus S$ is reduced to a unique node $v$, then we first compute
$\mathbf{Vor}(T,S+v)$, which by Proposition 2.4 can be done in ${\cal O}(n)$
time. Doing so, we can compute in ${\cal O}(n)$ time the values
$\ell_{\pi}(v,S+v)$ and $\ell_{\pi}(s,S+v)$, for every $s\in S$, and so,
$R(v)$. Thus, from now on we assume that $|V\setminus S|>1$. Our algorithm
goes as follows:

  1. 1.

We compute $\mathbf{Vor}(T,S)$. By Proposition 2.4, this can be done in ${\cal
O}(n)$ time.

  2. 2.

We compute a centroid, i.e. a node $c$ such that every connected component of
$T\setminus\\{c\\}$ contains at most $n/2$ nodes. It can be done in ${\cal
O}(n)$ time [17]. If furthermore $c\notin S$, then we compute $R(c)$. It can
be done in ${\cal O}(n)$ time if we are given $\mathbf{Vor}(T,S+c)$.
Therefore, by Proposition 2.4, we can compute $R(c)$ in ${\cal O}(n)$ time.

  3. 3.

Let $s_{c}\in S$ be such that $c\in\mathbb{T}(s_{c},S)$. We compute
$\alpha(v)=\sum\\{\pi(x)\mid x\in W(v,s_{c})\cap\mathbb{T}(s_{c},S)\\}$, for
every $v\notin S$, which can be done in ${\cal O}(n)$ time as follows: we set
the cost of every node in $V\setminus\mathbb{T}(s_{c},S)$ to $0$, then we
apply Lemma 3.5. Afterwards, we replace $\pi$ with some new cost function
$\pi^{\prime}$ so that:

$\pi^{\prime}(x)=\begin{cases}\pi(x)\ \text{if}\ x\notin\mathbb{T}(s_{c},S)\\\
0\ \text{otherwise.}\end{cases}$

  4. 4.

For every $v$ with $v\notin S\cup\\{c\\}$, we compute the cost of all vertices
$x\in\mathbb{T}(v,S+v)$ such that $v,x$ are in separate connected components
of $T\setminus\\{c\\}$. Equivalently, we aim at computing
$\beta(v)=\sum\\{\pi^{\prime}(x)\mid c\in I(v,x)\ \text{and}\
d(x,v)<d(x,S)\\}$, which can be done in ${\cal O}(n)$ time if we apply Lemma
3.6. For every $v$ with $v\notin S\cup\\{c\\}$, we further compute the maximum
cost of a subset $\mathbb{T}(s,S+v)$, amongst all sites $s$ with $s\neq s_{c}$
and $v,\mathbb{T}(s,S)$ are in separate connected components of
$T\setminus\\{c\\}$. Equivalently, we aim at computing
$\gamma(v)=\max\\{\ell_{\pi}(s,S+v)\mid c\notin\mathbb{T}(s,S),\ c\in
I(v,s)\\}$, which can be done in ${\cal O}(n)$ time if we apply Lemma 3.7.

  5. 5.

Let $C_{1},C_{2},\ldots,C_{q}$ be the connected components of
$T\setminus\\{c\\}$. We consider each component $C_{j}$ sequentially, for
every $j$ with $1\leq j\leq q$. Let $S_{j}=(S\setminus\\{s_{c}\\})\cap C_{j}$.
Let $\pi_{j}$ be the restriction of $\pi^{\prime}$ to $C_{j}$. For every $v\in
C_{j}$, we define:

$\displaystyle\lambda_{j}(v)$ $\displaystyle=\lambda(v)+\alpha(v)+\beta(v)$
$\displaystyle\Lambda_{j}(v)$
$\displaystyle=\max\\{\Lambda(v),\ell_{\pi}(s_{c},S)-\alpha(v),\gamma(v)\\}$
$\displaystyle R_{j}(v)$
$\displaystyle=\max\\{\lambda_{j}(v)+\ell_{\pi_{j}}(v,S_{j}+v),\Lambda_{j}(v)\\}\cup\\{\ell_{\pi_{j}}(s,S_{j}+v)\mid
s\in S_{j}\\}$

We compute $R_{j}(v)$ for every $v\in C_{j}$. For that, it suffices to apply
our algorithm recursively on $C_{j},\pi_{j},S_{j},\lambda_{j},\Lambda_{j}$.
Finally, we set $R(v)=R_{j}(v)$ for every $v\in C_{j}$.

The recursion depth is in ${\cal O}(\log{n})$ because at each stage the
maximum number of nodes in a subtree considered is halved. Since all subtrees
considered at any recursion stage are node disjoint, the running time of the
stage is in ${\cal O}(n)$. Hence, the total running time is in ${\cal
O}(n\log{n})$.

In order to prove correctness of the algorithm, it suffices to prove that for
every $j$ with $1\leq j\leq q$, for every $v\in C_{j}$, $R_{j}(v)=R(v)$. For
that, by Lemma 2.3:

$\displaystyle\mathbb{T}(v,S+v)$ $\displaystyle=\bigcup\\{x\in V\mid
d(x,v)<d(x,S)\\}$ $\displaystyle=\bigcup\\{W(v,s)\cap\mathbb{T}(s,S)\mid s\in
S\\}$

In particular,

$\displaystyle\lambda(v)+\ell_{\pi}(v,S+v)$
$\displaystyle=\lambda(v)+\sum_{s\in
S}\pi\left(W(v,s)\cap\mathbb{T}(s,S)\right)$
$\displaystyle=\lambda(v)+\pi\left(W(v,s_{c})\cap\mathbb{T}(s_{c},S)\right)+\sum_{s\in
S\setminus\\{s_{c}\\}}\pi\left(W(v,s)\cap\mathbb{T}(s,S)\right)$
$\displaystyle=\lambda(v)+\alpha(v)+\sum_{s\in
S\setminus\\{s_{c}\\}}\pi^{\prime}\left(W(v,s)\cap\mathbb{T}(s,S)\right)$
$\displaystyle=\lambda(v)+\alpha(v)+\sum_{s\in
S\setminus(S_{j}\cup\\{s_{c}\\})}\pi^{\prime}\left(W(v,s)\cap\mathbb{T}(s,S)\right)+\sum_{s\in
S_{j}}\pi^{\prime}\left(W(v,s)\cap\mathbb{T}(s,S)\right)$
$\displaystyle=\lambda(v)+\alpha(v)+\beta(v)+\sum_{s\in
S_{j}}\pi_{j}\left(W(v,s)\cap\mathbb{T}(s,S_{j})\right)$
$\displaystyle=\lambda_{j}(v)+\ell_{\pi_{j}}(v,S_{j}+v)$

For every $s\in S$, we have that $\mathbb{T}(s,S+v)=\mathbb{T}(s,S)\setminus
W(v,s)$. Therefore,

$\displaystyle\max\\{\Lambda(v)\\}\cup\\{\ell_{\pi}(s,S+v)\mid s\in S\\}$
$\displaystyle=\max\\{\Lambda(v),\ell_{\pi}(s_{c},S+v)\\}\cup\\{\ell_{\pi}(s,S+v)\mid
s\in S\setminus\\{s_{c}\\}\\}$
$\displaystyle=\max\\{\Lambda(v),\ell_{\pi}(s_{c},S)-\alpha(v)\\}\cup\\{\ell_{\pi}(s,S+v)\mid
s\in S\setminus(S_{j}\cup\\{s_{c}\\})\\}$
$\displaystyle\cup\\{\ell_{\pi}(s,S+v)\mid s\in S_{j}\\}$
$\displaystyle=\max\\{\Lambda(v),\ell_{\pi}(s_{c},S)-\alpha(v),\gamma(v)\\}\cup\\{\ell_{\pi}(s,S+v)\mid
s\in S_{j}\\}$
$\displaystyle=\max\\{\Lambda_{j}(v)\\}\cup\\{\ell_{\pi_{j}}(s,S_{j}+v)\mid
s\in S_{j}\\}$

By combining both equalities, we obtain as desired $R(v)=R_{j}(v)$. ∎

######  Remark 2.

In the recursive algorithm presented for trees, a site $s_{c}$ is discarded
from $S$ at every recursion stage. Therefore, the running time of the
algorithm is in ${\cal O}(n|S|)$, that is linear if $|S|$ is a constant. This
can be improved to ${\cal O}(n\log{|S|})$ as follows: at every recursion
stage, we compute a node $c$ so that there are at most $|S|/2$ sites in every
connected component of $T\setminus\\{c\\}$. It can be done in ${\cal O}(n)$
time because it is a special case of weighted centroid computation [17]. In
doing so, the recursion depth goes down to ${\cal O}(\log{|S|})$.

###  3.3 Bounded-treewidth graphs

We generalize the results of the prior subsections to some increasing
hierarchy of graph classes, namely, graphs of bounded treewidth. Recall that a
tree decomposition of a graph $G$ is a pair $(T,{\cal X})$, where $T$ is a
tree and ${\cal X}:V(T)\mapsto 2^{V(G)}$ is a mapping that satisfies the
following properties:

  * •

For every vertex $v\in V(G)$, there exists a node $t\in V(T)$ such that
$v\in{\cal X}_{t}$;

  * •

For every edge $uv\in E(G)$, there exists a node $t\in V(T)$ such that
$u,v\in{\cal X}_{t}$;

  * •

For every vertex $v\in V(G)$, the node subset $\\{t\in V(T)\mid v\in{\cal
X}_{t}\\}$ induces a connected subtree of $T$.

The subsets ${\cal X}_{t}$, for every node $t\in V(T)$, are called the bags of
the tree decomposition. We define the width of a tree decomposition as the
largest size of its bags minus one. The treewidth of $G$ is the minimum width
of its tree decompositions. In particular, graphs of unit treewidth are
exactly the forests, and every cycle has treewidth two.

Cabello and Knauer were the first to propose a reduction from some polynomial-
time solvable distance problems on bounded-treewidth graphs to orthogonal
range queries [10]. We propose a novel application of their framework to the
Balanced Vertex problem with constant number of sites in $S$.

We only consider counting queries in what follows. In particular, a range
query will always refer to a counting orthogonal range query. Let ${\cal P}$
denote a static $n$-set of $k$-dimensional points in $\mathbb{R}^{k}$. Let
also $f:{\cal P}\mapsto\mathbb{R}$ be fixed. A box is the Cartesian product of
$k$ intervals. Finally, a range query asks to compute

$\sum\\{f(\overrightarrow{p})\mid\overrightarrow{p}\in{\cal P}\cap{\cal B}\\}$

for some box ${\cal B}$. Bentley presented the $k$-range tree data structure
in order to answer to range queries [6]. The performance analysis of the
latter has been recently improved:

######  Lemma 3.9 ([8]).

Let $B(n,k)=\binom{k+\log{n}}{k}$. Being given a fixed $n$-set of
$k$-dimensional points, and any weight function $f$, a $k$-range tree can be
constructed in ${\cal O}(k^{2}B(n,k)n)$ time. Moreover, a range query can be
answered in ${\cal O}(2^{k}B(n,k))$ time.

Throughout this subsection, we write all running times as some functions of
$B(n,k)$. We refer to Remark 3 for a more detailed analysis of $B(n,k)$.

Roughly, our strategy consists in mimicking our previous approach for trees.
Specifically, centroids in a tree decomposition of width at most $k$ are
balanced separators of size at most $k$. We generalize Lemma 3.6, for cut-
vertices in trees, to the following Lemma 3.10 for $k$-separators. Our
generalization makes use of range queries. Intuitively, the function $D_{S}$
in the statement of Lemma 3.10 below represents the distances to the sites of
$S$ in some supergraph of $G$.

######  Lemma 3.10.

Being given a graph $G=(V,E,\lambda)$ with positive integer edge weights, and
two nonnegative cost functions $\pi$ and $D_{S}$, let $A$ and $B$ satisfy:
$A\cup B=V$, $|A\cap B|\leq k$. We can compute $\delta(a,B)=\sum\\{\pi(b)\mid
b\in B\setminus A\ \text{and}\ d(b,a)<D_{S}(b)\\}$, for every $a\in A\setminus
B$, in ${\cal O}(km+k2^{k}B(n,k)n)$ time.

###### Proof.

For convenience, let $X=A\cap B$. We further assume for simplicity that
$|X|=k$. We first compute a shortest-path tree rooted at $x$, for every $x\in
X$. Since all edge weights are positive integer, this can be done in ${\cal
O}(m)$ time per vertex in $X$, using Thorup’s single-source shortest-path
algorithm [24]. Let $X=(x_{1},x_{2},\ldots,x_{k})$ be totally ordered in some
arbitrary way. We proceed as follows for every $i$ with $1\leq i\leq k$.

  1. 1.

For every $b\in B\setminus X$, we create a $k$-dimensional point
$\overrightarrow{p_{i}(b)}=(p_{i,1}(b),p_{i,2}(b),\ldots,p_{i,k}(b))$, where:

$\begin{cases}p_{i,i}(b)=D_{S}(b)\\\ p_{i,j}(b)=d(b,x_{j})-d(b,x_{i})\
\text{for every}\ j\ \text{with}\ 1\leq j\leq k,\ j\neq i\end{cases}$

Let $f(\overrightarrow{p_{i}(b)})=\pi(b)$. We add all these points and their
weights in some $k$-range tree. By Lemma 3.9, this can be done in ${\cal
O}(k^{2}B(n,k)n)$ time.

  2. 2.

For every $a\in A\setminus X$, we aim at computing the cost $\delta_{i}(a,B)$
of all vertices $b\in B\setminus X$ with the following properties:
$D_{S}(b)>d(b,a)$, $x_{i}$ is on a shortest $ab$-path; no vertex of
$\\{x_{1},x_{2},\ldots,x_{i-1}\\}$ is on a shortest $ab$-path. We can
formulate these properties as range constraints for each coordinate of
$\overrightarrow{p_{i}(b)}$, as follows:

$\begin{cases}p_{i,j}(b)=d(b,x_{j})-d(b,x_{i})>d(a,x_{i})-d(a,x_{j}),\
\text{for every}\ j\ \text{with}\ 1\leq j<i\\\ p_{i,i}(b)=D_{S}(b)>d(a,b)\\\
p_{i,j}(b)=d(b,x_{j})-d(b,x_{i})\geq d(a,x_{i})-d(a,x_{j}),\ \text{for every}\
j\ \text{with}\ i<j\leq k\end{cases}$

As a result, for a fixed $a$, we can compute the cost of all corresponding
vertices of $B\setminus X$ with a single range query, which by Lemma 3.9 can
be answered in ${\cal O}(2^{k}B(n,k))$ time.

Finally, we compute $\delta(a,B)=\sum_{i=1}^{k}\delta_{i}(a,B)$, for every
$a\in A\setminus X$. ∎

Being given a tree decomposition $(T,{\cal X})$ of width ${\cal O}(k)$, the
following result is a combination of Lemma 3.10 with a centroid decomposition
of $T$.

######  Lemma 3.11.

Let $S$ be an arbitrary vertex subset in a graph $G=(V,E)$, and let $\pi$ be
any nonnegative cost function. If $G$ has treewidth at most $k$, then we can
compute $\delta(v)=\sum\\{\pi(u)\mid d(u,v)<d(u,S)\\}$, for every $v\in
V\setminus S$, in ${\cal O}(k2^{{\cal O}(k)}B(n,k)n\log{n})$ time.

###### Proof.

We consider a more general case where we are also given a positive integral
edge weight function $\lambda$ (initially, we have $\lambda(e)=1$ for every
$e\in E$). We may assume that $n>k+1$ (otherwise, we can compute all values
$\delta(v)$ in ${\cal O}(k^{2})$ time, if we use a brute-force algorithm). We
may further assume that all distances $D_{S}(v)=d(v,S)$, for every vertex $v$,
are known throughout the entire procedure, which can always be ensured by
running a BFS on $S$ before the algorithm starts. Let $(T,{\cal X})$ be a tree
decomposition of $G$ of width ${\cal O}(k)$. Such a tree decomposition can be
computed in ${\cal O}(2^{{\cal O}(k)}n)$ time [21]. We often use that $m={\cal
O}(kn)$.

  1. 1.

We compute some bag ${\cal X}_{t}$, with $t\in V(T)$, such that every
connected component of $G\setminus{\cal X}_{t}$ contains at most $n/2$
vertices. Such a bag always exists and it can be computed in ${\cal O}(kn)$
time if $(T,{\cal X})$ is given. For every $x\in{\cal X}_{t}\setminus S$, we
can compute $\delta(x)$ in ${\cal O}(m)={\cal O}(kn)$ time if we run a BFS on
$x$.

  2. 2.

We group the connected components of $G\setminus{\cal X}_{t}$ in two subsets
$A$ and $B$ so that: $A\cup B=V$, $A\cap B={\cal X}_{t}$ and
$\max\\{|A|,|B|\\}\leq 2n/3$. We apply Lemma 3.10 twice in order to compute
$\delta(a,B)$ for every $a\in A\setminus{\cal X}_{t}$ ($\delta(b,A)$, for
every $b\in B\setminus{\cal X}_{t}$, resp.). This can be done in ${\cal
O}(km+k2^{k}B(n,k)n)={\cal O}(k2^{k}B(n,k)n)$ time.

  3. 3.

Let $G_{A}$ ($G_{B}$, resp.) be obtained from $G[A]$ ($G[B]$, resp.) by adding
edges $xx^{\prime}$ of weights $d(x,x^{\prime})$, for every two
$x,x^{\prime}\in{\cal X}_{t}$. The computation of all distances
$d(x,x^{\prime})$ can be done in ${\cal O}(km)={\cal O}(k^{2}n)$ time, if we
run a BFS on every vertex of ${\cal X}_{t}$. We apply our algorithm
recursively to $G_{A},G_{B}$ in order to compute the values
$\delta_{A}(a)=\sum\\{\pi(a^{\prime})\mid a^{\prime}\in A,\
d(a,a^{\prime})<D_{S}(a^{\prime})\\}$, for every $a\in A$, and the values
$\delta_{B}(b)=\sum\\{\pi(b^{\prime})\mid b^{\prime}\in B,\
d(b,b^{\prime})<D_{S}(b^{\prime})\\}$, for every $b\in B$.

  4. 4.

For every $a\in A\setminus{\cal X}_{t}$, we set
$\delta(a)=\delta(a,B)+\delta_{A}(a)$. In the same way, for every $b\in
B\setminus{\cal X}_{t}$, we set $\delta(b)=\delta(b,A)+\delta_{B}(b)$.

The recursion depth is in ${\cal O}(\log{n})$. Each recursive stage can be
done in ${\cal O}(k2^{k}B(n,k)n)$ time (the running time is dominated by Step
2). Therefore, the running time of the algorithm is in ${\cal O}(k2^{{\cal
O}(k)}B(n,k)n\log{n})$. ∎

Finally, we give a one-to-many reduction from Balanced Vertex with constant
number of sites to Lemma 3.11.

######  Theorem 3.12.

We can solve Balanced Vertex in ${\cal O}(k2^{{\cal O}(k)}B(n,k)n|S|\log{n})$
time if $G$ has treewidth at most $k$.

###### Proof.

For every $v\notin S$, our algorithm in what follows computes
$\ell_{\pi}(v,S+v)$ and all values $\ell_{\pi}(s,S+v)$, for every $s\in S$.
Note that doing so, we can compute $L_{\pi}(S+v)$, for every $v\notin S$, in
additional ${\cal O}(n|S|)$ time.

  1. 1.

We compute $\mathbf{Vor}(G,S)$. By Proposition 2.4, this can be done in ${\cal
O}(m)$ time, that is in ${\cal O}(kn)$ if $G$ has treewidth $k$. Doing so, we
can compute the loads $\ell_{\pi}(s,S)$, for every $s\in S$, in additional
${\cal O}(n)$ time.

  2. 2.

We apply Lemma 3.11 in order to compute $\ell_{\pi}(v,S+v)$, for every
$v\notin S$.

  3. 3.

We then consider each $s\in S$ sequentially. We replace $S$ by the list $(s)$
with a unique site, and the cost function $\pi$ by a new cost function
$\pi_{s}$ such that

$\begin{cases}\pi_{s}(u)=0\ \text{if}\ u\notin\mathbb{T}(s,S)\\\
\pi_{s}(u)=\pi(u)\ \text{otherwise.}\end{cases}$

Note that we can compute the new cost function $\pi_{s}$ in ${\cal O}(n)$
time, that is because we are given $\mathbf{Vor}(G,S)$. We apply Lemma 3.11 in
order to compute, for every $v\notin S$, $\pi(W(v,s)\cap\mathbb{T}(s,S))$.
Doing so, we can compute
$\ell_{\pi}(s,S+v)=\ell_{\pi}(s,S)-\pi(W(v,s)\cap\mathbb{T}(s,S))$.

Overall, since we apply Lemma 3.11 $|S|+1$ times, the running time is in
${\cal O}(k2^{{\cal O}(k)}B(n,k)n|S|\log{n})$. ∎

######  Remark 3.

Bringmann et al. proved that for every $\varepsilon>0$, there exists a
constant $c$ such that $B(n,k)=2^{ck}n^{\varepsilon}$ [8]. In particular, for
every $\varepsilon>0$, there exists a constant $c^{\prime}$ such that the
running time of our algorithm for bounded treewidth graphs is in ${\cal
O}(2^{c^{\prime}k}|S|n^{1+\varepsilon})$. The exponential dependency on the
treewidth is necessary, even for one site, if one assumes the Hitting Set
Conjecture. Indeed, the graph constructed in the proof of Theorem 2.8 has
treewidth ${\cal O}(\log{n})$.

###  3.4 Proper interval graphs

We devote our last and arguably most technical subsection to proper interval
graphs. Recall that an interval graph is the intersection graph of a family of
intervals on the real line. A realization of an interval graph $G$ is a
mapping of its vertices to closed intervals on the real line, so that two
vertices are adjacent in $G$ if and only if their corresponding intervals are
intersecting. It is a proper realization if there are no two vertices such
that the interval of one is contained in the interval of the other. A proper
interval graph is one admitting a proper realization.

Our scheme only applies to proper interval graphs, not to interval graphs, and
it is good to explain why it is so. Roughly, we would like to mimic the scheme
for paths (see Lemma 3.3). A natural path representation for the interval
graphs is to order the vertices by nondecreasing left boundary, within some
fixed realization. Then, what we would like to prove is the existence of some
constant $\kappa$ (ideally, $\kappa=1$) such that if we insert a new site $v$
at the end of $S$, then only the $\kappa$ closest sites to $v$ on the left and
right of the path representation could have their respective territories
modified. Unfortunately, this is impossible due to the potential existence of
vertices whose interval covers an arbitrary number of other intervals.
Therefore, we restrict ourselves to proper realizations, for which the latter
case cannot happen. Some important properties of proper realizations are
captured by the following distance formula:

######  Lemma 3.13 ([15]).

Let $G=(V,E)$ be a proper interval graph, and let $x_{0}$ be the vertex with
the minimum left boundary in some proper realization of $G$. We can compute in
${\cal O}(n)$ time a total ordering $\sigma:V\to\\{1,\ldots,n\\}$ so that, for
every vertices $u$ and $v$ with $d(u,x_{0})\leq d(v,x_{0})$:

$d(u,v)=\begin{cases}d(v,x_{0})-d(u,x_{0})\ \text{if}\ d(u,x_{0})<d(v,x_{0})\
\text{and}\ \sigma(v)<\sigma(u)\\\ d(v,x_{0})-d(u,x_{0})+1\
\text{otherwise}.\end{cases}$

First, we combine Lemma 3.13 with orthogonal range queries (see Sec. 3.3) in
order to precompute the load of every new site in a prioritized Voronoi
diagram. We could easily do so with $3$-dimensional range queries because, for
every vertex $u$, we only need to memorize $\sigma(u)$ and
$d(u,x_{0}),d(u,S)$. However, we can shave some polylogarithmic factors by
reducing further down to $1$-dimensional range queries. Indeed, a $1$-range
tree is just a balanced binary search tree111Values are stored at the leaves,
but this feature is not important in our case.. In particular, by using a
self-balanced binary search tree implementation, we can serve range queries on
a dynamic collection of values. Doing so, we only need to store $\sigma(u)$,
for every vertex $u$, while other relevant distance information can be deduced
contextually for the vertices $u$ that are currently stored in the search
tree.

######  Lemma 3.14.

Let $G=(V,E)$ be a proper interval graph, let $x_{0}$ be the vertex with the
minimum left boundary in some proper realization of $G$, and let $\sigma$ be
as in Lemma 3.13. For every nonnegative cost function $\pi$, and every proper
vertex list $S$, we can compute the values $\ell_{\pi}(v,S+v)$, for every
$v\notin S$, in ${\cal O}(m+n\log{n})$ time.

###### Proof.

We first describe the algorithm.

  1. 1.

We compute all distances $d(v,x_{0}),d(v,S)$, for every vertex $v$. Doing so,
we partition $V$ in distance layers
$X_{0}=\\{x_{0}\\},X_{1}=N(x_{0}),X_{2},\ldots,X_{e(x_{0})}$, where
$e(x_{0})=\max_{v\in V}d(x_{0},v)$ and, for every $j$ with $0\leq j\leq
e(x_{0})$, $X_{j}=\\{v\in V\mid d(x_{0},v)=j\\}$. This can be done in ${\cal
O}(n+m)$ time. Let us further compute $\mathbf{Vor}(G,S)$, which by
Proposition 2.4 can also be done in ${\cal O}(n+m)$ time. For convenience, for
every vertex $v$, we denote in what follows by $s_{v}$ the unique site of $S$
such that $v\in\mathbb{T}(s_{v},S)$.

  2. 2.

We consider each distance layer $X_{0},X_{1},\ldots,X_{e(x_{0})}$
sequentially. Throughout all iterations of this phase, we maintain a counter
$\Lambda^{-}$ and a balanced binary search tree $T^{-}$ such that the
following invariants hold before considering any layer $X_{j}$:

     * •

$\Lambda^{-}=\sum\\{\pi(u)\mid d(x_{0},u)<j,\ \text{and}\
d(u,s_{u})>j-d(x_{0},u)+1\\}$.

Since the cost $\pi(u)$ of every vertex $u$ needs to be added and removed from
$\Lambda^{-}$ at most once, we can maintain the counter $\Lambda^{-}$
throughout this whole phase in total ${\cal O}(n)$ time.

     * •

we store in $T^{-}$ all vertices $u$ such that: $d(x_{0},u)<j$, and
$d(u,s_{u})=j-d(x_{0},s_{u})+1$. A vertex $u$ is identified in $T^{-}$ with
the value $\sigma(u)$. Furthermore, at each vertex $u$ in $T^{-}$ we store the
sum of the costs $\pi(u^{\prime})$ of all vertices $u^{\prime}$ in its rooted
subtree.

Each vertex $u$ is inserted and deleted from $T^{-}$ at most once. Standard
implementations such as AVL [2] can be easily modified in order to dynamically
maintain the cost of rooted subtrees after each insertion/deletion. As a
result, we can maintain $T^{-}$ throughout this whole phase in total ${\cal
O}(n\log{n})$ time.

For every $v\in X_{j}$, we compute the cumulative cost of all vertices $u\in
T^{-}$ such that $\sigma(v)<\sigma(u)$. Since every node of $T^{-}$ stores the
cost of its rooted subtree, this can be done in ${\cal O}(\log{n})$ time by
using range searching techniques, namely: we search for the vertex $u$ of
$T^{-}$ such that $\sigma(u)>\sigma(v)$ and $\sigma(u)$ is minimized, then we
process the costs of all vertices on the path to the root and of their
respective right subtrees (details left out can be found, e.g., in [6, 8]).
Let $\lambda^{-}(v)=\Lambda^{-}+\sum\\{\pi(u)\mid u\in
T^{-},\sigma(v)<\sigma(u)\\}$.

  3. 3.

Roughly, we do the reverse of the previous phase. Specifically, we consider
each distance layer $X_{e(x_{0})},X_{e(x_{0})-1},\ldots,X_{0}$ sequentially.
Throughout all iterations of this phase, we maintain a counter $\Lambda^{+}$
and a balanced binary search tree $T^{+}$ such that the following invariants
hold before considering any layer $X_{j}$:

     * •

$\Lambda^{+}=\sum\\{\pi(u)\mid d(x_{0},u)>j,\ \text{and}\
d(u,s_{u})>d(x_{0},u)-j+1\\}$.

     * •

we store in $T^{+}$ all vertices $u$ such that: $d(x_{0},u)>j$, and
$d(u,s_{u})=d(x_{0},s_{u})-j+1$. A vertex $u$ is identified in $T^{+}$ with
the value $\sigma(u)$. Furthermore, at each vertex $u$ in $T^{+}$ we store the
sum of the costs $\pi(u^{\prime})$ of all vertices $u^{\prime}$ in its rooted
subtree.

For every $v\in X_{j}$, we compute the cumulative cost of all vertices $u\in
T^{+}$ such that $\sigma(v)>\sigma(u)$. Let
$\lambda^{+}(v)=\Lambda^{+}+\sum\\{\pi(u)\mid u\in
T^{+},\sigma(v)>\sigma(u)\\}$.

The total running time is in ${\cal O}(m+n\log{n})$.

Let $j$ with $0\leq j\leq e(x_{0})$ be fixed. We set $\Pi(j)=\sum\\{\pi(u)\mid
u\in X_{j},\ d(u,s_{u})>1\\}$. For every $v\in X_{j}\setminus S$, we claim
that we have

$\ell_{\pi}(v,S+v)=\begin{cases}\lambda^{-}(v)+\lambda^{+}(v)+\Pi(j)\
\text{if}\ d(v,s_{v})>1\\\ \lambda^{-}(v)+\lambda^{+}(v)+\Pi(j)+\pi(v)\
\text{else}\end{cases}$

Indeed, let $u\in V\setminus\\{v\\}$ be arbitrary. There are three different
cases:

  * •

If $d(u,x_{0})=j$, then by Lemma 3.13, $d(u,v)=1$. In particular,
$u\in\mathbb{T}(v,S+v)$ if and only if $d(u,s_{u})>1$. Therefore,
$\ell_{\pi}(v,S+v)\geq\Pi(j)$, and if $d(v,s_{v})=1$ then
$\ell_{\pi}(v,S+v)\geq\Pi(j)+\pi(v)$.

  * •

If $d(u,x_{0})<j$, then by Lemma 3.13,
$d(u,v)\in\\{j-d(u,x_{0}),j-d(u,x_{0})+1\\}$. In particular,
$u\notin\mathbb{T}(v,S+v)$ if $d(u,s_{u})\leq j-d(u,x_{0})$. Furthermore,
$u\in\mathbb{T}(v,S+v)$ if $d(u,s_{u})>j-d(u,x_{0})+1$. Otherwise,
$d(u,s_{u})=j-d(u,x_{0})+1$, and so we have $u\in\mathbb{T}(v,S+v)$ if and
only if $d(u,v)=j-d(u,x_{0})$, which by Lemma 3.13 is equivalent to
$\sigma(v)<\sigma(u)$. As a result, $\ell_{\pi}(v,S+v)\geq\lambda^{-}(v)$.

  * •

Otherwise, $d(u,x_{0})>j$. By Lemma 3.13,
$d(u,v)\in\\{d(u,x_{0})-j,d(u,x_{0})-j+1\\}$. In particular,
$u\notin\mathbb{T}(v,S+v)$ if $d(u,s_{u})\leq d(u,x_{0})-j$. Furthermore,
$u\in\mathbb{T}(v,S+v)$ if $d(u,s_{u})>d(u,x_{0})-j+1$. Otherwise,
$d(u,s_{u})=d(u,x_{0})-j+1$, and so we have $u\in\mathbb{T}(v,S+v)$ if and
only if $d(u,v)=d(u,x_{0})-j$, which by Lemma 3.13 is equivalent to
$\sigma(u)<\sigma(v)$. As a result, $\ell_{\pi}(v,S+v)\geq\lambda^{+}(v)$.

Our claim directly follows from this case analysis. ∎

From another application of Lemma 3.13, where we process distance layers from
$x_{0}$ in a different way than what we did for Lemma 3.14, we obtain the
following complementary result:

######  Lemma 3.15.

Let $G=(V,E)$ be a proper interval graph, let $x_{0}$ be the vertex with the
minimum left boundary in some proper realization of $G$, and let $\sigma$ be
as in Lemma 3.13. For every nonnegative cost function $\pi$, and every proper
vertex list $S$, we can compute the values
$\Lambda(v)=\max\\{\ell_{\pi}(s,S+v)\mid s\in S\\}$, for every vertex $v\notin
S$, in ${\cal O}(m+n\log{n})$ time.

###### Proof.

We need some notations for what follows. Let $e(x_{0})=\max_{v\in
V}d(x_{0},v)$. For every $j$ with $0\leq j\leq e(x_{0})$, let $X_{j}=\\{v\in
V\mid d(x_{0},v)=j\\}$.Finally, for every vertex $v$, let $s_{v}$ be the
unique site of $S$ such that $v\in\mathbb{T}(s_{v},S)$.

Roughly, the algorithm consists of two phases. During its first phase, we
compute the Voronoi diagram of $G$ with respect to $S$, and we create a max-
heap ${\cal H}$ storing all sites in $S$. Then, during the second and main
phase, we process the heap in order to compute $\Lambda(v)$, for every $v\in
V\setminus S$. More precisely, we iterate over the distance layers
$X_{0},X_{1},\ldots,X_{e(x_{0})}$ and, for every $j$ with $0\leq j\leq
e(x_{0})$, we compute all values $\Lambda(v)$, for $v\in X_{j}\setminus S$,
sequentially. Intuitively, when we consider a vertex $v\in X_{j}\setminus S$,
the key of every site $s$ in ${\cal H}$ must be equal to $\ell_{\pi}(s,S+v)$.

First Phase. We compute $\mathbf{Vor}(G,S)$, which by Proposition 2.4 can be
done in ${\cal O}(n+m)$ time. We compute, also in ${\cal O}(n+m)$ time, the
distances $d(x_{0},v),d(v,S)$ for every vertex $v$. Doing so, we can partition
$V$ in $X_{0},X_{1},\ldots,X_{e(x_{0})}$. Finally, we create a max-heap ${\cal
H}$ and, for every site $s$ of $S$, we insert $s$ into ${\cal H}$ with key
equal to

$key(s)=\ell_{\pi}(s,S)$

Being given $\mathbf{Vor}(G,S)$, we can compute all the keys in ${\cal O}(n)$
time. Every insertion in a heap can be done in ${\cal O}(\log{n})$ time.
Therefore, we can initialize the heap ${\cal H}$ in ${\cal O}(n\log{n})$ time.

Throughout every loop $j$ of the second phase, we maintain the following
invariant for ${\cal H}$: for every site $s$ of $S$,

$key(s)=\ell_{\pi}(s,S)-\sum\\{\pi(u)\mid u\in\mathbb{T}(s,S)\ \text{and}\
d(u,s_{u})>|j-d(u,x_{0})|+1\\}$

Intuitively, this is because any such vertex $u$ must be in the territory of
$v\notin S$, provided $v\in X_{j}$. For that, before we start the $j^{th}$
loop, we need to actualize the keys of all sites. More precisely, for every
vertex $u$:

  * •

We set $key(s_{u})=key(s_{u})-\pi(u)$ if the following conditions hold:

$\begin{cases}d(u,s_{u})\geq 2\\\
j=\max\left\\{0,d(u,x_{0})-d(u,s_{u})+2\right\\}\end{cases}$

Indeed, if $d(u,s_{u})\leq 1$, then there is no $j^{\prime}$ such that
$d(u,s_{u})>|j^{\prime}-d(u,x_{0})|+1$. Otherwise, for $j\leq d(u,x_{0})$, we
have $d(u,s_{u})>d(u,x_{0})-j+1$ if and only if $j>d(u,x_{0})-d(u,s_{u})+1$.

  * •

We set $key(s_{u})=key(s_{u})+\pi(u)$ if the following conditions hold:

$\begin{cases}d(u,s_{u})\geq 2\\\ j=d(u,s_{u})+d(u,x_{0})-1\end{cases}$

Indeed, if $d(u,s_{u})\geq 2$ and $j\geq d(u,x_{0})$, then we have
$d(u,s_{u})>j-d(u,x_{0})+1$ if and only if $j<d(u,s_{u})+d(u,x_{0})-1$.

For every vertex $u$, there are at most two loops such that we modify
$key(s_{u})$. Therefore, we need to modify any key ${\cal O}(n)$ times during
the second phase. Overall, we can maintain our invariant throughout the second
phase in ${\cal O}(n\log{n})$ time.

Second Phase. We are now ready to describe the main loop of the algorithm. We
consider each distance layer $X_{0},X_{1},\ldots,X_{e(x_{0})}$ sequentially.
Let $j$ with $0\leq j\leq e(x_{0})$ be fixed. We compute $\Lambda(v)$ for
every vertex $v\in X_{j}\setminus S$.

For that, we define the frontier $F_{j}$, as follows:

$F_{j}=\\{u\in V\setminus X_{j}\mid d(u,s_{u})=|j-d(u,x_{0})|+1\\}.$

Intuitively, being given a vertex $v\in X_{j}\setminus S$, the vertices $u$ in
the frontier may or may not be in $\mathbb{T}(v,S+v)$ depending on whether
$\sigma(u)$ is bigger or smaller than $\sigma(v)$. Determining, for every site
$s$, the vertices in $F_{j}\cap\mathbb{T}(s,S)$ that belong to $v$’s
territory, is the main difficulty in our algorithm. In what follows, we find
it convenient to bipartition $F_{j}$ in $F_{j}^{<},F_{j}^{>}$ such that:

$\displaystyle F_{j}^{<}$ $\displaystyle=\\{u\in F_{j}\mid d(x_{0},u)<j\\}$
$\displaystyle F_{j}^{>}$ $\displaystyle=\\{u\in F_{j}\mid d(x_{0},u)>j\\}$

We subdivide the loop in many intermediate steps:

  1. 1.

For every site $s$ of $S$, we set:

$key(s)=key(s)-\sum\\{\pi(u)\mid u\in F_{j}^{<}\cap\mathbb{T}(s,S)\\}$

Since we are given $\mathbf{Vor}(G,S)$, this can be done in ${\cal
O}(|F_{j}^{<}|\log{n})$ time by scanning the vertices of $F_{j}^{<}$.

  2. 2.

We order the vertices of $F_{j}\cup X_{j}$ according to $\sigma$. This can be
done in ${\cal O}(|F_{j}|\log{n}+|X_{j}|\log{n})$ time by using any fast
sorting algorithm.

  3. 3.

We scan the vertices of $F_{j}\cup X_{j}$ by increasing $\sigma$ values:

     * •

Case of a vertex $u\in F_{j}^{<}$. We set $key(s_{u})=key(s_{u})+\pi(u)$.

     * •

Case of a vertex $u\in F_{j}^{>}$. We set $key(s_{u})=key(s_{u})-\pi(u)$.

     * •

Case of a vertex $v\in X_{j}\setminus S$. First, if $d(s_{v},v)=1$, then we
set $key(s_{v})=key(s_{v})-\pi(v)$. We set $\Lambda(v)$ to be the maximum key
in ${\cal H}$. Finally, if $d(s_{v},v)=1$, then we reset
$key(s_{v})=key(s_{v})+\pi(v)$.

This can be done in ${\cal O}(\log{n})$ time per vertex considered.

  4. 4.

We reset the keys in ${\cal H}$, namely, for every site $s$ of $S$, we set:

$key(s)=key(s)+\sum\\{\pi(u)\mid u\in F_{j}^{>}\cap\mathbb{T}(s,S)\\}$

It takes ${\cal O}(|F_{j}^{>}|\log{n})$ time.

The total running time for the $j^{th}$ loop is in ${\cal
O}(|F_{j}|\log{n}+|X_{j}|\log{n})$. Since every vertex $u$ can appear in the
frontier $F_{j^{\prime}}$ for at most two indices $j^{\prime}$, the overall
running time of the second phase is in ${\cal O}(n\log{n})$.

In order to prove correctness of our algorithm, let $j$ with $0\leq j\leq
e(x_{0})$ be fixed. Let $v\in X_{j}\setminus S$ be arbitrary. In order to
prove that we correctly computed $\Lambda(v)$, it suffices to prove that at
the time we consider this vertex during the $j^{th}$ loop we have
$key(s)=\ell_{\pi}(s,S+v)$ for every site $s$ of $S$. That is indeed the case
because:

$\displaystyle key(s)$ $\displaystyle=\ell_{\pi}(s,S)-\sum\\{\pi(u)\mid
u\in\mathbb{T}(s,S)\ \text{and}\ d(u,s_{u})>|j-d(u,x_{0})|+1\\}$
$\displaystyle\hskip 50.0pt-\sum\\{\pi(u)\mid u\in
F_{j}^{<}\cap\mathbb{T}(s,S)\\}$ $\displaystyle\hskip 50.0pt+\sum\\{\pi(u)\mid
u\in F_{j}^{<}\cap\mathbb{T}(s,S)\ \text{and}\ \sigma(u)<\sigma(v)\\}$
$\displaystyle\hskip 50.0pt-\sum\\{\pi(u)\mid u\in
F_{j}^{>}\cap\mathbb{T}(s,S)\ \text{and}\ \sigma(u)<\sigma(v)\\}$
$\displaystyle\hskip 50.0pt-\mathbf{1}[s=s_{v}\ \text{and}\
d(s,v)=1]\cdot\pi(v)$ $\displaystyle=\ell_{\pi}(s,S)-\sum\\{\pi(u)\mid
u\in\mathbb{T}(s,S)\setminus\\{v\\}\ \text{and}\
d(u,s_{u})>|j-d(u,x_{0})|+1\\}$ $\displaystyle\hskip 50.0pt-\sum\\{\pi(u)\mid
u\in F_{j}^{<}\cap\mathbb{T}(s,S)\ \text{and}\ \sigma(u)>\sigma(v)\\}$
$\displaystyle\hskip 50.0pt-\sum\\{\pi(u)\mid u\in
F_{j}^{>}\cap\mathbb{T}(s,S)\ \text{and}\ \sigma(u)<\sigma(v)\\}$
$\displaystyle\hskip 50.0pt-\mathbf{1}[s=s_{v}]\cdot\pi(v)$
$\displaystyle=\ell_{\pi}(s,S)-\sum\\{\pi(u)\mid
u\in\mathbb{T}(s,S)\setminus\\{v\\}\ \text{and}\
d(u,s_{u})>|j-d(u,x_{0})|+1\\}$ $\displaystyle\hskip 50.0pt-\sum\\{\pi(u)\mid
u\in F_{j}^{<}\cap\mathbb{T}(s,S)\ \text{and}\ d(u,v)=j-d(u,x_{0})\\}$
$\displaystyle\hskip 50.0pt-\sum\\{\pi(u)\mid u\in
F_{j}^{>}\cap\mathbb{T}(s,S)\ \text{and}\ d(u,v)=d(u,x_{0})-j\\}$
$\displaystyle\hskip 50.0pt-\mathbf{1}[s=s_{v}]\cdot\pi(v)$
$\displaystyle=\ell_{\pi}(s,S)-\sum\\{\pi(u)\mid u\in\mathbb{T}(s,S)\
\text{and}\ d(u,v)<d(u,s)\\}$ $\displaystyle=\ell_{\pi}(s,S+v)$

∎

The following theorem summarizes our results in this subsection:

######  Theorem 3.16.

We can solve Balanced Vertex in ${\cal O}(m+n\log{n})$ time if $G$ is a proper
interval graph.

###### Proof.

We compute a proper realizer, which can be done in ${\cal O}(n+m)$ time [12].
Then, in additional ${\cal O}(n)$ time, we compute the vertex $x_{0}$ of
minimum left boundary and the ordering $\sigma$ of Lemma 3.13. We are done
applying Lemmas 3.14 and 3.15. ∎

##  4 Conclusion

In this paper, we introduced a new problem on graph Voronoi diagrams, and we
completely settled its complexity for general graphs under plausible
complexity assumptions. We left open whether our conditional time lower bound
could also hold under weaker complexity hypotheses.

We proposed various ways to tackle with our new problem on tree-like and path-
like topologies. In this respect, two immediate questions following our work
could be whether our results can be extended to bounded-treewidth graphs with
nonconstant number of sites, and to interval graphs.

Acknowledgement. This work was supported by a grant of the Ministry of
Research, Innovation and Digitalization, CCCDI - UEFISCDI, project number PN-
III-P2-2.1-PED-2021-2142, within PNCDI III.

## References

  * [1] A. Abboud, V. Vassilevska Williams, and J. Wang.  Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs.  In Proceedings of the twenty-seventh annual Symposium on Discrete Algorithms (SODA), pages 377–391. SIAM, 2016.
  * [2] G. Adelson-Velsky and E. Landis.  An algorithm for the organization of information.  Proceedings of the USSR Academy of Sciences, 146:263–266, 1992\.
  * [3] F. Aurenhammer.  Voronoi diagrams—a survey of a fundamental geometric data structure.  ACM Computing Surveys (CSUR), 23(3):345–405, 1991.
  * [4] S. Bandyapadhyay, A. Banik, S. Das, and H. Sarkar.  Voronoi game on graphs.  Theoretical Computer Science, 562:270–282, 2015.
  * [5] M. Bender and M. Farach-Colton.  The level ancestor problem simplified.  Theoretical Computer Science, 321(1):5–12, 2004.
  * [6] J. Bentley.  Decomposable searching problems.  Information Processing Letters, 8(5):244–251, 1979.
  * [7] J. A. Bondy and U. S. R. Murty.  Graph theory.  Springer, 2008.
  * [8] K. Bringmann, T. Husfeldt, and M. Magnusson.  Multivariate Analysis of Orthogonal Range Searching and Graph Distances.  Algorithmica, pages 1–24, 2020.
  * [9] S. Cabello.  Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs.  ACM Transactions on Algorithms, 15(2):21, 2018.
  * [10] S. Cabello and C. Knauer.  Algorithms for graphs of bounded treewidth via orthogonal range searching.  Computational Geometry, 42(9):815–824, 2009.
  * [11] V. Cohen-Addad, S. Dahlgaard, and C. Wulff-Nilsen.  Fast and compact exact distance oracle for planar graphs.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 962–973. IEEE, 2017.
  * [12] D. Corneil.  A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs.  Discrete Applied Mathematics, 138(3):371–379, 2004.
  * [13] M. Erwig.  The graph Voronoi diagram with applications.  Networks: An International Journal, 36(3):156–163, 2000.
  * [14] M. Garey and D. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  A Series of Books in the Mathematical Sciences. W.H. Freeman and Company, 1979.
  * [15] C. Gavoille and C. Paul.  Optimal distance labeling for interval graphs and related graph families.  SIAM Journal on Discrete Mathematics, 22(3):1239–1258, 2008.
  * [16] P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir, and O. Weimann.  Voronoi diagrams on planar graphs, and computing the diameter in deterministic $\tilde{O}(n^{5/3})$ time.  In Proceedings of the twenty-ninth annual Symposium on Discrete Algorithms (SODA), pages 495–514. SIAM, 2018.
  * [17] A. Goldman.  Optimal center location in simple networks.  Transportation science, 5(2):212–221, 1971.
  * [18] L. Hakimi and M. Labbé.  A Locational Problem Associated with the Voronoi partition of a network.  In ORSA/TIMS Natonal Meeting (April). ORSA/TIMS, 1988.
  * [19] L. Hakimi, M. Labbé, and E. Schmeichel.  The Voronoi partition of a network and its implications in location theory.  ORSA journal on computing, 4(4):412–417, 1992.
  * [20] F. Hurtado, R. Klein, E. Langetepe, and V. Sacristán.  The weighted farthest color Voronoi diagram on trees and graphs.  Computational Geometry, 27(1):13–26, 2004.
  * [21] T. Korhonen.  A single-exponential time 2-approximation algorithm for treewidth.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 184–192. IEEE, 2022.
  * [22] K. Mehlhorn.  A faster approximation algorithm for the Steiner problem in graphs.  Information Processing Letters, 27(3):125–128, 1988.
  * [23] A. Okabe, T. Satoh, T. Furuta, A. Suzuki, and K. Okano.  Generalized network Voronoi diagrams: Concepts, computational methods, and applications.  International Journal of Geographical Information Science, 22(9):965–994, 2008.
  * [24] M. Thorup.  Undirected single-source shortest paths with positive integer weights in linear time.  Journal of the ACM (JACM), 46(3):362–394, 1999.
  * [25] R. Williams.  A new algorithm for optimal $2$-constraint satisfaction and its implications.  Theoretical Computer Science, 348(2-3):357–365, 2005.