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

Given an n-vertex non-negatively real-weighted graph G, whose vertices are partitioned into a set of k clusters, a 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 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 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 diameters of the clusters is either O(1) or Theta(n). Furthermore, we also show that the problem is 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 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 single-pair shortest path problem, and we show it is hard to approximate within a (tight) factor of n1-ε, for any ε>0.