% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

\let\phi\varphi
\let\epsilon\varepsilon
\let\rho\varrho
\let\tilde\widetilde
\def\LL{\mathcal L}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{amsthm}

\usepackage{color}
\usepackage{ifpdf}
\ifpdf
  \usepackage[pdftex]{graphicx}
  \graphicspath{{./Fig_pdf/}{./Pdf/}}
  \DeclareGraphicsExtensions{.pdf}
\else
  \usepackage[dvips]{graphicx}
  \graphicspath{{./Fig_eps/}{./Eps/}}
  \DeclareGraphicsExtensions{.ps,.eps}
\fi

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}[lemma]{Theorem}
%\newtheorem{claim}[lemma]{Claim}
\newtheorem{observation}[lemma]{Observation}
\newtheorem{conjecture}[lemma]{Conjecture}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{definition}[lemma]{Definition}


\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}

\begin{document}
\setcounter{page}{157}
\begin{frontmatter}

\title{An Optimal Algorithm for the Indirect Covering Subtree Problem}

\author{Joachim Spoerhase}
\ead{joachim.spoerhase@uni-wuerzburg.de}

\address{Lehrstuhl f\"ur Informatik I, Universit\"at W\"urzburg, Am
  Hubland, 97074 W\"urzburg, Germany}

\begin{keyword}
  Graph algorithm\sep coverage\sep medianoid\sep tree\sep efficient algorithm
\end{keyword}

\end{frontmatter}

\paragraph*{Introduction}

Suppose that a company wants to open a number $r$ of facilities in a
given network, modeled by an edge-weighted graph.  A potential
customer $u$, located at some node of the graph, is willing to use the
service provided by that company if the cost thereby incurred is
limited by some bound~$\rho(u)$.  The costs are modeled by
shortest-path distances in the underlying graph, that is, the cost for
customer $u$ equals the distance to the closest server of the company.
For example, the distances may represent transportation costs or
travel times in a logistical network, but also response times in a
communication network.  If the company serves customer $u$---that is,
his distance to the closest server does not exceed $\rho(u)$---it
earns a profit of $w(u)$, which generally corresponds to the demand of
the customer.  The goal of the company is to identify $r$ locations
(nodes of the graph) for its facilities such that the total profit is
maximized.

The resulting optimization problem, called \emph{maximum coverage
  location} \cite{megiddo:maximum-coverage-location}, is NP-hard for
arbitrary graphs.  It can, however, be solved in time $O(rn^2)$ on
\emph{trees} \cite{Tamir:p-median-tree}.  As trees form the sparsest
(and thus cheapest) networks connecting a given set of nodes they play
an important role in many areas of application such as logistical and
communication networks.  For example, we may think of backbones of a
computer network, which are often tree-shaped.  This is the case that
we investigate in this paper.

In the past years there has been an increasing interest in location
problems combined with \emph{connectivity} requirements (for example,
connected dominating set, or connected facility location).  We follow
this line of research and consider a variant of maximum coverage
location on a tree where the facilities are required to form a
\emph{connected} subgraph, that is, a subtree of the input tree.
Albeit consisting of a plurality of nodes, such a subtree is
considered as a \emph{single}, \emph{tree-shaped} facility.  The cost
of this facility is given by its total edge weight. (The number of
nodes within the facility is not bounded.)  The goal is to identify a
tree-shaped facility that maximizes the net profit, that is, the
income produced by the customers minus the setup cost of the facility.
As possible application we may think of a company that wants to
establish a \emph{high-bandwidth core} (tree-shaped facility) in a
given communication network in order to provide some service to
potential customers.  A customer is only willing to pay for the
service if the response time is sufficiently low.

Kim et al.\ \cite{kim-etal:location-tree-shaped} introduce the
\emph{indirect covering subtree problem}, which can be used to model
the above scenario.  But instead of assigning to each customer a
\emph{profit $w(u)$} they assume that a \emph{penalty $\pi(u)$} is
imposed on the company if customer $u$ is \emph{not} served.  The
company aims at minimizing the sum of setup cost and the total penalty
cost.  It should be clear that both formulations are equivalent.

\paragraph*{Problem Definition}
The input of the indirect covering subtree problem is an undirected
tree $T=(V,E)$ with non-negative edge weights $c\colon
E\rightarrow\RR_{\geq 0}$.  The edge weights induce a distance
function $d\colon V\times V\rightarrow\RR_{\geq 0}$ on the node set.
Each node is associated with a radius $\rho(u)$ and a non-negative
penalty $\pi(u)$.  Consider a subtree $Y$ of $T$.  A node $u$ is said
to be \emph{covered} (indirectly) by $Y$ if $d(u,Y)\leq\rho(u)$, that
is, if $u$ lies within distance $\rho(u)$ from $Y$.  If $u$ is
\emph{not} covered by $Y$, then $u$ imposes a penalty $\pi(u)$ on $Y$.
If $U\subseteq V$ is a set of nodes then $p(U,Y):=\sum\{\,\pi(u)\mid
u\in U\text{ and } d(u,Y)>\rho(u)\,\}$ denotes the penalty imposed
on~$Y$ by~$U$.  The total penalty imposed on $Y$ is given by
$p(Y):=p(V,Y)$.  The indirect covering subtree problem asks for a
subtree $Y$ of $T$ such that the total cost $c(Y)+p(Y)$, given by the
sum of setup and penalty cost, is minimum among all subtrees of $T$.

If we require that $Y$ be a node rather than a subtree we obtain the
\emph{single maximum coverage location problem}
\cite{megiddo:maximum-coverage-location,spoerhase+wirth:single-max-coverage}.
It is not hard to see that single maximum coverage location is a
special case of indirect covering subtree.  (Scale all edge lengths
and radii with a sufficiently large factor while leaving the penalties
unchanged.)

\paragraph*{Previous Results}
The maximum coverage location problem (allowing the placement of an
arbitrary set of $r$ nodes) is NP-hard on general graphs
\cite{megiddo:maximum-coverage-location} while it can be solved in
time $O(rn^2)$ on trees \cite{Tamir:p-median-tree}.  This leads to an
$O(n^2)$ algorithm for the \emph{single} maximum coverage location
problem on trees by setting $r=1$.  Kim et al.\
\cite{kim-etal:location-tree-shaped} provide a faster algorithm
running in $O(n\log^2n)$.  Their algorithm works even for the more
general indirect covering subtree problem.  Recently a slightly faster
$O(n\log^2n/\log\log n)$-time algorithm for single maximum coverage
location has been reported \cite{spoerhase+wirth:single-max-coverage}.

\paragraph*{Our Contribution}

We propose an $O(n\log n)$ algorithm for indirect covering subtree,
which is faster than the previously best algorithms for that problem
and single maximum coverage location on trees.  We complement this
result with a matching lower bound on the running showing that our
algorithm is optimal.

Our result also implies faster algorithms for competitive location
problems \cite{Hakimi:competitive-environment}. Specifically, we
obtain an $O(n\log n)$ algorithm for $(1,X)$-medianoid and
$O(n^2\allowbreak\log n\log w(T))$ and $O(n^2\log n\log w(T)\log D)$
algorithms for the discrete and absolute $(1,p)$-centroid problems on
trees, respectively.  Here, $w(T)$ denotes the total node weight of
the tree and $D$ is the maximum edge weight.  The previously best
algorithms are slower by factor of $O(\log n/\log\log n)$
\cite{spoerhase+wirth:rp-centroid}.

\paragraph*{Sketch of the Algorithm}

We employ the algorithmic framework used by Kim et al.\
\cite{kim-etal:location-tree-shaped}.  We improve, however, one of
their core routines by using a more sophisticated technique to
subdivide trees.  This technique, which we call \emph{two-terminal
  subtree subdivision}, is a simplification of the recursive
coarsening strategy \cite{spoerhase+wirth:single-max-coverage} used
for solving single maximum coverage location on a tree.  The source of
our speedup is that we manage to avoid explicitly sorting the nodes
according to their distances and radii during the recursion, which has
been necessary in the coarsening approach and also in the original
algorithm of Kim et al.  A further advantage of our algorithm is that
it is a lot simpler than the recursive coarsening algorithm.

The two-terminal subtree technique has proved successful also for
other location problems
\cite{spoerhase+wirth:relaxed-mgf-dam,spoerhase+wirth:jda-stackelberg}.
We believe that there are further problem classes where it can be
applied.

Our algorithm is based on the so-called \emph{bitree model}
\cite{kim-etal:location-tree-shaped}.  A bitree is a directed graph
$T'$ that can be derived from an undirected tree $T$ by replacing any
edge $(u,v)$ of $T$ with a pair of anti-parallel arcs $(u,v)$ and
$(v,u)$.  With each arc $(u,v)$ of such a bitree $T'$ we associate a
cost $c_{T'}(u,v)$.  But in contrast to the edge costs in the indirect
covering subtree problem we allow these arc costs to be negative and
asymmetric.  This induces a distance function $d_{T'}\colon V\times
V\rightarrow\RR$ where $d_{T'}(u,v)$ is the length of the unique
$u$-$v$-path in $T'$.  If $v$ is a node and $U$ a set of nodes of $T'$
we define $p'(U,v):=\sum\{\,\pi(u)\mid u\in U\text{ and
}d_{T'}(u,v)>\rho(u)\,\}$ and $p'(v):=p'(V,v)$ similar to the
undirected case.

Kim et al.\ reduce the indirect covering subtree problem to the
computation of $p'(v)$ for all nodes of a given bitree.  Specifically,
they show that if $p'(v)$ can be computed in time $O(h(n))$ for all
nodes $v$ of an arbitrary bitree then the indirect covering subtree
problem can be solved in the same asymptotic running time on
undirected trees.  They develop a routine to compute the
$p'(\cdot)$-values of an bitree in total time $O(n\log^2 n)$.  Thus
they can also solve indirect covering subtree in $O(n\log^2 n)$.

We suggest an algorithm that computes all $p'(\cdot)$-values of an
arbitrary bitree in $O(n\log n)$, which yields our main result.

We assume that any node of the given bitree $T'$ has out-degree at
most three.  It is not hard to see, that this is no proper
restriction. If $s$ and $t$ are distinct nodes then $T'_{st}$ denotes
the maximal sub-bitree of $T'$ having $s$ and $t$ as leaves.  We call
$s$ and $t$ \emph{terminals of $T'_{st}$} and $T'_{st}$
\emph{two-terminal sub-bitree} (TTSB) of $T'$.

Our algorithm divides the input bitree $T'$ recursively into TTSBs.
Since we are dealing with a degree-bounded bitree we can subdivide any
TTSB $T'_{st}$ into five (or fewer) TTSBs, called \emph{child TTSBs of
  $T'_{st}$}, which have bounded size.
\begin{lemma}\label{lem:subdiv-degree-ttsb}
  Let $T'_{st}$ be a TTSB with maximum out-degree three.  Then
  $T'_{st}$ can be partitioned into five (or fewer) arc-disjoint TTSBs
  each of which having at most $\frac12|T'_{st}|+1$ nodes.  This
  subdivision can be computed in $O(|T'_{st}|)$ time. \qed{}
\end{lemma}

Consider a TTSB $T'_{st}$.  We introduce the lists $L_{d,s}(T'_{st})$
and $L_{\rho,s}(T'_{st})$.  Both lists contain all nodes $v$ of
$T'_{st}$ sorted in increasing order with respect to the values
$d_{T'}(s,v)$ and $\rho(v)-d_{T'}(v,s)$, respectively.  The lists
$L_{d,t}(T'_{st})$ and $L_{\rho,t}(T'_{st})$ are defined
symmetrically.

Our algorithm computes $p'(v,T'_{st})$ for all $v\in T'_{st}$ as well
as the four lists $L_{d,s}(T'_{st})$, $L_{d,t}(T'_{st})$,
$L_{\rho,s}(T'_{st})$ and $ L_{\rho,t}(T'_{st})$ for any TTSB
$T'_{st}$ occurring during the recursion.  We show that this
information can be propagated inductively from child towards parent
TTSBs such that we will have computed $p'(\cdot, T')=p'(\cdot)$ at the
top of the recursion.  One such propagation step takes time linear in
the size $|T'_{st}|$ of the current TTSB $T'_{st}$.  Together with
Lemma~\ref{lem:subdiv-degree-ttsb} we infer.
\begin{theorem}\label{thm:disc-single-cov-tree}
  The indirect covering subtree problem and hence also single maximum
  coverage location on a tree can be solved in time $O(n\log
  n)$. \qed{}
\end{theorem}

We complement our algorithm with a lower bound $\Omega(n\log n)$ on
the running time for solving single maximum coverage location on a
tree.  To this end we introduce a variant of the set disjointness
problem, which needs $\Omega(n\log n)$ time to be recognized on
certain real-number RAMs \cite{ben-amram+galil:RAM}.  Finally, we
provide a linear time reduction from this problem to single maximum
coverage location on a tree.

\begin{thebibliography}{KLTW96}

\bibitem[BAG01]{ben-amram+galil:RAM}
A.~M. Ben-Amram and Z.~Galil.
\newblock Topological lower bounds on algebraic random access machines.
\newblock {\em SIAM Journal on Computing}, 31(3):722--761, 2001.

\bibitem[Hak83]{Hakimi:competitive-environment}
S.~L. Hakimi.
\newblock On locating new facilities in a competitive environment.
\newblock {\em European Journal of Operational Research}, 12:29--35, 1983.

\bibitem[KLTW96]{kim-etal:location-tree-shaped}
T.~U. Kim, T.~J. Lowe, A.~Tamir, and J.~E. Ward.
\newblock On the location of a tree-shaped facility.
\newblock {\em Networks}, 28(3):167--175, 1996.

\bibitem[MZH83]{megiddo:maximum-coverage-location}
N.~Megiddo, E.~Zemel, and S.~Hakimi.
\newblock The maximum coverage location problem.
\newblock {\em SIAM Journal on Algebraic and Discrete Methods}, 4(2):253--261,
  1983.

\bibitem[SW09a]{spoerhase+wirth:single-max-coverage}
J.~Spoerhase and H.-C. Wirth.
\newblock An {$O(n\,(\log n)^2/\log\log n)$} algorithm for the single maximum
  coverage location or the {$(1,X_p)$}-medianoid problem on trees.
\newblock {\em Information Processing Letters}, 109(8):391--394, 2009.

\bibitem[SW09b]{spoerhase+wirth:jda-stackelberg}
J.~Spoerhase and H.-C. Wirth.
\newblock Optimally computing all solutions of {S}tackelberg with parametric
  prices and of general monotonous gain functions on a tree.
\newblock {\em Journal of Discrete Algorithms}, 7(2):256--266, 2009.

\bibitem[SW09c]{spoerhase+wirth:rp-centroid}
J.~Spoerhase and H.-C. Wirth.
\newblock $(r,p)$-centroid problems on paths and trees.
\newblock {\em Theoretical Computer Science}, 410(47--49):5128--5137, 2009.

\bibitem[SW10]{spoerhase+wirth:relaxed-mgf-dam}
J.~Spoerhase and H.-C. Wirth.
\newblock Relaxed voting and competitive location under monotonous gain
  functions on trees.
\newblock {\em Discrete Applied Mathematics}, 158:361--373, 2010.

\bibitem[Tam96]{Tamir:p-median-tree}
A.~Tamir.
\newblock An {$O(pn^2)$} algorithm for the $p$-median and related problems on
  tree graphs.
\newblock {\em Operations Research Letters}, 19:59--64, 1996.

\end{thebibliography}
% \bibliographystyle{alpha}


% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
%\appendix

\end{document}

