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.



Complexity of a very simple graph partitioning problem
For $k=2$, it's polynomial (in fact quadratic in the number of vertices). Draw an edge (in an auxiliary graph) between two vertices iff their distance is greater than $r$ (marking that these two vertices must be in the same part). Then you can partition the graph into two sets if and only if the auxiliary graph is disconnected.


