Hardness, Approximability, and Fixed-Parameter Tractability of the Clustered Shortest-Path Tree Problem

Abstract

Given an $n$-vertex non-negatively real-weighted graph $G$, whose vertices are partitioned into a set of $k$ clusters, a \emph{clustered network design problem} on $G$ consists of solving a given network design optimization problem on $G$, subject to some additional constraint on its clusters. In particular, we focus on the classic problem of designing a \emph{single-source shortest-path tree}, and we analyze its computational hardness when in a feasible solution each cluster is required to form a subtree. We first study the \emph{unweighted} case, and prove that the problem is \np-hard. However, on the positive side, we show the existence of an approximation algorithm whose quality essentially depends on few parameters, but which remarkably is an $O(1)$-approximation when the largest out of all the \emph{diameters} of the clusters is either $O(1)$ or $\Theta (n)$. Furthermore, we also show that the problem is \emph{fixed-parameter tractable} with respect to $k$ or to the number of vertices that belong to clusters of size at least 2. Then, we focus on the \emph{weighted} case, and show that the problem can be approximated within a tight factor of $O(n)$, and that it is fixed-parameter tractable as well. Finally, we analyze the unweighted \emph{single-pair shortest path problem}, and we show it is hard to approximate within a (tight) factor of $n^{1-\epsilon }$, for any $\epsilon >0$.

21 pages, 3 figures