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

Preprint · Mattia D'Emidio, Luca Forlizzi, Daniele Frigioni, Stefano Leucci, Guido Proietti

- Archive id: arxiv:1801.10416
- Published: 2018-01-31
- arXiv: https://arxiv.org/abs/1801.10416
- Source URL: https://arxiv.org/abs/1801.10416
- PDF: https://arxiv.org/pdf/1801.10416
- Provenance: arxiv

## 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 $Θ(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-ε}$, for any $ε\>0$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.