Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs

We consider the following natural problem that generalizes min-sum-radii clustering: Given is $k in mathbb{N}$ as well as some metric space $(V, d)$ where $V = F cup C$ for facilities $F$ and clients $C$. The goal is to find a clustering given by $k$ facility-radius pairs $(f_1, r_1), dots, (f_k, r_k) in F times mathbb{R}{geq 0}$ such that $C subseteq B(f_1, r_1) cup cdots cup B(f_k, r_k)$ and $sum{i=1, dots, k} g(r_i)$ is minimized for some increasing function $g : mathbb{R}{geq 0} to mathbb{R}{geq 0}$. Here, $B(x, r)$ is the radius-$r$ ball centered at $x$. For the case that $(V, d)$ is the shortest-path metric of some edge-weighted graph of bounded treewidth, we present a dynamic program that is tailored to this class of problems and achieves a polynomial running time, establishing that the problem is in XP with parameter treewidth.