The following problem seems like a very simple and natural one, but I am not familiar with any existing work on it; in particular I am hoping to prove it is NP hard:
Let $G$ be a complete weighted graph that satisfies a triangle inequality, let $k \geq 2$ be an integer, and let $r>0$. My goal is to partition the vertices of $G$ into $k$ subsets $G_1,\dots,G_k$ with the following property: if we select any set of $k$ vertices $v_1,\dots,v_k$, with $v_i \in G_i$ for all $i$, and we let $S$ be the subgraph on the $v_i$'s consisting of edges with weights less than $r$, then we want $S$ to be connected. Thus, we're looking for a $k$-way partition that is "connected with radius $r$".
Does this ring any bells? I would think that one could prove that this is NP-hard by, say, a reduction to a maximum covering problem or a $k$-centers problem, but my attempts have been unsuccessful so far. The problem as stated is a feasibility question because we are given $k$ and $r$, but it could also be made into an optimization problem by fixing one parameter and searching for the minimum possible value of the other.