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

arXiv: https://arxiv.org/abs/1801.10416 · HTML: https://mlsanity.com/paper/1801.10416/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2018.

## Built on by (most cited first, 2 of 2)

- [A bi-level encoding scheme for the clustered shortest-path tree problem in multifactorial optimization](https://mlsanity.com/paper/2102.09954/) (2021)
- [On Computing Top-k Simple Shortest Paths from a Single Source](https://mlsanity.com/paper/2509.26094/) (2025)

## Abstract (arXiv)

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.